Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 10 11 12 13 14 [15] 16 17 18 19 20   вперед  Ctrl
 Re: Пятничная задачка для ума за 1 миллион $  [new]
tip78
Member

Откуда: Москва
Сообщений: 474
exp98
jbond, не учи меня жить, лучше помоги доказать, что А*А обязателно неправильн, если А - правильн, с наскоку не получилось.
Возможно, что также А*В - неправильн, если обе правильн.

а что вы хотите получить?
чтобы работало перемножение матриц стороны должны быть одинаковы
кол-во строк A = кол-во столбов B или наоборот
но в нашем случае это 2 одинаковых доски
25 сен 17, 12:44    [20820344]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
exp98
Ааа, ясно ....
выше снова хрень написал, надоело оправдываться, почистил бы кто за мной ... ((((((
tip78
а что вы хотите получить?
док-во либо оповержение гипотезы, сформулированной лишь на примерах N=8 и 5
25 сен 17, 12:55    [20820379]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
неправильность - если по диагонали бьются, коллизии то есть по-местной терминологии. А так у нас они все квадратные.
Для А2 критерий для диагоналей звучит так (перефразировка для циклических разложений): суммы всех пар соседних чисел различны и разности - тоже (а значит разнообразие и тех и других = N).
Гипотеза в том, что сумм либо разностей пар через одного меньше N, а значит имеются 2 одинаковых значения.
Либо непосредственно доказать перемножением, либо по индукции, либо ...... хрз.

Для А*В - формулировка похожая.
25 сен 17, 13:05    [20820420]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
ex1276
Guest
Коллеги, потратил вечер

Получил пару формул расчета количества решений для задачи N ферзей. Просто пошел через разные константы.

Одна формула, как выяснилось, почти повторяет расчеты Benoit Cloitre Nov 10 2002 (constant c around 2.54 such that a(n) is asymptotic to n!/c^n), но является расходящейся, как и его формула. Он не нашел константу, но там в принципе подходит (e) = exp(1). Надо калибровать.

Вторая является сходящейся и с ростом n дает все более точные результаты (на имеющихся данных).
Удивило, что для доски 15x15 точность равна 0,00028.
Точность на 27x27 равна 0,0186 (при точности Benoit Cloitre 0,0879) - более чем в 4 раза лучше.
Еще один компонент формулы мне не нравится, опять же надо калибровать.

Думал, что решения четных и нечетных досок должны подчиняться разным закономерностям. Но это не так.
Цифры страшенные получаются. Любые алгоритмы перебора в принципе никогда не справятся.
Excel выдержал расчет количества решений для досок до 150x150.

Что скажете, в этом есть какая-то ценность?

Полезная ссылка:
https://oeis.org/search?q=A000170
26 сен 17, 13:14    [20823620]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
ex1276,

конечно, есть.

При желании, опубликовать можно. У буржуев есть онлайн журнал по комбинаторике, есть arxiv.org
26 сен 17, 14:27    [20823942]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
exp98, а я о своём безотносительно текущей ценности.
Себе уже не верю. Пробую схематично повторить здесь факты из в/алгебры.
+
Каждое {А^k} конечно, след-но когда-нить цепочка (траектория) повторится (к=р - наименьшее такое).
Тогда предпоследний в цепочке Ар = Е, Ар-1 = А-1 = А*.
Т.о. {А^k} - ЦГ порядка р. при любом А, в т.ч. и для наших правильных А.
ЦГ - не пересекаются либо полностью подмнож-во одно другого.
Отсюда сразу следует, что А2 не образует самостоятельную траекторию, иначе бы с неё начиналась другая цепочка, а они не могут пересекаться.

Ниже для А - правильных.
Также следует и то, что если А - правильн, тогда А2 (если порядок больше 3) не будет правильн (т.к. у каждой правильн своя траектория, и пересекаются только в Е).
При р=3 имеем только {А, А*, Е}.
Аналогично, никакая Аi из {А^k} не образует самостоятельную траекторию и одновременно она неправильн при р из [2, n-2].
В итоге получилось док-во гипотез для всех N (выдвинутых при N=8).

+
С другой стороны, ЦГ A порядка, скажем 12, можно разложить в прямое произведение ЦГ-3 и Цг-4, т.е. в виде всех пар {bi*cj}, 3 и 4 - взаимопростые множители.
В скобочной форме записи перестановок это выглядит типа (123)(4)(5)(6)(7)(8) * (1)(2)(3)(4567)(8)
Пример.
А= (1482)(356)(7) - правильн.
В=(1482)(3)(5)(6)(7) , С= (1)(4)(8)(2)(356)(7) - неправ.
А= В*С = С*В
То есть некоторые правильн можно получать получать произведением спец. неправильных. Как генерить эти спец, стоит ещё подумать.

Теперь хочется проверить ещё гипотезу.
А * В = С - неправ., если А и В правильные, т.е найденные траектории нельзя получить друг из друга умножением на правильную.
26 сен 17, 14:53    [20824086]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98,

немного запутывает дело терминология "правильности" перестановки, т.к. уже есть правильные матрицы и искомая расстановка ферзей как раз соответствует некоторой правильной матрице, но с дополнительным условием правильности - отсутствием атак по диагонали.
26 сен 17, 16:17    [20824414]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
А где раздел терминов? шучу ... я изначально здесь говорю так:
Есть единичная матрица Е.
Перестановками строк получаем все остальные. Всего N! матриц.
Среди них только некотрые удовлетворяют правилам расстановки фишек для классич. задачи N-фишек. Их я зову правильными. (для n=8 их 92)
Ак - эквивалент A^k
Ар - эквивалент A^0 = A^p, p - порядок ЦГ
26 сен 17, 17:19    [20824607]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Вообще, фигово, когда одни просто правильные, а другие более правильные )
Я пишу соответственно неправильные / правильные.
26 сен 17, 17:23    [20824620]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
А подкиньте, кому нетрудно, на пропитание правильные расстановки для N=9, штук 10-20 без симметрий. Одна у меня есть (13786254)(9).
26 сен 17, 18:21    [20824771]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35705
Давайте базу заведем. Я как бывший базовик могу взять на себя часть усилий.
26 сен 17, 19:03    [20824880]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98
А подкиньте, кому нетрудно, на пропитание правильные расстановки для N=9, штук 10-20 без симметрий. Одна у меня есть (13786254)(9).


https://www.ibm.com/developerworks/community/blogs/HermannSW/resource/BLOGS_UPLOADED_IMAGES/n-queens_xsl.pdf?lang=en
26 сен 17, 19:22    [20824907]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98
Вообще, фигово, когда одни просто правильные, а другие более правильные )
Я пишу соответственно неправильные / правильные.


Об этом речь.
Сносит крышу, когда правильную матрицу называют неправильной.
Называй по-другому как-нибудь, например, красивая )
26 сен 17, 19:34    [20824926]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35705
Почему-то вспомнились фундаментальные частицы из физики. С довольно странными названиями
типа кварк "красивый", кварк "прелестный" и т.п. Либо физики объединились в творческом экстазе
с лириками либо это был просто троллинг уставших от прагматизма теоретиков.
26 сен 17, 23:00    [20825316]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
tip78
Member

Откуда: Москва
Сообщений: 474
вот тут неплохой словарик
27 сен 17, 00:05    [20825449]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35705
Как хранить найденные матрицы?

Если база - то оптимально положить вектор ферзей в строку. Причём так положить чтобы
Учесть поиски остаточных решений. А также учесть в логике презентации (view)
Повороты и отражения.
27 сен 17, 09:49    [20825789]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Aleksandr Sharahov
exp98
Вообще, фигово, когда одни просто правильные, а другие более правильные )
Я пишу соответственно неправильные / правильные.
Об этом речь.
Сносит крышу, когда правильную матрицу называют неправильной.
...Но приговор с издёвкой
И не согласен вовсе я,
Меняй формулировку! (с)

Чем же она правильная? правильная для ладей?
- 2*2= ?
- ну там 7, 8, но ни как не 9.
- Ответ немножко правильный, но 7 более правильный, т.к. в стандартной метрике он ближе к искомому.

Или расчётный счёт для платежа правильный, но не совсем. А, ерунда, попробуйте на другой счёт, может получится.

Они все просто даны в исходном множестве перестановок из Е. Других матриц у меня для вас нет.
А правильными везде называют искомые, у людей во всяк случ. Стало быть остальные неправильные. 2-значная классическая логика.

Как раз разные там немножко правильные, чуть более чем немного менее правильные, по-другому правильные и т.п. -- вот это не как у людей. Привычка - дело такое ...
27 сен 17, 10:39    [20825984]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
mayton
Как хранить найденные матрицы? Если база - то оптимально положить вектор ферзей в строку
Да может банально в 4 столба? id, num, row, col ? для начала. К полю по его номеру доступаться не комильфо. Тем более рекуррентно доступаться.
Вопрос другой, как долго хранитель будет хранить?
27 сен 17, 10:46    [20826023]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98
Aleksandr Sharahov
пропущено...
Об этом речь.
Сносит крышу, когда правильную матрицу называют неправильной.
...Но приговор с издёвкой
И не согласен вовсе я,
Меняй формулировку! (с)

Чем же она правильная? правильная для ладей?...


Именно. В алгебре правильной матрицей часто называют матрицу без полностью нулевых строк и столбцов. Иногда различают правильные по строкам и правильные по столбцам.

Но нам пофиг, конечно. А чтоб нас ваще никто не понял простыми назовем все числа, кратные 2, а четными все степени двойки )
27 сен 17, 11:43    [20826286]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Демагогия не в названиях. Видите ли, эти - неправильные, но мы их и не используем ...
Здесь читать, здесь не читать, а здесь это мы рыбу заворачивали ... А зачем тогда о них вспоминать? Тем более не годится отсылка к тому, что ежели кто-то где-то иногда застолбил это название за другим свойством ... КМ не показатель - там как раз аналогов не было.

В любом случае я 3 раза давал определение и поступил более логично, да и научно. И продолжу его придерживаться:
- Определил рассматриваемое мн-во
- Разделил его на 2 класса
- Именовал классы (важно!) как можно более естесственно.

Без вот этого предварительного шага:
- Вспоминаем всё множество.
- Забываем его бОльшую часть, но именуем её.
- .....
27 сен 17, 12:16    [20826383]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98,

да я не против, не пойми меня неправильно )
27 сен 17, 12:32    [20826420]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
дык и я всего лишь иронизировал
только на демагогию у меня рефлекс, трудно смолчать
27 сен 17, 14:16    [20826726]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
ex1276
Guest
Коллеги, правильно я понимаю, что любой из алгоритмов перебора так или иначе имеет три блока:

1. Перебор ладейных матриц (нет пересечений ферзей по горизонталям и вертикалям)
В сущности это достигается обычной перестановкой в комбинаторике, количество матриц = N!

Асимптотическая формула количества таких матриц = КОРЕНЬ( 2 * ПИ() * N ) * ( N / EXP(1) ) ^ N
Для доски 100x100, количество ладейных матриц = 10^158

2. Проверка матриц по диагоналям (нет пересечений ферзей на диагоналях) - неуникальные решения задачи

Асимптотическая формула количество решений = КОРЕНЬ( 2 * ПИ() * M ) * ( M / EXP(2) ) ^ M , где M = N +1
Для доски 100x100, количество неуникальных решений = 10^116

3. Проверка решений на уникальность и подсчет количества решений.
27 сен 17, 18:19    [20827522]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Так уж однозначно не скажу:
1) - да, по формуле Стирлинга
2) - да, формулой не интерсовался
3) - как вариант

Можно добавить
4) Управление перебором / фильтрация (подряд / локальные поиски / рекуррентные поиски / ассоциативные поиски ...)
Для задачи с начальным расположением п.4 актуален.
27 сен 17, 19:18    [20827597]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
1. Не совсем. Просто рекурсия или цикл по строкам.
2. Проверка по столбцам и диагоналям выполняется одновременно.
3. Проверка на уникальность нужна только при генерации всех расстановок с учетом симметрии.
27 сен 17, 19:50    [20827641]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 10 11 12 13 14 [15] 16 17 18 19 20   вперед  Ctrl
Все форумы / Программирование Ответить