algorithm - 动态图算法最短路径

Question

我有一个问题，我正在将其转换为 TSP 类问题，以便我可以在此处对其进行解释，并且我正在寻找可能对我有帮助的任何现有算法。

1. 有一个我需要去的地方的列表，我需要去所有的地方。
2. 有些地方必须作为 n 的第一个 x 访问(即，它们需要是前 3 个或前 5 个访问的地方)。 (其中数量是任意的)
3. 还有一些其他地方必须作为 n 的最后 y 个访问(即，它们需要是最后 3 个或最后 5 个访问的地方)。
4. 可以对这些地方进行分类(有些地方可能没有类别)，对于属于一个类别的地方，它们需要尽可能远离彼此(即，如果 2 个地方被归类为绿色，那么我想访问这些绿色分类地点之间尽可能多的其他类别地点)

这是一个示例列表:

A:类别绿色:最后 3

B:类别无:无排序

C: 粉红色类别:前 3

D: 类别无:无排序

E:类别无:最后 3

F:类别绿色:无排序

G:粉红色类别:前 3

我想提出的顺序是:

G(pink,first3) -> F(green,none) -> C(pink,first3) -> D(none,none) -> B(none,none) -> E(none,last3) -> A(green,last3)

解释:G在前，尽量远离C。F紧随其后，让它离A越远越好。C 紧随其后，因为它需要排在前 3 位。C 和 G 可以互换D B 可以放在任何地方E 紧随其后，因为它必须是最后 3 个A 排在最后，因为它必须排在最后 3 个，将它放在最后，它离 F 越远越好。

我的想法是评估每条边的成本，然后动态计算边的成本。因此，如果您尝试先访问 A，然后访问 F，成本会很高，而不是先访问 A，然后访问其他某个地方，然后再访问 F(中间的地点数量可能是成本的一​​部分)。另外，我会介绍一个开始和结束的地方，所以，如果我必须作为第一个 x 访问某些地方，如果开始在那个地方的 N 个地方之内，我就可以给它一个低成本。最后也是一样。

我想知道是否有一种图形算法可以考虑这种动态权重/成本并确定从开始到结束的最短路径？

注意:在某些情况下，最好的情况可能不可用，这没关系，只要我能证明成本很高是因为没有足够的类别分离(例如:所有地方都属于同一类别) .

蛮力算法我最初的想法是:给定一个地点列表，提出所有地点排序组合并计算每个地点之间的成本，然后选择最便宜的。 (但这将意味着评估 n!其中 8 将是我必须评估的 362880 个订单!为什么是 8，因为我认为这是要评估的平均数量)

但是有没有一种算法可以让我在不测试所有顺序的情况下确定它。

Answer 1

你可以做的一件事:

• 按以下顺序排列位置:第一个，...第一个，无序，最后一个，...最后一个。
• 遍历列表并在不违反先前顺序的情况下尽可能将相同颜色的元素分开
• 计算此列表的成本并将其存储为当前最佳
• 使用此列表来确定您评估排列的顺序
• 在构建排列时，跟踪成本
• 当成本超过当前最佳值(包括剩余位置的理论最小成本，如果有的话)时中止构建当前排列
• 当您获得理论上可能的最佳分数时也会中止。