N-Puzzle с сеткой 5x5, теоретический вопрос

Question

Я пишу программу, которая решает 24-головоломку (сетка 5x5), используя две эвристики.Первый использует количество блоков в неправильном месте, а второй использует расстояние Манхэттена между текущим местом и требуемым местом блоков.

У меня есть разные функции в программе, которые используют каждую эвристику с A * и жадным поискоми сравнивает результаты (итого 4 разных части).

Мне любопытно, неверна ли моя программа или это ограничение головоломки.Головоломка генерируется случайным образом, кусочки перемещаются несколько раз, и большую часть времени (~ 70%) решение найдено при большинстве поисков, но иногда они терпят неудачу.

Я могу понять, почему жадность потерпит неудачу,поскольку он не завершен, но, видя, как A * завершен, это заставляет меня поверить в то, что в моем коде есть ошибка.

Итак, кто-то может сказать мне, является ли это ошибкой в ​​моем мышлении или ограничениемголоволомка?Извините, если это плохо сформулировано, я перефразирую при необходимости.

Спасибо

РЕДАКТИРОВАТЬ:

Так что я вполне уверен, что что-то я делаю не так.пошаговый список того, как я делаю поиски, здесь что-то не так?

• Создать новый список для группы, отсортированный по используемой эвристике
• Создайте набор для хранения посещенных узлов.
• Добавьте начальное состояние головоломки на край
• , пока край не пустой.
  • извлеките первый элемент изкрай
  • если узел был посещен ранее, пропустите его
  • , если целью является узел, верните его
  • добавьте узел к нашему посещенному набору
  • разверните узел и добавьте всех потомков обратно на край

Answer 1

Если вы имеете в виду эту скользящую головоломку: это решаемо, если вы обмениваетесь двумя частями из рабочего решения - поэтому, если вы не находите решение, это ничего не говорит о правильности вашего алгоритма.

Это просто твое семя испорчено.

Изменить: Если вы начнете с решения и сделаете (случайные) законные шаги, то правильный алгоритм найдет решение (так как изменение порядка является решением).

Answer 2

Не совсем ясно, кто изобрел его, но Сэм Лойд популяризировал загадку 14-15, в конце 19-го века, которая является 4x4 версией вашего 5x5.

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

Answer 3

Хотя перечисленные вами шаги кажутся немного неполными, вы перечислили достаточно, чтобы ваш A * нашел решение, если оно есть (хотя и не оптимально, если вы просто пропускаете узлы).

Звучит так, что либо генерация вашей головоломки неверна, либо ваш алгоритм не реализован правильно. Чтобы легко проверить генерацию головоломки, сохраните шаги, использованные для генерации головоломки, и запустите ее в обратном порядке и проверьте, является ли результат состоянием решения, прежде чем разрешить отправку головоломки в поисковые процедуры. Если вы когда-либо создали недопустимую головоломку, сбросьте головоломку и ожидаемые шаги и посмотрите, в чем проблема. Если загадка пройдена и алгоритм не работает, вы, по крайней мере, сузили суть проблемы.

Если это ваш алгоритм, опубликуйте более подробное объяснение шагов, которые вы на самом деле реализовали (не только как работает A *, мы все это знаем), например, когда вы запускаете функцию оценки и Вы прибегаете к списку, который действует как ваша очередь. Это облегчит определение проблемы в вашей реализации.

Answer 4

Я предполагаю, что ваш код верен, и вы правильно реализовали все алгоритмы и эвристики.

Это оставляет нам «сгенерированную случайно» часть вашей инициализации головоломки. Вы уверены, что генерируете правильные состояния головоломки? Если вы создадите нелегальное состояние, очевидно, что решения не будет.