最短路径算法

Question

我正在尝试在我的代码中实现最短路径算法，但我不知道该怎么做。假设您有一个包含多个线段的 (x,y) 坐标的矩阵。假设每条线段都有一个与之关联的分数，该分数表示 "valuable" 该线段对设计的影响。

如果将此信息放入矩阵中，则行的格式可以如下所示：

X 开始，Y 开始，X 结束，Y 结束，得分

现在，假设上面的矩阵中没有提供连接信息，即你不知道基于矩阵的一条线与另一条线的关系。基于上面的矩阵，我想找到产生最高分数的元素路径（在我的程序中它是最低分数，但这是语义）。然而，要注意的是每条路径必须是连续的，连接线段之间没有跳跃。有谁知道如何编码？我在下面有一段代码，其中计算并存储了每个元素的分数（在矩阵 ElementMap 中），但是一旦有了 ElementMap，我不知道如何形成最佳路径。

谢谢

for i = 1:Count2
 for j = 1:length(ElementMap)

    xStart = ElementMap(j,1);
    yStart = ElementMap(j,2);
    xEnd = ElementMap(j,3);
    yEnd = ElementMap(j,4);

    Score = 0;
    if NodeMap(2*(i-1)+1) == ElementMap(j,1) && ElementMap(j,5) ~= 1

        for m = 1:length(ThetaIncident)

            [Point] = RayScore(xStart,yStart,xEnd,yEnd,ThetaIncident(m),OvenGlassXrange);

            Score = Score - Point;
        end
        ElementMap(j,5) = 1;  % 1 will indicate Element has been analyzed
    end
    ElementMap(j,6) = ElementMap(j,6) + Score;
 end
end

Answer 1

在我看来你是从这样一个数组开始的：

+---------+---------+-------+-------+-------+
| Start X | Start Y | End X | End Y | Score |
+---------+---------+-------+-------+-------+
| 1       | 3       | 2     | 4     | 23    |
+---------+---------+-------+-------+-------+
| 1       | 3       | 7     | -3    | 87    |
+---------+---------+-------+-------+-------+
| 7       | -3      | 5     | 5     | 12    |
+---------+---------+-------+-------+-------+

在您着手寻找最短路径之前，我建议您编写代码来做一些准备工作。我建议您首先创建一个 new/separate 数组来表示作为线段端点的 x-y- 坐标对。

使用我上面给出的相同示例数据，我们有：

+---+----+
| X |  Y |
+---+----+
| 1 | 3  |
+---+----+
| 2 | 4  |
+---+----+
| 7 | -3 |
+---+----+
| 5 | 5  |
+---+----+

接下来，随便name/index这几个点

+---------+---+----+
| pointID | X |  Y |
+---------+---+----+
| 1       | 1 | 3  |
+---------+---+----+
| 2       | 2 | 4  |
+---------+---+----+
| 3       | 7 | -3 |
+---------+---+----+
| 4       | 5 | 5  |
+---------+---+----+

您可以根据 pointID 而不是 x 和 y 坐标来考虑原始 table。没有必要写代码来做这件事，但是可以用一个小例子手工完成，以帮助构思。

+--------------+------------+-------+
| StartPointID | EndPointID | Score |    
+--------------+------------+-------+
| 1            | 2          |  23   |
+--------------+------------+-------+
| 1            | 3          |  87   |
+--------------+------------+-------+
| 3            | 4          |  12   |
+--------------+------------+-------+

现在，构造一个矩阵，其中第 i 行第 j 列中的条目是与线段相关联的分数，该线段从索引为 i 的点开始，到索引为 j 的点结束。

    ╔═════╦═════╦═════╦═════╗
    ║ 1   ║ 2   ║ 3   ║ 4   ║
╔═══╬═════╬═════╬═════╬═════╣
║ 1 ║ N/A | 23  | 87  | N/A |
╠═══╬-----+-----+-----+-----+
║ 2 ║ 23  | N/A | N/A | N/A |
╠═══╬-----+-----+-----+-----+
║ 3 ║ 87  | N/A | N/A | 12  |
╠═══╬-----+-----+-----+-----+
║ 4 ║ N/A | N/A | 12  | N/A |
╚═══╩-----+-----+-----+-----+

有了最后一个数组（顺便说一句，对于边加权图，这称为 adjacency matrix), you are now ready to find a shortest path。

最短路径算法

Shortest Path Algorithm

algorithm

matlab

shortest-path