Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 20   вперед  Ctrl
 Расстановка ферзей  [new]
Dima T
Member

Откуда:
Сообщений: 12092
Поднимаю топик в продолжение этого Пятничная задачка для ума за 1 миллион $

По просьбе участников 20858476:
Aleksandr Sharahov
exp98
Вопрос возник.
Во-первых, может создать отдельно продолжение темы, но уже без денег в названии? ну не будет оно таким бурным, фигли, 20 стр уже, а дельного поискать ещё надо ... а эту закрыть.

Поддерживаю. И флуд порезать можно.

PS Предложение участникам того топика: подытожьте тут состояние своего алгоритма, что сделано, что не доделано, ссылки или копипаст из того топика, чтобы туда не возвращаться.

PPS Если какие-то ссылки надо закрепить - давите "Сообщить модератору" и пишите что нужно, буду править этот пост.
10 окт 17, 20:57    [20858804]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1316
Я сразу оттуда сюда.

kealon(Ruslan) , боюсь я некорректно написал. Базовый и базисный, оба придумал не я. Имело ввиду:
Достаточно ли в качестве базисных для получения всех правильных взять только базовые, возможно с дополнительным применением симметрий? То, что просто домножить на матрицу - это понятно, но какие свойства д.б. у это матрицы?

Вот трактовка:
Базовые используют в контексте симметрий. Их назначают.
Базисные аналогично векторному базису - они основа для разложения всех остальных на произведения (групповая операция), если существуют.

Но я о другом хотел ещё раз:
== убеждение, что причина факториального роста решений ... в возможности различных отображений: повороты, фр...(запрещённое слово)

Моё мнение несколько отличается, т.к.: N = 3+5+4+4+6+6+ .... Не бином Ньютона и не треуг-к Паскаля, но всё же комбинаторика. Вот и почти всё объяснение. И длина каждой цепочки известна= НОК(). А симметрий всего штук 10.

Но ... вспомним, что понятие симметрии давно обобщено как инвариант относительно преобразования. Просто одни имеют наглядную и быструю функцию, а ф(запрещённое слово), даже в том понимании как оно используется в задаче, их пока не очень имеет.
У меня пока всё.
11 окт 17, 10:13    [20859753]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 36634
Мой алгоритм.

Попытка оптимизировать классический поиск в глубину с возвратом в части проверок ферзя под боем.
Я обратил внимание на то что в листовых узлах поиска мы сканируем битовые матрицы o(n). Этот
Артефакт устранен.

В настоящий момент алгоритм концептуально готов и работает. Но я решил потратить ещё время
На оптимизацию копирований промежуточных temporary vectors. Поскольку я писал его на java
То создал соотв. Форк в профильном форуме.

Для доски 15 на 15 выдаёт решения со скоростью порядка 10 тыс в секунду.

Для досок с 1000 размерностью нужны другие оптимизации.

Данный алгоритм в отличие от стохастичных выдаёт гарантийно все решения.

Что ещё не сделано по топику? Не реализована задача "остаточных ферзей".
11 окт 17, 11:23    [20859991]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1484
Полезные ссылки:

1. Оригинальная формулировка и пояснения к задаче завершения расстановки ферзей на английском (перевод на русский сделал mayton).
http://claymath.org/events/news/8-queens-puzzle
В такой постановке задача не решена, но ниже приводятся решения более простых задач.

2. Картинки с фундаментальными расстановками ферзей для малых N
https://www.ibm.com/developerworks/community/blogs/HermannSW/resource/BLOGS_UPLOADED_IMAGES/n-queens_xsl.pdf?lang=en

3. Алгоритм единственной расстановки (автор Bo Bernhardsson) есть в википедии.

4. Алгоритм генерации всех расстановок ферзей на битовых масках (автор Martin Richards)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.7113&rep=rep1&type=pdf
Есть в 2 раза более быстрый вариант с использованием зеркальной симметрии.

5. В 4 раза более быстрый вариант генерации всех расстановок на битовых масках с использованием 8-кратной симметрии (зеркало и 4 вращения) и возможностью распараллеливания
http://www.ic-net.or.jp/home/takaken/e/queen/

6. Как найти одно случайное решение (в т.ч. завершение) за полиномиальное время:
http://www.fizyka.umk.pl/~milosz/AlgIILab/10.1.1.57.4685.pdf
Существует ускоренный примерно в 5 раз вариант за счет частично бесконфликтного начального заполнения.
Алгоритм не позволяет доказать отсутствие завершения.

7. Как завершить расстановку ферзей (N queens completion problem)
http://guildalfa.ru/alsha/node/35
Обзор включает реализацию всех перечисленных алгоритмов, плюс несколько доморощенных вариантов расстановки и завершения.
11 окт 17, 13:20    [20860638]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1484
Какие задачи мы точно можем решить (классификация):

1. найти любое расположение, при котором ферзи не бьют друг друга,
2. найти все такие расположения или подсчитать количество таких расположений (хотя это разные задачи, но предполагается, что найти одно без другого нереально на существующих компьютерах).

Если предположить, что на доске NxN уже стоят M<N ферзей, то можно говорить о задачах завершения расстановки: 1M (любое завершение), 2M (все завершения).

Задачи 1 и 1M имеют полиномиальную сложность, 2 и 2M – экспоненциальную.
11 окт 17, 13:38    [20860753]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1484
Симметрия, уникальность, распараллеливание.

При решении задачи 2 могут использоваться следующие виды независимых симметрий:
- зеркальная симметрия относительно вертикали (лево-право),
- повороты на 0, 90, 180, 270 градусов.

Зеркальная симметрия позволяет сократить перебор в 2 раза и, соответственно, время работы в 2 раза.

Полная симметрия (зеркало+повороты) позволяет сократить перебор почти в 8 раз и время работы в ~4 раза. При этом найденные решения проверяются на уникальность, с целью убедиться, что решение лексикографически минимально.

Решение задачи 2 можно распараллелить, развертывая внешний цикл(ы).

Для распараллеливания задач 2 и 2M также можно применить любую систему начальных заполнений, обеспечивающую полноту перебора завершений, например, разложение по строке (строкам).

P.S. Все мои посты в старой ветке теперь можно удалить.
11 окт 17, 14:14    [20860959]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

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

как практик теоретикам: экспоненциальный рост на практике - для *любой* (насколько хватило терпения) 20%-но заполненной доски всегда находится куча завершений.
11 окт 17, 14:30    [20861043]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 36634
Саша я снова протестующих против обсуждения зеркал.

Два поинта:
1) Зеркало бесполезно для стохастичных алгоритмов 1000х1000 в поиске первого остаточного решения.
2) Для полно-переборных алгоритмов отбивание зеркальных решений потребует дисковых ресурсов которых
У нас нет уже на доске 20х20.
11 окт 17, 14:55    [20861155]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

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

Речь только об использовании симметрии в задаче 2 (т.е. найти все расположения ферзей на доске NxN). В этом случае никакой памяти вообще не надо. Нужна только доп. проверка фундаментальности решения: лексикографически сравниваем найденное решение со всеми его отражениями-поворотами, и если оно совпадает с минимальным, то объявляем его фундаментальным. Вот и все. Японец же это реализовал.
11 окт 17, 15:08    [20861210]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1316
Aleksandr Sharahov
P.S. Все мои посты в старой ветке теперь можно удалить.
Кроме твоего последнего там [20858476].
11 окт 17, 15:30    [20861294]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1484
exp98
Aleksandr Sharahov
P.S. Все мои посты в старой ветке теперь можно удалить.
Кроме твоего последнего там [20858476].


Точно, сюда перенес:

Есть 3 способа переставлять и 2 способа наполнять:
1п. Переставлять больше 2х ферзей за раз - нигде не встречал.
2п. Переставлять 2 конфликтующих не между собой, если это уменьшает общее число конфликтов - быстро сходится, но из-за ям может понадобиться больше попыток.
3п. Переставлять 2 любых, среди которых есть хотя бы один конфликтующий, если это уменьшает общее число конфликтов - медленно сходится, но реже (почти никогда) попадает в ямы.
1н. Наполняем примерно 20% или чуть больше случайно-бесконфликтно, а остальное случайно с возможными коллизиями по диагоналям - быстрее найдем первое завершение.
2н. Наполняем все случайно - выше шанс найти завершение за меньшее число попыток.

В версии "3*10^6 ферзей за 1 мин" авторы случайного алгоритма похоже использовали вариант 1н+3п. Но у них в слайдах явная опечатка, так что точно не скажу.
11 окт 17, 15:44    [20861332]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1316
Aleksandr Sharahov
как практик теоретикам: - для (насколько хватило терпения) 20%-но заполненной доски всегда находится куча завершений.
С тех пор я признавался, что изменил первоначальное мнение.
Как теоретик практику:
условно говря для
(123)(456)(789)(ABCDE),
в скобочной записи начальная расстановка:
(_2_)(4__)(__9)(__CD__)
Теперь "на пальцах". Поскольку в итоге все буквы д.б. разными, а эти двигать нельзя, и циклы изолированы один от другого, то резалт зависит теперь только от диагоналей. Но строгое док-во этого как раз и хотят ВБУ. (конечно же (123) на самом деле не явля прав-й )

Мечтаю прикрутить и эту идею тоже к отсеву перебора.
11 окт 17, 17:33    [20861758]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 36634
Aleksandr Sharahov, ок.

Кстати предлагаю тебе портировать мой алгоритм на delphi
11 окт 17, 19:40    [20862060]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1484
mayton
Aleksandr Sharahov, ок.

Кстати предлагаю тебе портировать мой алгоритм на delphi


Как я понимаю, у твой алгоритм похож на этот:
http://penguin.ewu.edu/~trolfe/Queens/OptQueen.html

С ним мне будет проще справиться, т.к. в нем все типы данных "паскальные".
11 окт 17, 21:17    [20862219]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 36634
Aleksandr Sharahov, сложно сказать. Надо анализировать.
11 окт 17, 21:23    [20862228]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1484
mayton
Aleksandr Sharahov, сложно сказать. Надо анализировать.


Разумеется, за исключением зеркала и фильтра уникальных, т.е. как Listing 4
11 окт 17, 22:16    [20862326]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1316
Подвижек не видно, но сегодня пятница. Закидывыаю скриптик для разложения перестановок матрицы Е в произведение циклов.

Для запуска нужен только правильно установленный виндовс (WSH в нём).
Отладочный файл Pr, выходдной файл tt.
Запускать CScript //nologo "wscycles.vbs" <Pr >tt
Именно через CScript.ехе (но не WScript), т.к. потоковый вход/выход доступен через него.

Вообще-то, сначала пилил это на SQL, забил и сделал в д'билдере а-ля визуализацию на форме, в итоге ручной трансляцией)) переложил на VBS.
Поскольку раздел Программизм, то при желании начинающие прграммисты могут совершенствовать ЭТО до бесконечности, а онайденных багах сообщать.

Комментировать особенно нечего.
Фичи, они же направления совершенствования:
- входной алфавит задан как {1-9,0,a,b,c ...z} и вроде бы обработка регистрозависимая
- предполагается, что все слова введены через пробел (и их не очень много подряд), а не чрез любой "пробельный" символ
- лишние буквы не анализируются (в Pr намеренно внесены 'TAB', Й и BA)
- пустые строки игнорируются
- объём входных данных не проверяется
- уникальность букв и длина слова не проверяется
- лог ошибок не ведётся
- отсутствует оптимизация как по скорости, так и по памяти
Ах,да, самые внешние скобки ((...)) - воизбежание превращения в отрицательные числа после копирования в эксэл.

К сообщению приложен файл (from128.zip - 1Kb) cкачать
20 окт 17, 12:40    [20885471]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1316
Скорректировал скрипт на более общий формат входных данных, в к-ром каждый "символ" имеет вид ".004":
".01.02.03.04.05.06.07.08.09.10.11.12.13. ... .97.98.99"

Точка в формате для удобства чтения, имхо. Ожидания скрипта от входных данных регулируются константой chrwidth. В остальном всё то же.

см. вложенный файл.

К сообщению приложен файл (wscycles.zip - 1Kb) cкачать
25 окт 17, 12:59    [20898561]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Dr.Jones
Member

Откуда:
Сообщений: 7
расставить 1000 ферзей на доске 1000 на 1000 не сложно. Я написал программу которая расставила и 10К ферзей на 10к^2 доске. Но задача не об этом.
25 окт 17, 14:23    [20899063]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1316
Dr.Jones, а представляете, аж в начале самом родительской темы был представлен паттерн для доски бесконечность на бесконечность ... но задача не об том.
25 окт 17, 15:37    [20899505]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 36634
Несколько лет назад мы в топике развлекались генерацией простых чисел и факторизацией.
И вы не поверите. Несмотря на то что базовому алгоритму Эратосфена две тыщи лет в обед - если
углубитесь в задачу то зацепите и алгоритмы и теорию чисел и старика Ферма.

Топик тоже был не об этом.
25 окт 17, 23:26    [20900641]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1316
Наверное последнее из простого.

Небольшая косметика в исходнике.
В скрипт добавлено немного функционала, но он не любит экстремалов.
Спорно, так ли нужна нумерация в выходных стримах.
Параметры командной строки: -t=N
     " -t=1 - преобразовать в скобочную запись"
     "    2 - проверить правильность канонического вида"
     "    3 - таблица умножения заданных перестановок"
     "    4 - по степеням (построить циклическую группу)"
     " <stdin  >[>]stdout  или  'type файл_данных | CScript //nologo ...'  вместо <stdin"


Кто бы ещё дал экзешник под вин7 для генерации в поток решений в размерностях 10 - 100 ? Боюсь, вбс не потянет сотню.
26 окт 17, 18:47    [20903857]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Matric77
Member

Откуда:
Сообщений: 137
Проведена оценка количества решения для досок большого размера методом подбора.
Количество решений для доски размера N можно представить в виде одной формулы:
R(N) = R(17) * KR^(N-17) * (N+1)! / 17!
где КR = 0,3891;
R(17) - количество решений для доски размера 17
15 ноя 17, 20:06    [20957828]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Matric77
Member

Откуда:
Сообщений: 137
В предыдущем сообщении была допущена ошибка. Теперь правильно:
R(N) = R(17) * KR^(N-17) * N! / 17!
где КR = 0,3891;
R(17) - количество решений для доски размера 17
15 ноя 17, 21:02    [20957940]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Matric77
Member

Откуда:
Сообщений: 137
Если считать по предыдущей формуле на компьютере, то помещается в ячейку только число, не превышающее значения 4,0496E+306, что является количеством решений только для доски размера 207. Получается, что пока трудно посчитать оценку количества решений задачи 8 ферзей для доски размера 1000, не говоря о досках большего размера.
16 ноя 17, 12:59    [20959651]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 20   вперед  Ctrl
Все форумы / Программирование Ответить