光栅路径遵循算法

Question

我有一个栅格网格的值看起来像下面的图像(白色是高值,黑色背景值是零).

我正在尝试编写某种路径跟踪代码,从其中一行的末尾开始并跟踪到另一端,通过最高可能值(即,选择在行中的像素越白)更好)但仍然走到另一端.

我已经在这方面苦苦挣扎了一段时间,似乎无法得到任何我尝试工作的东西.所以我想知道,是否已针对此类问题开发了通用算法？我已经做了很多搜索,但大多数路径算法似乎都设计用于矢量/网络,而不是像这样的栅格网格.

有任何想法吗？

Answer 1

最简单的想法可能是使用A*算法,其中每个像素是一个节点,节点的成本是像素黑暗.

更新:找到一个很好的教程.

Answer 2

我认为你不需要遗传算法或任何荒谬的东西；好的老式递归和动态编程就足够了。我最初认为，您应该能够通过广度优先搜索来实现您的目标。从起点开始，您访问分数大于路径值的所有邻居——所有单元格都从无穷大开始，黑色单元格的成本将是无穷大，这些是您可以修剪掉的路径）。到达目的地后，如果可以到达，您应该能够原路返回以找到路径。它很贪婪，但如果你的路径像这些一样表现良好，那就应该没问题。

对于灰度较多且曲折的路径，将光栅图像转换为图形可能是一个好主意，边缘权重是邻居的灰度值（或灰度值的差异，具体取决于这是什么）数据实际上意味着）。因此，您应该能够根据该解释使用任何最短路径算法。