Алгоритмы решения сдвигашек и пятнашек.

[SergR]

Добрый день всем.
Как-то играясь с SBPSolver http://dev.culand.ch/SBPSolver.htm  - решателем головоломок типа сдвигашек, задумался над тем какой алгоритм применяется при решении таких задач. Даже сел за повторное (первое в институте) изучение графов в интуите.ру. Гуглением (пока гугл меня не забанил ) нашел алгоритмы А*, поиск вширину, прыжки, волновой (по-моему) синтез. Но все они для одной движущейся фишки, остальные при этом рассматриваются как неподвижные. А в жизни все сложнее - уже установленную на свое место фишку необходимо сдвинуть, что бы попытаться поставить на место другую. Или вместе с 1 (в пятнашках) зацепить паровозиком и 2 что бы было меньше ходов и т.д.
Так вот вопрос - может у кого есть такие наработки или ссылки на что-нибудь подобное. Затеял все для того что бы мозги жиром не заплыли

[pytlivyj]

Ссылка на историю.

Алгоритмы решения многих головоломок в буквенном варианте приведены в книге «Математические головоломки» в 2-х частях.
I-я часть была выпущена издательством «Знание» в 1990 г.. Во II-ой части шло описание сборки кубиков Рубика, начиная с 2х2х2 до 6х6х6, и даже N - слойного! Но в связи с перестройкой и распадом СССР, II-я часть книги свет так и не увидела. Автором книги является Анатолий Тимофеевич Калинин в соавторстве с Владимиром Натановичем Дубровским. Книгу эту можно легко найти в художественной библиотеке.

[Николай]

Добавлю, что ссылка на электронную версию этой замечательной книги есть у нас на форуме в соответствующей теме.

[SergR]

Наверное некорректно поставил вопрос. SBPSolver находит решение с минимальным количеством передвижений при различных по форме и количеству плиточек и форме и размеру игрового поля. А в вышеуказанной книге нет универсального решения, к каждой головоломке индивидуальный подход (что неприемлемо для программной реализации). "... мы наметили и общий план решения головоломок этого типа. Но, честно говоря, алгоритмы, составленные по этому плану, будут неуклюжими, громоздкими, плохо защищенными от ошибок. Так что в каждом конкретном случае ... простор для применения фантазии, изобретательности и логических способностей остается открытым" - выдержка из этой книги.
При поверхностном изучении алгоритмов понял, что существует "некономичный" алгоритм поиска в ширину. Он вроде самый универсальный, но и долгий. В игре типа 15 существет 16! разных вариантов размещения плиток иполовину из них последовательно нужно перебрать для поиска кратчайшего пути решения (в грубом прочтении алгоритма).
Буду дальше изучать алгоритмы и графы, тем более этот предмет один из немногих был мне понятен и интересен в институте.

[grigr]

Тут есть пара солверов, изучай
http://twistypuzzles.ru/forum/index.php/topic,422.msg5020.html#msg5020

[SergR]

Тут есть пара солверов, изучай
http://twistypuzzles.ru/forum/index.php/topic,422.msg5020.html#msg5020

Благодаря этим ссылкам и "забил" голову такой проблемой. Спасибо

[grigr]

можно понаблюдав за их работой вычислить и их алгоритм...

[SergR]

Если кому интересно, то расскажу о моих исследованиях данной проблемы.
На текущий момент существует два типа алгоритмов, которые можно применить к кратчайшему решению головоломок типа сдвигашек и пятнашек - это неинформированный и информированный.
Неинформированный поиск (также слепой поиск, метод грубой силы, англ. uninformed search, blind search, brute-force search) — стратегия поиска решений в пространстве состояний, в которой не используется дополнительная информация о состояниях, кроме той, которая представлена в определении задачи. Всё, на что способен метод неинформированного поиска, — вырабатывать преемников и отличать целевое состояние от нецелевого.
Информированный поиск (также эвристический поиск, англ. informed search, heuristic search) — стратегия поиска решений в пространстве состояний, в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами.
Информация о конкретной задаче формулируется в виде эвристической функции. Эвристическая функция на каждом шаге перебора оценивает альтернативы на основании дополнительной информации с целью принятия решения о том, в каком направлении следует продолжать перебор. К слову сказать - информации на русском языке практически ноль, а вот на английском языке (дипломы, курсовые и др. документы) достаточно.

[SergR]

Неинформированный метод поиска всегда находит оптимальное решение если вообще решение существует.
Весь процесс поиска решения сдвигашек по этим алгоритмам можно представить как задачу поиска на графе. Вершинами такого графа будут состояния поля головоломки, полученные в результате перемещения элементов

Основные недостатки этих алгоритмов - это большой объем памяти и скорость работы, так как все состояния игры надо хранить в памяти. Так для головоломки пятнашки существует 16!/2 возможных состояний
Включает основные алгоритмы поиска:

• Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Необходимо проверять текущее состояние с уже проверенными вершинами на предмет наличия бесконечного цикла. Первое найденное решение может не быть минимальным

• Поиск в ширину (англ. breadth-first search, BFS) — это стратегия поиска решений в пространстве состояний, в которой вначале развёртывается корневой узел, затем — все преемники корневого узла, после этого развёртываются преемники этих преемников и т.д. Прежде чем происходит развёртывание каких-либо узлов на следующем уровне, развёртываются все узлы на данной глубине в дереве поиска. Всегда находит решение с минимальным количеством ходов

• Поиск с ограничением глубину (англ. depth-limited search, DLS) — вариант поиска в глубину, в котором применяется заранее определённый предел глубины, что позволяет решить проблему бесконечного пути. Поиск с ограничением глубины применяется в алгоритме поиска с итеративным углублением.
• Поиск в глубину с итеративным углублением (англ. iterative-deepening depth-first search, IDDFS, DFID) — стратегия, которая позволяет найти наилучший предел глубины поиска DLS. Это достигается путём пошагового увеличения предела до тех пор, пока не будет найдена цель.
• Двунаправленный поиск (англ. bidirectional search) в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в том, что можно одновременно проводить два поиска (в прямом направлении, от начального состояния, и в обратном направлении, от цели), останавливаясь после того, как два процесса поиска встретятся на середине.

[Isaev]

Для решения пятнашек можно вполне применять тот самый A*, который ты нагуглил в самом начале, с простенькой эвристикой. Можно уложиться в пару секунд для поиска оптимального решения из любой ситуации.
Число бога для классичекого поля 4х4 равно 80.