问题标签 [shortest-path]

我有一系列图形坐标，我需要找到通过它们的最短单向路径。我没有预定的开始/结束，但每个点只能触摸一次，不需要返回最佳原点。

我尝试了几种 TSP 方法，但它们似乎都是基于最后返回原点，这在这种情况下会产生非常低效的结果。

例子

1, 13
3, 0
3, 7
2, 21
2, 11
3, 12
1, 19
3, 6

将解决

3, 0
3, 6
3, 7
3, 12
2, 11
1, 13
1, 19
2, 21

笔记：

是的，我尝试了搜索功能，有一个基本相同的问题 算法：所有点之间的最短路径， 但唯一真正的答案是 TSP，再一次，闭路对此效率低下。

它不需要 100% 准确，我已经有一个排列方法，但它太慢了，我需要处理至少 ~25-30 点，用一个好的近似值来解决对我来说很有效

提前致谢。

编辑澄清一下，TSP 倾向于解决 img #1，我想要的结果是 img #2
img 3 是通过 TSP 解决的上述示例，而 img #4 是所需的（x 坐标向后移动 -.5 以提高可见性

） more for good measure #1 = TSP, #2 = desired

基本上我想要连接 n 点的最短链，使用最有效的起点和终点

我一直在制作一个系统，该系统可以接收有关驾驶员、潜在乘客及其位置的数据，并尝试在某些限制条件下优化可以与驾驶员一起乘坐电梯的乘客数量。我正在使用 python-constraint 模块，决策变量是这样表示的：

因此，当我打印 p 的值以及 driver_set 和passenger_set 时，我得到以下输出（给定我提供的测试数据）：

因此，有 3 名乘客和 2 名司机：变量 (2,0) 表示乘客 2 在 0 号车内，依此类推。我添加了以下约束，以确保没有乘客乘坐超过一辆车，并且驾驶员的人数不能超过座位：

这行得通 - 生成的所有解决方案都满足这些约束。但是，我现在想添加一些限制条件，即任何解决方案都不应该让车手行驶超过一定距离。我有一个函数，它接收一个司机（与 driver_set 中的实体格式相同）并计算司机接所有乘客的最短距离。我试图添加这样的约束：

这给出了以下错误：

我不确定应该如何为 python-constraint 定义这个约束：每个驱动程序只有一个最短距离值。我应该为此使用 lambda 函数吗？

编辑

我尝试实现它的 lambda 版本，但是我似乎没有降低 lambda 语法。我到处寻找，但似乎找不到这有什么问题。基本上我替换了最后一段代码（添加约束以限制 getRouteDistance(driver) 的值），而是把它：

但后来我得到了这个错误（注意它不是从我编辑的行中调用的，它来自之后的问题.getSolutions（））：

有没有其他人试图做这样的事情？我不明白为什么约束库不允许这样做。

我知道在 NP-HARD 中存在以下问题：给定一个简单的图 G=(V,E)，V 中有两个顶点 v，v'，一个整数 B，以及一个非负长度函数 len：E-> Z+ ，是否有一条从 v 到 v' 长度小于 B的简单路径？

我的问题是：在与以前相同的条件下，如果我们有兴趣在 G 中找到从顶点 v 到 v' 的最长但不一定简单的路径，那么问题仍然存在于 NP-HARD 中吗？

注意：我试图减少汉密尔顿路径，但我仍然无法证明 NP 是否存在问题，可简化为我提到的这个问题。我也查过Garey & Johnson，但我什么也没找到。

我想要一点提示来证明这个问题是否是 NP-HARD。提前致谢！

这是我从这里的站点获得的代码，我想知道 A* 的这种实现是否正确。我已经查看了它并将其与维基百科页面进行比较，它似乎是有效的。我问的原因是因为在该站点中它说此代码中仍然存在错误，我尝试找到它但找不到任何错误。我想更改它，以便将起点和终点作为输入参数

Pqueue 的代码可以在这里找到

罗文先生计划徒步游览巴黎。不过，由于他有点懒惰，所以他想走最短的路径，穿过他想去的所有地方。他计划从第一个地方坐公共汽车，从最后一个地方再坐一辆，所以他可以自由选择起点和终点。你能帮助他吗？

输入

输入的第一行包含访问地点的数量 (n)。然后，在接下来的 n 行中，您找到每个要访问的地方的坐标。这是一个例子：

3

132 73

49 86

72 111

输出

对于每个测试用例，假设从一个地方到另一个地方的步行距离是欧几里得距离，您的程序应该输出一行，其中包含 Rowan 先生访问所有地方必须步行的最短距离。该算法应该以定点表示法输出一个数字，小数点右侧恰好有 3 位数字，并且没有前导空格。最多有12个地方可以参观。例子

示例输入：

3

132 73

49 86

72 111

示例输出：

104.992

我一直在为我的家庭作业编写这段代码，但我无法让它工作，我开始想知道这是否是最好的方法..

问题是 floyd-warshall 函数，它对 float **path 结构没有任何作用.. 不知道为什么.. 在 floydwarshall(path, n, next) 之前和之后路径是相同的；

我在 2d 平面上有 n 个点，n <= 12，我需要可用最短路径的距离，包括所有点，从其中任何点开始，但不形成闭合回路

我一直在尝试弗洛伊德元帅、旅行推销员问题和其他算法，但没有成功。

这个问题对我的老师来说很容易，所以我认为它不需要阿罗拉近似值左右，但我不知道解决这个问题的最佳方法是什么，但也许是一些动态算法之类的

有什么帮助吗？

我有两个数组，一个是节点节点成本数组 [a_node,b_node,cost]，它有 8000 个条目，另一个是节点与坐标 [node,x,y] 的关联，它也有大约 8000 个条目. 拥有这两个的静态数组更好还是将它们存储在数据库中并从中创建一个数组作为性能问题更好？

这两个数组将用于运行最短路径算法。

I have a set data which is a collection of node - node - associated cost. This cost is represented as a distance in feet.

I also have a x-y-coordinate for each node. Now in the A* algorithm I will need to add the cost from node to node + the heuristic cost from the middle node to the destination. However, these two values needs to be having the same metric/unit. I can't have one in feet and the other one in coordinate distance.

I know that in order to do this I first need to find a scaling factor, to scale the cost from feet to x-y-coordinate distance. Right? All I can say is that all this cost is scalable. So this beta value will be the same for all pair of node-node.. Question is how do I find this value?

What I've done right now is to find the coordinate distance between node - node and then from that compare with the cost in feet. And I can therefore find a beta, which is a constant and should work for every node-node-cost (feet)... I am not sure if this is true though. I am not looking for a magic trick here, just a simple way/math to solve this

在 A* 中，您得到的结果通常只有一条路径。根据 A*，给定的起点和终点是否有可能有 3 条推荐路径？所以返回的第二个是第二好的路径，第三个是第三好的路径..

我在想也许以某种方式修改启发式以反映第二和第三个最佳路径。你们怎么看？

更新： 我的实现是在 PHP 中，我使用的是封闭集。因此，如果有办法做到这一点，请告诉我。

在询问了一些关于最短路径算法的一般建议（2D 航路点寻路：从 curLocation 到 targetLocation 的 WP 组合），然后询问更具体的实现（500 多个航路点/节点的最短路径算法（例如 Dijkstra 的）？）已决定使用 JUNG 库（http://jung.sf.net/）。

我现在的目标是通过使用点列表（大小〜1000）中的任意点组合来获得从点 A 到点 B 的最短路径，其中每个点都直接连接到 x 距离内的所有点。

为此，我需要设置一个树形图。我相信这是一个树图实现列表：http: //jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics。 jung.algorithms.shortestpath

那是对的吗？现在，所有这些实现都仅限于稀疏树图，但我必须创建一个相当密集的树图。

那么，我应该在 JUNG 中使用什么树形图来实现我的目标？