在二维网格表面寻找最短路径的困难

Question

三天前我提出了这个问题，由于没有包含足够的信息而被贡献者烧了。对此我感到很抱歉。

我有一个2D矩阵，每个数组位置与河道水深相关，我希望应用Dijkstra或类似的“最小代价路径”算法来找到建造跨越水域所需的最少混凝土量。

将数据格式化成清晰版本需要一些时间，因此我学会了一些基本的Matlab技能。我已经除去了大部分陆地，现在海岸线标准化为某个值，我的计划是使用一个循环移动到“西”岸的每个“像素”，并对其运行最小代价算法以找到最接近的“东”岸，并通过整个网格移动，最终找到最小代价路径。

这是我的问题，将数据拟合到任何算法。不幸的是，我被选项和不同的格式所压倒，因为其他示例是针对其他用例的。

我另一个考虑因素是当计算出最短代价路径时，它将是一条崎岖不平的线，这不适合建造桥梁，因此如果可能的话，我需要限制路径中的弯曲半径，但我不知道如何去做。

河道图片：

任何关于方法的建议都将是有益的，我只需要知道是否有人知道应该适用的方法，然后我将花时间学习如何拟合数据。

- drcross

---

你之前问过这个问题吗？如果是的话，正确的做法是编辑你的问题并包含这些信息。 - Nissa

所以你想在网格中找到最短路径。但这有点违背问题的本质：你不需要最短路径，也不需要在网格中找到它，你只是在将数据离散化到网格上。这里的大问题是要设计一个“成本”函数，一个给定路径后，会给出混凝土量的函数。我们无法为您找到这个函数，因为这不是一个编程问题，而是一个研究问题。请记住，Stackoverflow是用于编程问题，而不是关于您想要使用编程解决的问题。 - Ander Biguri

某位用户，我会更新旧问题。Ander我可以研究混凝土的数量，显然我不是在寻求关于这方面的帮助，我是在寻找如何从一岸到另一岸生成最少成本路径的方法。这似乎是一个非常基本的例子，我很惊讶在所有文档和论坛的例子中从未提到过这种情况。 - drcross

啊哈！因为你要么提供了太多信息但没有清晰地表达你的需求，要么这是一个非常困难的例子。机器学习算法被创建来解决这个问题，数学家们研究凸和非凸情况下算法的收敛性。这不是一个简单的例子。除非你只想要两点之间的最短路径，那就是一条直线。 - Ander Biguri

@anderbiguri，你的回答在这种情况下并没有帮助，只会让我更加沮丧，试图进入这个领域。 - drcross

@drcross 欢迎来到工程领域，这里问题令人沮丧，你需要自己研究解决！ - Ander Biguri

Answer 1

您可以这样将Dijkstra算法应用于您的问题：

1. 您想要连接的两个“干燥”区域对应于值为0的矩阵条目；其他单元格具有指定深度（或填充此位置的混凝土成本）的正值

2. 您的边缘是矩阵中相邻单元格的连接。 （可以是4-或8-邻域。）边缘的权重是连接单元格的值的算术平均值。

3. 然后，您在一个“干燥”区域中设置起点，在另一个“干燥”区域中设置终点，应用Dijkstra算法。

最便宜的路径将连接两个值为0的单元格，其权重将对应于访问的单元格成本之和。 （每个单元格重量的一半来自前往该单元格的边缘，另一半来自离开该单元格的边缘。）

这样，您将获得一条可能非常弯曲的路径，通向水上，这可能是建造廉价桥梁的有用提示。

使用 A* 算法可以加速计算。因此，需要为每个单元格确定到达另一侧的剩余成本下限。这种下限可以通过检查围绕一个点的“同心圆”来计算，只要圆环不包含另一侧的 0 单元格。然后，每个圆环的最小单元值之和就是剩余成本的下限。

- coproc

Answer 2

另一种方法是强调您需要一个非锯齿形状的桥梁的约束条件，可以使用蒙特卡罗、模拟退火或遗传算法。初始的“桥梁”由两个随机选择的端点（峡谷的每一侧各一个）之间的简单样条曲线和峡谷中少量随机选择的中间点组成。最终您将得到一个物理上“真实”的桥梁和一个合理优化的混凝土成本。

- Penguino