0

我正在为个人项目处理图像,但我坚持了一步(而且这是一个相对容易的步骤)顺便说一句,我的问题与图像无关。

我正在计算图像上每个像素的 int 值。我想找到像素(节点)之间成本最低的路径。实际上我有一个 A* 算法的工作实现。但我不想使用它,因为我不想将“地图”限制为只能通过或不能通过的节点。我希望每个节点都可以通过但要付出代价。有些节点的通过成本很高,有些则不会。但是不会有不能通过的节点。

我认为我不需要提供任何代码,因为它是项目中非常孤立的部分。所以我不想操纵任何人。但基本上我有一个包含节点列表的地图对象。并且节点有 id, x,y 位置。成本、邻居(顶部、底部、左右像素)和节点参考,以了解我从哪里来到这里等。

我希望我能表达出与 Dijkstra 最短路径算法的区别。我该如何相应地修改它?或者任何人都可以推荐另一种方式来做到这一点?

4

1 回答 1

2

我想我看到了问题......“有些节点的通过成本很高,有些则不会。” 这不是算法的真正工作方式,您应该将问题转化为节点(无成本)和边(有成本)。然后应该很容易使用 A*、Dijkstra 或任何其他寻路算法。

在您的情况下,每个像素都是一个节点/顶点。每个像素都有 4 个边缘(边界处除外)。边缘的成本将是目标像素的 int 值。

此外,您不应该在节点中保留节点引用,这是算法工作来跟踪它的来源。

希望这可以帮助。

于 2012-04-18T20:57:56.720 回答