Как поиск A * выбирает следующий узел, когда добавляются узлы с одинаковым значением heauristi c?

Question

У меня есть базовое c понимание концепции, но модельный ответ, данный лектором, смутил меня,

Меня смущает тот факт, что (2,3) узел B расширяется раньше (2,3) узла, который теоретически сначала добавляется в очередь (до добавления узла B)

Это дерево является графическим представлением оценки кратчайшего пути сетки. Это дерево не означает, что (2,3) узел не имеет дочерних элементов на самом деле они ссылаются на одно и то же место в сетке. Может кто-нибудь уточнить, что я пропустил? Заранее спасибо:)

Answer 1

Ответ в том, что до реализации очереди приоритета.

Возьмите обычную реализацию heap с массивом. Элементы упорядочены следующим образом:

0 1 2 3 4 5 6 7 8 9 10

Но ниже позиции i следующие два: 2i+1 и 2i+2. Таким образом, массив представляет собой древовидную структуру, которая выглядит следующим образом:

[0,
  [1,
    [3, [7, 8]],
    [4, [9, 10]]]],
  [2, [5, 6]]]

Теперь предположим, что 3, 5 имеют одинаковый приоритет друг с другом и поэтому 6, 7. И эти 4 были добавлены в этом порядке. Также предположим, что куча сбрасывает верхний (левый, как вы думаете об этом) элемент первым на связях. Затем, когда вы извлечете, мы в конечном итоге доберемся до 3 и 5 до дна и 3 сначала упадут. Но когда вы продолжите извлечение, вы в конечном итоге получите значение ie между 6, 7, и теперь 7 находится сверху (слева, как бы вы ни сориентировали свое мышление), и поэтому оно падает первым.

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

Это напрямую связано с тем, почему Heapsort не является стабильной сортировкой.