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

Книги по головоломкам, в том числе электронные.

Модератор: SergR

Аватара пользователя
SergR
Администратор
Сообщения: 508
Зарегистрирован: 02 май 2015, 21:06
Откуда: г. Красный Сулин, Ростовской обл.
Интересы: Член клуба ценителей головоломок "Диоген".
Пол: Мужской
Страна: Russia
Возраст: 49

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

Сообщение SergR » 14 янв 2016, 12:34

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

"Попытайтесь быть хотя бы немного добрее, и вы увидите, что будете не в состоянии совершить другой поступок."
Конфуций

#1
Аватара пользователя
SergR
Администратор
Сообщения: 508
Зарегистрирован: 02 май 2015, 21:06
Откуда: г. Красный Сулин, Ростовской обл.
Интересы: Член клуба ценителей головоломок "Диоген".
Пол: Мужской
Страна: Russia
Возраст: 49

Re: Алгоритмы решения перестановочных головоломок

Сообщение SergR » 14 янв 2016, 12:40

Неинформированный метод поиска всегда находит оптимальное решение если вообще решение существует.
Весь процесс поиска решения сдвигашек по этим алгоритмам можно представить как задачу поиска на графе. Вершинами такого графа будут состояния поля головоломки, полученные в результате перемещения элементов
Изображение
Основные недостатки этих алгоритмов - это большой объем памяти и скорость работы, так как все состояния игры надо хранить в памяти. Так для головоломки пятнашки существует 16!/2 возможных состояний
Включает основные алгоритмы поиска:
  • Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Необходимо проверять текущее состояние с уже проверенными вершинами на предмет наличия бесконечного цикла. Первое найденное решение может не быть минимальным
    Изображение
  • Поиск в ширину (англ. breadth-first search, BFS) — это стратегия поиска решений в пространстве состояний, в которой вначале развёртывается корневой узел, затем — все преемники корневого узла, после этого развёртываются преемники этих преемников и т.д. Прежде чем происходит развёртывание каких-либо узлов на следующем уровне, развёртываются все узлы на данной глубине в дереве поиска. Всегда находит решение с минимальным количеством ходов
    Изображение
  • Поиск с ограничением глубину (англ. depth-limited search, DLS) — вариант поиска в глубину, в котором применяется заранее определённый предел глубины, что позволяет решить проблему бесконечного пути. Поиск с ограничением глубины применяется в алгоритме поиска с итеративным углублением.
  • Поиск в глубину с итеративным углублением (англ. iterative-deepening depth-first search, IDDFS, DFID) — стратегия, которая позволяет найти наилучший предел глубины поиска DLS. Это достигается путём пошагового увеличения предела до тех пор, пока не будет найдена цель.
  • Двунаправленный поиск (англ. bidirectional search) в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в том, что можно одновременно проводить два поиска (в прямом направлении, от начального состояния, и в обратном направлении, от цели), останавливаясь после того, как два процесса поиска встретятся на середине.
С уважением, Сергей.

"Попытайтесь быть хотя бы немного добрее, и вы увидите, что будете не в состоянии совершить другой поступок."
Конфуций

#2
Аватара пользователя
SergR
Администратор
Сообщения: 508
Зарегистрирован: 02 май 2015, 21:06
Откуда: г. Красный Сулин, Ростовской обл.
Интересы: Член клуба ценителей головоломок "Диоген".
Пол: Мужской
Страна: Russia
Возраст: 49

Re: Алгоритмы решения перестановочных головоломок

Сообщение SergR » 14 янв 2016, 12:42

Информированный метод надо готовить инфу.
С уважением, Сергей.

"Попытайтесь быть хотя бы немного добрее, и вы увидите, что будете не в состоянии совершить другой поступок."
Конфуций

#3
Аватара пользователя
Lion
Пользователь
Сообщения: 74
Зарегистрирован: 10 дек 2015, 08:02
Откуда: г. Тольятти, самарская обл.
Интересы: Выпиливание лобзиком, жонглирование, игра на гитаре.
Пол: Мужской
Страна: Russia
Возраст: 28

Re: Алгоритмы решения перестановочных головоломок

Сообщение Lion » 14 янв 2016, 12:50

Класс, очень интересно. Аж захотелось соответствующую литературу почитать. Так и сделаю. Огромное спасибо SergR за этот экскурс.
С уважением, Lion

#4
Аватара пользователя
SergR
Администратор
Сообщения: 508
Зарегистрирован: 02 май 2015, 21:06
Откуда: г. Красный Сулин, Ростовской обл.
Интересы: Член клуба ценителей головоломок "Диоген".
Пол: Мужской
Страна: Russia
Возраст: 49

Re: Алгоритмы решения перестановочных головоломок

Сообщение SergR » 14 янв 2016, 13:52

Литературы валом, особенно на англицком языке, да на основе пятнашек, да еще написанные метром алгоритмов Д.Кнутом, да еще с эвристическими функциями - читать неперечитать.
С уважением, Сергей.

"Попытайтесь быть хотя бы немного добрее, и вы увидите, что будете не в состоянии совершить другой поступок."
Конфуций

#5

Вернуться в «Литература»

Кто сейчас на конференции

Сейчас этот форум просматривают: CommonCrawl [Bot] и 0 гостей