我有一个类似于下图的栅格值(白色是高值,黑色背景值为零)。
我正在尝试编写某种路径跟踪代码,从其中一行的末尾开始并跟踪到另一端,通过可能的最高值(即,选择在行中的像素越白更好)但仍然到达另一端。
我已经为此苦苦挣扎了一段时间,似乎无法得到任何我尝试工作的东西。所以我想知道,是否已经针对此类问题开发了通用算法?我做了很多搜索,但大多数路径算法似乎都设计用于矢量/网络,而不是像这样的栅格网格。
有任何想法吗?
一种方法:
需要进行一些调整才能使其正常工作,但可以这样做。另一种变体是勾勒白色部分,如果它们比 1 或 2 或 3 个像素宽,然后合并双线。
我认为您不需要遗传算法或任何可笑的东西;好的老式递归和动态编程就足够了。我最初的想法是,您应该能够通过进行广度优先搜索来实现您的目标。从您的起点开始,您访问所有得分高于路径值的邻居——所有单元格从无穷大开始,黑色单元格的成本将是无穷大,这些是您可以修剪的路径)。一旦到达目的地,如果可以到达,您应该能够回溯以找到路径。这是贪婪的,但如果你的路径表现得像这样,那应该没问题。
对于具有更多灰色和曲折的路径,将光栅图像转换为图形可能是个好主意,边缘权重是邻居的灰度值(或灰度值的差异,取决于这个数据实际上意味着)。因此,您应该能够使用任何基于该解释的最短路径算法。
如果您正在大规模这样做或进行研究,您可能会尝试使用http://en.wikipedia.org/wiki/Ant_colony_optimization,但如果您这样做是为了赚钱,只需选择类似洪水填充http://en 的东西。 wikipedia.org/wiki/Flood_fill