在我们的项目中，我们必须可视化网络 . 该网络由多个设备组成，每个设备都有多个端口 . 设备可视化为包含彼此相邻排列的每个端口的盒子 . 每个端口都可以链接到任何其他设备上的任何其他端口 . 每个链接都必须以不会在任何设备上运行的方式进行路由，并且如果可能的话，它不会跨越其他链接 .
目前，我们使用A *寻路来查找每个链路的路由 . 设备占用的网格节点具有非常高的权重 . 完成一个链接的路径查找后，我们为该链接的路径占用的每个网格节点添加一个较低的权重 .
这种类型的工作，但路径查找的顺序极大地影响了结果，并且通常这导致非常次优的路径 . 这是一个常见的错误，即在同一方向上运行的多条路径往往比必要的更频繁地穿越 .
这是一个例子：A连接到C，B连接到D.
A|
B++
||
++---C
+---D
这里发生的是首先运行从A到C的链路寻路 . 路径从A开始，直线向下直到它与C处于同一高度，然后向右转，直到它到达C.
现在，路径寻找从B到D的链路运行 . 它首先必须跳过第一个链接才能到达可以移动的空闲空间而不会受到惩罚 . 然后它再次转向并再次跳过第一条路径，然后它可以达到与D相同的高度，在那里它向右转到D .
还有一种解决方案根本不需要任何跳转 .
现在我的问题是：是否有任何算法允许在同时搜索多个路径时找到最佳（或至少是一个好的）解决方案？用于查找竞争路径的非贪心算法？
我不关心实现或库，我只是在寻找一个合适的算法 .
编辑：我忘了一件重要的事情：这应该只影响边缘的定位 . 设备的位置以及端口的位置由用户设置，因此不允许通过算法修改 .