获取从方阵的一个点到另一个有障碍物的所有可能路径

Question

我有一个方阵（比如 5x5），有多个起点和终点（比如 3 组）：

最终目标是为每对点找到路径，以便没有路径与另一点交叉。在那个简单的例子中，可能有不止一个解，但在现实生活中，一旦你开始添加更多的点对，就会有一个唯一的解来填充整个矩阵，以至于没有一个方格是空的。

然而，我的第一步是为每对点找到从一个起点到其相应终点的所有可能路径，这样我就可以丢弃所有路径与另一条路径相交的路径。如果可能的话，我想这样做而不必求助于图论，因为 1) 我对此一无所知，并且 2) 它似乎没有在 Octave 中实现。

我做了相当多的研究，从 GitHub 中找到了以下函数，它几乎完全符合我想要实现的目标，但确实依赖于图论：

function pth = pathbetweennodes(adj, src, snk, verbose)
%PATHBETWEENNODES Return all paths between two nodes of a graph
%
% pth = pathbetweennodes(adj, src, snk)
% pth = pathbetweennodes(adj, src, snk, vflag)
%
%
% This function returns all simple paths (i.e. no cycles) between two nodes
% in a graph.  Not sure this is the most efficient algorithm, but it seems
% to work quickly for small graphs, and isn't too terrible for graphs with
% ~50 nodes.
%
% Input variables:
%
%   adj:    adjacency matrix
%
%   src:    index of starting node
%
%   snk:    index of target node
%
%   vflag:  logical scalar for verbose mode.  If true, prints paths to
%           screen as it traverses them (can be useful for larger,
%           time-consuming graphs). [false]
%
% Output variables:
%
%   pth:    cell array, with each cell holding the indices of a unique path
%           of nodes from src to snk.

% Copyright 2014 Kelly Kearney

我的问题是尝试计算邻接矩阵。不熟悉图论，我有点理解邻接矩阵的概念，但对实际生成所述矩阵一头雾水。

如果我分别处理每一对并将其他占用的方块视为 "off-limits"，我将为每个场景有 25 - 4 = 21 个节点，并且在纸上我可以手动写下边缘，但我不知道如何编码？有人可以帮忙吗？

如果我们使用上面的示例并按行对节点进行排序，考虑到蓝色点对，我们会得到类似这样的结果，目标是从节点 1 到节点 17（反之亦然，有不涉及方向性）：

 1  2  3  4  5 
    6     7  8
 9 10 11 12 13
14 15 16 17
18    19 20 21

边缘是有效的移动（垂直或水平，没有对角线）所以像：

1 - 2
2 - 1
2 - 3
2 - 6
3 - 2
3 - 4
etc...

你如何从这里转到一些代码？

当然，如果有更好的方法来解决这个问题，我愿意接受任何建议。就问题的规模而言，它可以达到具有 10 对 start/end 点的 10x10 网格，因此有 82 个节点。

Answer 1

邻接矩阵是一个矩阵，其中元素 adj(n,:) 会用布尔值（或路径长度）告诉您节点 n 是否与所有其他元素相邻。例如在你的情况下 adj(14,:) 除了 adj(14,9)、adj(14,15) 和 adj(14,18).

之外都是零

不过，您的起点不错，但略有偏离。没有连接的节点仍然是您系统中的一个节点。这会让你的生活更轻松！

您的初始矩阵只是 node_ids=1:25，或者如果您想要 node_ids=reshape(1:25,5,5)。您不想访问的节点可以描述为不与任何事物相邻的节点。因此，对此进行编程的方法是首先为 5x5（或任何大小）网格创建邻接矩阵，然后删除所有不需要的路径，例如adj(:,6)=0（对于所有节点，确保它们不与节点 6 相邻（注意，节点是您示例中的第一个红色圆圈））。

要构建此矩阵，您只需要知道哪些节点是相邻的，但对于立方体，找到一个方程来为您提供其相邻节点很容易（或者只需检查 node_ids(ind2sub(your_node)+[0 1]) 和其他组合）

获取从方阵的一个点到另一个有障碍物的所有可能路径

Get all possible paths from one point of a square matrix to another with obstacles

matrix

octave

graph-theory

adjacency-matrix