D* Lite算法中双键的优先级队列比较排序方法咨询

刚好我对D*-Lite里的优先级队列逻辑摸得很透，咱们直接说核心：

D*-Lite里的双键（通常记为(k₁, k₂)）的比较排序规则是先比左半部分k₁，仅当k₁相等时再比较右半部分k₂，而且都是数值越小的优先级越高。

为什么要这么设计？ #

先明确两个键的含义：

• k₁ 是节点的启发式优先级核心，等于 min(g(s), rhs(s)) + h(s, s_goal)，其中g是当前已知的最短路径代价，rhs是从节点到终点的估计代价，h是启发式函数。它决定了节点在队列中的层级优先级，k₁越小说明这个节点越接近最优路径的候选。
• k₂ 是辅助排序键，等于 min(g(s), rhs(s))，作用是当多个节点k₁相同时，区分它们的处理顺序——k₂更小的节点会被优先处理，这能保证算法的正确性，避免出现路径更新的遗漏。

论文里的明确依据 #

Koenig和Likhachev在2002年的原文里直接规定了这个排序逻辑：

优先级队列中的元素按照键值(k₁, k₂)升序排列，即先比较k₁，k₁小的优先级更高；若k₁相等，则比较k₂，k₂小的优先级更高。

代码实现示例（以Python为例） #

因为Python的元组默认比较逻辑就是先比第一个元素，再比第二个，所以直接把双键作为元组存入优先队列就行：

import heapq

# 假设已经计算好节点的k1和k2
priority_queue = []
heapq.heappush(priority_queue, (k1, k2, node))

# 取出优先级最高的元素
current_k1, current_k2, current_node = heapq.heappop(priority_queue)

这样队列会自动按照正确的规则排序，完全符合论文要求。

内容的提问来源于stack exchange，提问作者Robotex