В чем ошибка алгоритма(8 Puzzle, A*)?

Question

[Виталий Витренко]

Застрял с решением этого задания на Coursera.
Вообщем все особенности рассказать сложно здесь, поэтому надеюсь кто то проходил этот курс тоже.
Я практически реализовал этот алгоритм, но с некоторыми пазлами приключается вот какая проблема.
Допустим есть такая доска
На первом шаге получается в очередь с приоритетами заносятся два его "соседа".

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

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

Видимо я что то понял не так. Но некоторые пазлы(там где приоритеты не совпадают) собираются нормально. В чем ошибка в моих рассуждениях?

P. S. На форуме Coursera я уже спросил, но т.к. курс уже заканчивается, там сейчас довольно мало людей.
P. P. S. Еще раз, все подробности я не описывал, поэтому вопрос рассчитан на тех кто решал подобную задачу.

Answer 1

[Rsa97]

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

Comments

[Виталий Витренко]

Да, в этом и была проблема :)

Answer 2

[localghost]

А почему, если вы переходите к 3-0-2-1 (второму варианту первого шага), у вас в цепочке остается 2-3-0-1 (первый вариант первого шага)? У вас есть класс SearchNode с полем, условно, previous?

Upd.: или там могу сначала спросить: элементы очереди какого класса?

Comments

[Виталий Витренко]

Да, проблему я уже решил, считать за правильную последовательность надо было не все извлеченные SearchNode а только те что были связаны с начальным и конечным через previous.

[localghost]

Ок :)