A * Поиск, узел, который будет расширен следующим, когда функция оценки оценивает то же самое

Question

У меня проблемы с пониманием того, какой узел / состояние следует развернуть следующим в дереве поиска A *, когда функция оценки (f (n) = g (n) + h (n)) оценивает одно и то же для двух узлов.
Пример 1

Tree1 http://i39.tinypic.com/22w6d.jpg

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

Пример 2

Tree2 http://i39.tinypic.com/2wemfxg.jpg

В этом примере функция оценки B была меньше, чем C, и, следовательно, была расширена, но сгенерировала узел D с тем же f, что и C, в этом случае какой узел будет выбран для расширения следующим?

(я понимаю, что этот вопрос, вероятно, должен был быть размещен на cstheory.stackexchange, но у меня недостаточно репутации, чтобы публиковать изображения, извинения)
Заранее спасибо

Answer 1

Неважно, какой из них будет выбран, зависит от реализации приоритетной очереди, но чаще это будет C, поскольку вновь созданный узел D не будет идти перед C, который уже находится в очереди. Если мы продолжим с C и позже мы поймем, что h (C) был недооценен, то значение f текущего узла (аксессора C) станет больше, чем f (D), чем алгоритм вернется назад и расширит D, когда станет вершиной. очереди. Это будет работать, поскольку эвристика h всегда должна давать меньшие или равные значения, чем реальная стоимость.