统一成本解中的算法问题

0 投票
1 回答
1400 浏览
提问于 2025-04-16 01:40

我正在做一个叫做统一代价搜索的算法。不过,我得到的结果比实际的要大一点。扩展的节点数量也比实际的要多。

我使用的算法是这样的:

首先获取初始节点,然后把它放进优先队列。这个优先队列会根据成本自动排列节点,成本低的节点会排在前面。

接着使用一个循环,直到队列为空为止。

从队列中取出一个节点,检查它是否是目标状态。如果不是,再检查它是否在已访问列表中。已访问列表是一个集合,里面存放的是所有已经扩展过的节点。如果这个节点不在已访问列表中,就获取它的后继节点以及相应的成本和操作。

计算到这个节点的成本。

如果后继节点的成本比父节点的成本还要大,就把它加入队列,并检查这个后继节点是否在父节点目录中。如果不在,就把它设为父节点,这样我们可以回溯路径。

我的算法是对的吗?还是说我需要检查其他的东西?

1 个回答

2

看起来你正在用优先队列实现一个迪杰斯特拉算法。不过因为你的成本是一样的,所以其实用广度优先搜索就足够了。

撰写回答