N-головоломка с сеткой 5x5, теоретический вопрос

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

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

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

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

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

Спасибо

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

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

  • Создайте новый список для периферии, отсортированный по используемой эвристике.
  • Создайте набор для хранения посещенных узлов
  • Добавьте начальное состояние головоломки к краю
  • while the fringe isn't empty..
    • pop the first element from the fringe
    • если узел был посещен ранее, пропустите его
    • если узел является целью, вернуть его
    • добавить узел в наш посещенный набор
    • разверните узел и добавьте всех потомков обратно к краю

artificial-intelligence algorithm heuristics
person Gary    schedule 22.08.2010    source источник
comment
Это зависит от вашего определения посещения, но в 2D вы можете войти в узел с нескольких направлений, поэтому, возможно, вы исключаете лучшие ходы, если маскируете работу неправильно.   -  person Mark Elliot    schedule 22.08.2010
comment
Чтобы быть техническим, A * завершен только тогда, когда эвристика оценивается меньше, чем фактическая стоимость.   -  person Nick Larsen    schedule 26.08.2010

Ответы (4)


arrow_upward
3
arrow_downward

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

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

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

person Eiko    schedule 22.08.2010

arrow_upward
2
arrow_downward

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

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

person John R. Strohm    schedule 22.08.2010
comment
Спасибо за ваш ответ, но согласно комментарию, который я оставил на Ювале А, то, как я перетасовываю плитки, всегда должно приводить к разрешимой доске, видя, как я просто случайным образом перемещаю пустой квадрат. - person Gary; 23.08.2010
comment
Как ответила Эйко, если вы начнете с неразрешимой конфигурации, вы закончите после того, как N переместится снова в неразрешимую конфигурацию. - person Agnius Vasiliauskas; 26.08.2010

arrow_upward
0
arrow_downward

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

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

person Yuval Adam    schedule 22.08.2010
comment
Случайность включает в себя 10 различных случайных движений пустой плитки, поэтому я считаю, что это всегда будет генерировать решаемую головоломку за ‹ 10 ходов. Я обновил свой пост, добавив еще немного теории о том, как я делаю что-то, не могли бы вы взглянуть еще раз? - person Gary; 22.08.2010

arrow_upward
0
arrow_downward

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

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

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

person Nick Larsen    schedule 26.08.2010