基于坐标系统的广度优先搜索
breadth-first search in coordinate based system
我不是一个经验丰富的程序员（编程语言MATLAB），因此对高级算法几乎一无所知。其中之一是广度优先搜索。我理解这个概念，但将它应用到我的问题中对我来说很难。
我的问题：
我将相同大小的磁盘随机放置在一个正方形中，当它们是一个连接的网络时，会将磁盘的坐标放入单独的矩阵中。为了清晰起见，我对它们进行了着色（见图）。现在，我必须找到从左到右跨越网络的从左到右的最短路径，并希望根据坐标执行此操作。磁盘必须接触才能相互连接。如果它们不接触，它们就无法形成路径。
这就是我目前拥有的：
我在第 1 列和第 2 列中有一个坐标为 x 和坐标为 y 的矩阵，每一行代表一个磁盘（为方便起见，我们只获取所有连接磁盘的坐标，不包括连接时不从左到右跨越的那些).
圆盘的直径是已知的 (0.2)。
我们可以很容易地识别出哪些圆盘在正方形的左边界上，哪些圆盘在正方形的右边界上。这些代表可能的起始坐标和可能的目标坐标。
% Coordinates of group of disks, where the group connects from left to right.
0.0159 0.1385
0.0172 0.2194
0.0179 0.4246
0.0231 0.0486
0.0488 0.1392
0.0709 0.2109
0.0813 0.0595
0.0856 0.3530
0.1119 0.3756
0.1275 0.2530
0.1585 0.4751
0.1702 0.2926
0.1908 0.3828
0.1961 0.3277
0.2427 0.4001
0.2492 0.4799
0.2734 0.4788
0.3232 0.3547
0.3399 0.3275
0.3789 0.3716
0.4117 0.3474
0.4579 0.3961
0.4670 0.3394
0.4797 0.3279
0.4853 0.4786
0.3495 0.4455
0.4796 0.2736
0.0693 0.0746
0.1288 0.4204
0.1271 0.4071
0.1218 0.4646
0.1255 0.3080
0.4154 0.2926
磁盘的位置和连接磁盘的颜色。图像非常示意性，在更大的区域中应该有更多的磁盘（保持相同大小的磁盘）。
我的策略是设置广度优先搜索，将起始坐标作为正方形左侧的一个圆盘（可以是任何圆盘）。目标将是找到到广场右侧的最短路径。
据我了解，我想选择一个起始坐标并检查所有磁盘是否在我的起始坐标的直径距离（磁盘的中点到中点）内。如果它们在我的起始坐标范围内，我想将它们放在 'queue' 中（MATLAB 本身不支持？但让我们自己设置一个）。然后，下一步是取足够近的第一个磁盘并对这个磁盘执行相同的操作。我可以做到这一点，但是一旦我必须做我第一个磁盘中的第二个磁盘，我就迷失了 and/or 我应该采用什么数据结构以及如何保存它找到的 'path' .这意味着我可以找到一条路径，但不是所有路径，因此也不是最短路径。
感谢您的帮助！也许是一些我还没有看过的文档，或者是一个非常可比的例子。
此致，
If they are within range of my starting coordinate I want to place
them in a 'queue'
在将其添加到队列之前，您要确保此磁盘之前未被处理（放入队列）。每个磁盘应该只处理一次，所以你要确保“邻居”磁盘之前没有被处理过，然后将其标记为已处理并将其添加到队列中。
the next step is to take the first disk which was close enough and do
the same for this one.
实际上，下一个要处理的光盘就是排在队列首位的光盘。
继续这样做，直到达到目标/停止标准。
how to save the 'path' which it is finding
有几种方法可以做到这一点。一个简单的方法是为每个磁盘维护一个“来自”值。该值指向磁盘的“父级”。
由于每个磁盘被处理一次（最多），它将有一个“来自”值或 none。
当到达目标时，可以从目标的“来自”值开始重建路径。
此问题现已解决！
我解决这个问题的方法与我的问题中已经提出的方法很接近，但也得到了一些评论的帮助。
坐标之间的距离可以放入矩阵中。让我们看看坐标（磁盘）1 和坐标（磁盘 3）。这意味着我们将位于元素 (1,3) 和 (3,1) 处。如果磁盘在接触距离内，这两个元素将指示 1，否则指示 0。对所有磁盘都这样做，并创建邻接矩阵。
我用内置函数G = Graph(adjacency matrix)创建了一个'graph'我们可以创建一个无向图。然后使用内置函数 [path, distance of path] = shortestpath(G,s,t)，其中 G 是图形，s 和 t 是起始磁盘（在本例中，用整数表示），可以找到从磁盘 s 到 t 的最短路径。
但是我们必须注意一件事，那就是表示磁盘之间的实际距离。如果我们看一下 G，我们实际上可以看到它包含两个对象。一个代表节点，另一个代表边。边缘对于基于坐标的距离至关重要，因为我们可以将边缘的 'weight' 设置为两个磁盘之间的距离。这可以简单地通过遍历节点并计算相邻节点之间的距离并将它们插入权重（G.Edges.Weight(i) = distance between the respective nodes）来完成。
如何找到从左到右的最佳路径？我遍历所有起始磁盘（定义为接触正方形的左侧）并找到所有接触正方形右侧的磁盘的最短路径。保存路径的距离可以找到实际的最短路径。
为了给你一个可以实现的例子，下面的视频显示了从每个起始磁盘可以找到的路径，最后一帧显示了最短路径。 Video of path finding.最短路径我也附在这里：
Shortest path left to right.
如果你有任何关于具体问题想问我的问题，请告诉我。
我不是一个经验丰富的程序员（编程语言MATLAB），因此对高级算法几乎一无所知。其中之一是广度优先搜索。我理解这个概念，但将它应用到我的问题中对我来说很难。
我的问题： 我将相同大小的磁盘随机放置在一个正方形中，当它们是一个连接的网络时，会将磁盘的坐标放入单独的矩阵中。为了清晰起见，我对它们进行了着色（见图）。现在，我必须找到从左到右跨越网络的从左到右的最短路径，并希望根据坐标执行此操作。磁盘必须接触才能相互连接。如果它们不接触，它们就无法形成路径。
这就是我目前拥有的： 我在第 1 列和第 2 列中有一个坐标为 x 和坐标为 y 的矩阵，每一行代表一个磁盘（为方便起见，我们只获取所有连接磁盘的坐标，不包括连接时不从左到右跨越的那些). 圆盘的直径是已知的 (0.2)。 我们可以很容易地识别出哪些圆盘在正方形的左边界上，哪些圆盘在正方形的右边界上。这些代表可能的起始坐标和可能的目标坐标。
% Coordinates of group of disks, where the group connects from left to right.
0.0159 0.1385
0.0172 0.2194
0.0179 0.4246
0.0231 0.0486
0.0488 0.1392
0.0709 0.2109
0.0813 0.0595
0.0856 0.3530
0.1119 0.3756
0.1275 0.2530
0.1585 0.4751
0.1702 0.2926
0.1908 0.3828
0.1961 0.3277
0.2427 0.4001
0.2492 0.4799
0.2734 0.4788
0.3232 0.3547
0.3399 0.3275
0.3789 0.3716
0.4117 0.3474
0.4579 0.3961
0.4670 0.3394
0.4797 0.3279
0.4853 0.4786
0.3495 0.4455
0.4796 0.2736
0.0693 0.0746
0.1288 0.4204
0.1271 0.4071
0.1218 0.4646
0.1255 0.3080
0.4154 0.2926
磁盘的位置和连接磁盘的颜色。图像非常示意性，在更大的区域中应该有更多的磁盘（保持相同大小的磁盘）。
我的策略是设置广度优先搜索，将起始坐标作为正方形左侧的一个圆盘（可以是任何圆盘）。目标将是找到到广场右侧的最短路径。
据我了解，我想选择一个起始坐标并检查所有磁盘是否在我的起始坐标的直径距离（磁盘的中点到中点）内。如果它们在我的起始坐标范围内，我想将它们放在 'queue' 中（MATLAB 本身不支持？但让我们自己设置一个）。然后，下一步是取足够近的第一个磁盘并对这个磁盘执行相同的操作。我可以做到这一点，但是一旦我必须做我第一个磁盘中的第二个磁盘，我就迷失了 and/or 我应该采用什么数据结构以及如何保存它找到的 'path' .这意味着我可以找到一条路径，但不是所有路径，因此也不是最短路径。
感谢您的帮助！也许是一些我还没有看过的文档，或者是一个非常可比的例子。
此致，
If they are within range of my starting coordinate I want to place them in a 'queue'
在将其添加到队列之前，您要确保此磁盘之前未被处理（放入队列）。每个磁盘应该只处理一次，所以你要确保“邻居”磁盘之前没有被处理过，然后将其标记为已处理并将其添加到队列中。
the next step is to take the first disk which was close enough and do the same for this one.
实际上，下一个要处理的光盘就是排在队列首位的光盘。 继续这样做，直到达到目标/停止标准。
how to save the 'path' which it is finding
有几种方法可以做到这一点。一个简单的方法是为每个磁盘维护一个“来自”值。该值指向磁盘的“父级”。
由于每个磁盘被处理一次（最多），它将有一个“来自”值或 none。
当到达目标时，可以从目标的“来自”值开始重建路径。
此问题现已解决！
我解决这个问题的方法与我的问题中已经提出的方法很接近，但也得到了一些评论的帮助。
坐标之间的距离可以放入矩阵中。让我们看看坐标（磁盘）1 和坐标（磁盘 3）。这意味着我们将位于元素 (1,3) 和 (3,1) 处。如果磁盘在接触距离内，这两个元素将指示 1，否则指示 0。对所有磁盘都这样做，并创建邻接矩阵。
我用内置函数G = Graph(adjacency matrix)创建了一个'graph'我们可以创建一个无向图。然后使用内置函数 [path, distance of path] = shortestpath(G,s,t)，其中 G 是图形，s 和 t 是起始磁盘（在本例中，用整数表示），可以找到从磁盘 s 到 t 的最短路径。
但是我们必须注意一件事，那就是表示磁盘之间的实际距离。如果我们看一下 G，我们实际上可以看到它包含两个对象。一个代表节点，另一个代表边。边缘对于基于坐标的距离至关重要，因为我们可以将边缘的 'weight' 设置为两个磁盘之间的距离。这可以简单地通过遍历节点并计算相邻节点之间的距离并将它们插入权重（G.Edges.Weight(i) = distance between the respective nodes）来完成。
如何找到从左到右的最佳路径？我遍历所有起始磁盘（定义为接触正方形的左侧）并找到所有接触正方形右侧的磁盘的最短路径。保存路径的距离可以找到实际的最短路径。
为了给你一个可以实现的例子，下面的视频显示了从每个起始磁盘可以找到的路径，最后一帧显示了最短路径。 Video of path finding.最短路径我也附在这里：
Shortest path left to right.
如果你有任何关于具体问题想问我的问题，请告诉我。