D * lite: как сравнить и отсортировать парные ключи?

Question

Я пытаюсь реализовать алгоритм поиска пути D * -Lite, как описано в статье 2002 года Кенига и Лихачева для сетки на основе сетки.

В этом алгоритме используются двойные клавиши. Это левая и правая часть. Как правильно сравнить эти ключи для сортировки в очереди приоритетов? Стоит ли сначала сравнивать левые части и сравнивать правые, только если они равны? Или я должен выбрать другой путь?

Answer 1

Вы должны сравнить левые части 1-й (f-значения). Только если они равны, вы должны сравнивать вторую часть, которая в основном представляет собой g-значения. Это лексикографическое сравнение. Эта и другие концепции, используемые в D * lite, объясняются в видео-лекции mit opencourseware на youtube: https://youtu.be/_4u9W1xOuts

Answer 2

Да, я нашел ответ здесь: https://www.cs.cmu.edu/~maxim/files/aij04.pdf

А здесь: https://en.wikipedia.org/wiki/Lifelong_Planning_A*#Priority_Queue