问题标签 [shortest]

我遇到了一个奇怪的问题。

我有一个无界的棋盘，N 个骑士起始位置和 N 个目标位置。

任务是找到所有骑士到达所有目标位置的最少移动次数。

我知道单个骑士的最短路径问题可以使用广度优先搜索来解决，但是如何解决多个骑士的问题呢？

对不起我的英语，我很少用它。

默认情况下，flex 使用最长匹配规则。有什么方法可以覆盖此行为以使其匹配最短序列？

谢谢

我有以下问题。给定一个有向图 G=(V,E)，所有边 {i,j} 之间的边成本为 cij。我们有多个来源，比如 s1,...,sk，和一个目标，比如 t。问题是找到从 s1,...sk 到 t 的最低组合成本，其中所有不同路径访问的顶点总数为 M。（源和目标不计为已访问顶点和 0 <= M <= |V|-k+1，所以如果 M = 0，所有路径都直接从源到目标。）

我想出了以下方法，但还没有找到解决方案。

1. 该问题类似于多个目标（t1，...，tk）和一个源，只需反转所有边并使源成为目标和目标源。我认为这可能很有用，因为例如 Dijkstra 计算从一个源到图中所有其他顶点的最短路径。

2. 只需一个目标和一个源，就可以找到最大的最短路径。使用贝尔曼福特算法访问的顶点 M 的数量。这是通过迭代地增加访问顶点的数量来完成的。

3. 当必须访问顶点 v1,...,vk 时，找到从一个源到一个目标的最短路径的问题，对于较小的 k，可以解决如下： i) 计算所有顶点之间的最短路径。ii) 检查k中的哪一个！排列是最短的。我认为这在将我在 1) 处调整的问题转换为从一个源到一个“超级目标”的问题时很有用，强制访问“旧”目标 t1=v1,...,tk=vk。

不幸的是，结合 1、2 和 3 并不能提供解决方案，但它可能会有所帮助。有谁知道解决方案？能否有效解决？

我有一个非常困难的问题要解决，我只是想知道什么算法可以用来找到最快的路线。无向图由正调整和负调整组成，这些调整会影响在迷宫中导航的机器人或事物。我遇到的问题是包含可以是 + 或 - 的循环的迷宫。一个例子可能会有所帮助：-

1. 节点 A 给对象 10 分

2. 节点 B 从对象中取 15

3. 节点 C 给对象 20 分

路线=""

起始节点是A，结束节点是C

给定图形结构为：-

没有循环的节点是c+20，所以节点c有20的正调整但是没有循环

如果机器人或对象在其资源中有 10 个点，那么最佳路径是：-

路线="a,b,c"

这很容易实现，下一个挑战是知道如何回溯到一个好的节点，让我们假设在每个节点上你可以找到它的任何邻居节点及其调整级别。这是下一个示例：-

如果机器人开始时只有 5 个点，那么最好的路径是

路线="a,a,b,c"

这是一个非常简单的图表，但是当您有更多节点时，机器人很难知道是在一个好的节点上循环还是从一个好的节点转到另一个，同时跟踪可能的路线。

这样的路线将是一个回溯队列。

一个更难的例子会导致很多来回

机器人有 10 分

a > b > a > b > a > b > a > b > a > b > c 剩下 5 分。

机器人可以做到的另一种方式是：-

a > a > a > b > c

这是一种更有效的方法，但你怎么能编程这部分是我的问题。

有没有人知道解决这个问题的好算法，我已经研究了 Bellman-fords 和 Dijkstra 但这些只给出了一个简单的路径而不是循环路径。

它可以以某种方式或某种形式的启发式递归吗？

参考您的类比：-

我想我明白你的意思，到目前为止，有点伪会更清楚 route()

我的家庭作业（C++）有问题。我不是要求完整的解决方案，但朝正确的方向倾斜可能会有所帮助。:)

我有一个 NxN 板（最大 N = 100）和那个板上的 1x2 图形（立方体）。立方体的一侧涂成红色，另一侧涂成蓝色。立方体的默认位置是棋盘的左上角，蓝色面朝上：

（4x4 示例，B 代表蓝色）

黑板上可能有石头（障碍物）。 我可以用我的身材做的动作：

• 顺时针旋转 90/180/270 度
• 你可以围绕它的右/左/上/下边缘翻转立方体，改变它的“向上颜色”

例如，在默认位置使用向右翻转：

然后使用旋转 90：

然后使用左翻转：

当然，在旋转或翻转时，你不能落在石头上。所以，问题是——对于任何给定的棋盘配置（图形位置和石头位置）编写一个程序，使用最少的移动次数“将立方体带回家”在默认位置（蓝色面朝上！）如果可能，则返回 1，如果不可能，则返回 0。

我觉得这个问题很有趣，但我不得不承认我对此有点困惑。尤其是蓝边/红边部分。我真的不知道如何“翻译”那些我可以用通常的最短路径算法的语言使用的动作（我从来没有使用过这些）。因此，我将不胜感激您提供的每一条建议！:)

例如：

m_array = new int[6][6];
m_array[0] = new int[]{2, 0, 0, 0, 0, 0};
m_array[1] = new int[]{0, 2, 0, 0, 0, 2};
m_array[2] = new int[]{2, 0, 0, 1, 0, 0};
m_array[3] = new int[]{0, 0, 0, 0, 0, 0};
m_array[4] = new int[]{0, 2, 0, 0, 2, 0};
m_array[5] = new int[]{0, 0, 2, 0, 0, 0};


我怎样才能找到最接近的 2 到 1？

我想要一个函数，它返回一个数组路径，包括数组点。例如，我将“m_array”给我的函数，它会返回给我最近的 2 换 1，一个数组路径，如 [2,3][3,4][4,4]

对于n车站，给出了一个n*n矩阵，表示从车站到(i,j <= n)的直接行程时间。AA[i][j]ij

在车站之间旅行的人总是寻求最少的时间。给定两个站号a，b如何计算它们之间的最短旅行时间？

这个问题可以在不使用图论的情况下解决，即仅通过矩阵 A 来解决吗？

我想编写一个程序，返回从 A 点到 E 点的最短距离。我编写了代码来获取长度，但我不知道如何实际获取这些点。

输入的答案：shortestPath(["A","B", "C", "D", "E"],d) 是 10。但程序也应该输出距离，所以答案实际上应该是为 [10, ["A", "C", "D", "E"]]

如何使用广度优先搜索在简单（非有向）二部图中找到最短循环？

我已经评估 Neo4j 1.9.M03 有一段时间了，并且达到了我没想到的程度。

我有一个约 140,000 个顶点的图。我也有三类边，我们称它们为父亲、母亲和丈夫。每个类大约有 80,000 条边。没有属性，也没有索引。顶点存储大小约为 1.3 MB，边缘存储约为 8 MB。

数据源自 SQL Server，并且已知从 SQL 迁移到 Neo4j 的质量是正确的。对几十个顶点对运行SQL最短路径存储过程，已知最短路径距离和路径。

最短路径查询是 Cypher：START one=node(0), two=node(1234) MATCH p = shortestPath(one-[*..1000]-two) RETURN p;

部分测试用例一：我只使用丈夫和父亲的关系，循环的出现（例如v[0] -> v[1] -> v[2] -> v[0])很低。如果我在特定的已知长路径（例如已知为~450 跳）上执行最短路径计算，它会在 50ms 内返回（非缓存），路径约为 550 跳。预计长度会增加，因为我们排除了部分边。

部分测试用例二：同样，如果我只使用夫妻关系，循环的发生率（例如v[0] -> v[1] -> v[2] -> v[0])很低。如果我执行相同的最短路径，我会得到与以前相同的顺序的结果：大约 50 毫秒（非缓存)，路径长度也有类似的增加。

完整测试案例：我使用所有（父亲、母亲和丈夫）关系。由于常见情况，现在可以预见循环的发生率很高v[0] mother-> v[1] husband-> v[2] <-father v[0]。当我执行最短路径查询时，JVM 分配了 4 GB 的内存并且计算没有完成。这就是问题。

我的论点是循环的定期发生导致了这种行为，否则当我只添加另一类父边时，我不会期望性能有如此巨大的差异——除非最短路径算法没有考虑循环。

我直接使用 Java API 应用了 Dijkstra 算法，所有边的成本为 1，并获得了与使用的标准 ShortestPath 算法相似的结果。结果，我在 IntelliJ 调试 6 分钟后收到了这个异常。

你觉得我说的对吗？这是图形数据库或其最短路径算法的已知限制吗？对我来说，以前访问过的顶点不会存储在哈希表中似乎很愚蠢，这样最短路径算法就不会多次尝试离开以前访问过的顶点。

2013 年 1 月 25 日更新

一个 Github 回购，所以你可以跟随！

2013 年 2 月 7 日更新

请参阅已接受的答案。简而言之，周期与它无关。