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

Question

我有一个带有多个起点和终点（例如3组）的方阵（例如5x5）：

最终目标是找到每对点的路径，以使路径之间不会交叉。在这个简单的示例中，可能有多个解决方案，但是在现实生活中，一旦开始添加更多对点，就会有一个独特的解决方案可以填满整个矩阵，因此不会剩下任何正方形。

但是，我的第一步是为每对点找到从一个起点到其相应终点的所有可能路径，这样我就可以丢弃所有路径相交的路径。如果可能的话，我希望不必借助图论来执行此操作，因为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

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

[如果我分别对待每对，并将其他占用的正方形视为“禁区”，则每种情况下我将有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对起点/终点的10x10网格，因此是82个节点。

Answer 1

邻接矩阵是一个矩阵，如果节点adj(n,:)与所有其他元素相邻，元素n将使用布尔值告诉您。

尽管您从良好的起点开始，但与起点稍有不同。

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

要构建此矩阵，您只需要知道哪些节点是相邻的，但是对于一个多维数据集，找到一个方程式即可轻松地找到其相邻节点（或者只需检查node_ids(ind2sub(your_node)+[0 1])和其他组合即可]