平面图中任意两点之间的最优路径
Optimal route between any two points in a planar graph
我正在寻找一种算法，该算法可以找到平面图（平面图）中任意两点之间的最佳路线。我附上了图片来说明我想要实现的目标。在图像中，目标是将空心点连接到任何其他点并同时最小化交叉点（在这种情况下没有交叉点）。
在上图中，假设我还想将蓝色连接到灰色，将紫色连接到绿色，这会引入交叉点，这是我想要避免的。
所以，我只想要一个算法来找到平面图中任意两点之间的最佳路线，我所说的最佳路线是指交叉点最少的最短路线。如果有人能指出我开始的正确方向，我将不胜感激。
您正在寻找的东西已经在 VLSI 电路设计中进行了大量研究，称为路由（在这种情况下）。
这不是一个小答案，因为有许多基于设计要求的考虑因素。可以找到一些起点 here.
我正在寻找一种算法，该算法可以找到平面图（平面图）中任意两点之间的最佳路线。我附上了图片来说明我想要实现的目标。在图像中，目标是将空心点连接到任何其他点并同时最小化交叉点（在这种情况下没有交叉点）。
在上图中，假设我还想将蓝色连接到灰色，将紫色连接到绿色，这会引入交叉点，这是我想要避免的。
所以，我只想要一个算法来找到平面图中任意两点之间的最佳路线，我所说的最佳路线是指交叉点最少的最短路线。如果有人能指出我开始的正确方向，我将不胜感激。
您正在寻找的东西已经在 VLSI 电路设计中进行了大量研究，称为路由（在这种情况下）。
这不是一个小答案，因为有许多基于设计要求的考虑因素。可以找到一些起点 here.