首页 文章

算法 - 具有或有成本的最短路径

提问于
浏览 次
-1

我正在寻找一种有效的算法来解决以下问题：

给定有向加权图 G = (V,E) ，源顶点 S ，目标顶点 T 和 M （ V 的子集），需要找到从 S 到 T 的最短路径 .
M 中存在的一个特殊功能是 M 中的每个顶点，一旦'visited'，某个边的权重变为另一个值 . 在 M 中，将为每个顶点给出边和新权重 .

为了帮助理解问题，I have drawn an example using mspaint . （对不起质量） .

在此示例中，从 S 到 T 的'regular'最短路径是 1000 . 但是，访问顶点 C 会将边缘权重从 1000 减少到 500 ，因此这种情况下的最短路径是 200 100 500 = 800 .

algorithm graph-theory

1 回答

  • 2

    这个问题是NP难的，显然是NP . 证明是一个相对简单的小工具减少 .

    这或多或少地排除了对这个问题的琐碎，强力算法的重大改进 . 那么当你在这里说“效率”时，你究竟想要什么呢？

    ===

    Proof

    可能是问题陈述在某种程度上不清楚，因此OP关心的版本实际上并不是NP完全的 . 所以我将提供一些证明细节 .

    由于技术原因，通常当我们想要显示搜索问题是NP难的时，我们实际上是为了一个与搜索问题可以互联的相关决策问题 . 这里的决策问题是“给定如相关边缘权重变化数据所描述的有向加权图和数值V，最短路径最多具有V的值吗？” . 显然，如果你有搜索问题的算法，你可以很容易地解决决策问题，如果你有一个决策问题的算法，你可以用它来解决搜索问题 - 你可以使用二进制搜索来确定V的最佳值精度大于输入数，然后通过删除边并检查最佳解决方案值是否更改来更改问题实例，以确定边是否在路径中 . 所以在续集中我会谈到问题的决定版本 .

    The problem is in NP

    首先要看到它在NP中，我们希望看到决策问题的“是”实例在多项式时间内是可证明的 . 这里的证书只是最短的路径 . 很容易看出，最短路径不需要比图形本身更多的位来描述 . 计算任何特定路径的值也很容易，您只需完成路径的步骤并检查当时下一个边的值是多少 . 所以问题出在NP .

    The problem is NP-hard

    为了看到它是NP难的，我们从3SAT减少到决策问题 . 这是确定CNF形式的布尔公式的可满足性的问题，其中每个子句最多具有3个文字 . 有关3SAT的完整定义，请参见此处：https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

    我将描述的减少是一个转换，它采用3SAT的实例并产生决策问题的输入，当且仅当最短路径值小于指定阈值时，具有3SAT实例可满足的属性 .

    对于任何给定的3SAT公式，我们将生成的图表具有以下高级结构 . 对于每个变量，将有一个与之关联的"cloud"个顶点以某种方式连接，其中一些顶点在M中 . 图形的排列使得最短路径必须通过每个 Cloud 一次，通过首先是 x1 的 Cloud ，然后是 x2 的 Cloud ，依此类推 . 然后，对于公式的每个子句，还存在（不同地布置的） Cloud . 在经过最后一个变量的 Cloud 之后，路径必须连续通过子句的 Cloud . 然后它到达终端 .

    基本思想是，当通过 Cloud 进行变量 xi 时，恰好有两种不同的可能路径，并且该选择表示对 xi 的真值的承诺 . 变量 Cloud 的边缘的所有成本是相同的，因此它不满足该条款，然后我们付出代价 .

    变量 Cloud 看起来像这样：

    *_*_*_*
       /       \
Entry *         * Exit
       \       /
        *_*_*_*

    其中，星星是顶点，线条是边缘，所有边缘都指向右边，并且成本相同，我们可以将其视为零，或者如果这是一个问题，它们都可以是一个，它不会真的很重要在这里，我在两条路径上显示了4个顶点，但实际上顶点的数量将取决于某些事情，我们将会看到 .

    子句 Cloud 看起来像这样：

    *
       / \
Entry *_*_* Exit
       \ /
        *

    其中，所有边缘都指向右边 .

    3个中心顶点中的每一个都被“标记”（在我们的脑海中）并且对应于该子句中的三个文字中的一个 . 所有这些边缘再次成本为0 .

    这个想法是什么时候我浏览变量 Cloud ，并为该变量选择一个值，如果我不满足某个子句的字面值，那么子句 Cloud 中相应边缘的成本应该会上升 . 因此，只要至少我实际上满足该条款，我就有一条从入口到出口的路径，费用为0.如果这个分配错过了每一个文字，那么我必须支付大于零的东西 . 也许，100或者什么，它并不重要 .

    现在回到变量 Cloud ， xi 的变量 Cloud 在中间部分有 2m 个顶点，其中 m 是 xi 出现的子句数 . 然后，根据 k 这样的子句中它是正面还是负面显示， k 顶部或底部路径的顶点位于 M 并更改相应子句 Cloud 中的边缘，以获得成本100或任何其他固定值 .

    通过简单地将变量和子句 Cloud 连续地粘贴在它们的入口 - 出口节点上来制作整个图 . 阈值例如是50 .

    关键是，如果对3SAT实例有一个令人满意的赋值，那么我们可以从它构造一个通过cost 0的图形实例的路径，因为我们从不在顶点 Cloud 中支付任何东西，并且我们总是可以选择一个路径每个条款 Cloud 都是这个条款的标准，我们也不支付任何费用 . 如果对3SAT实例没有令人满意的赋值，那么任何路径必须在某个时刻得到一个错误的子句然后支付至少100.因此，如果我们将阈值设置为50并且使该实例的那部分成为可能，则减少是合理的 .

    如果问题陈述实际上不允许0成本边缘，我们可以轻松地更改解决方案，使其仅具有正成本边缘 . 因为，从开始到结束的任何路径中的边缘总数对于每个路径都是相同的 . 因此，如果我们将每个边缘成本加1，并将阈值设置为50长度，则不会更改任何内容 .

    正如David Eisenstat在评论中所指出的那样，可以使用向所有边缘添加固定值并调整阈值的相同技巧来确定问题也非常强烈 .

    Running time implications

    如果您在为每个变量 Cloud 分配的顶点数量方面是经济的，则减少将带有 n 变量的3SAT实例（因此输入长度 O(n) ）也带到 O(n) 顶点的图形实例，并且图形是稀疏的 . （ 100n 顶点应该是绰绰有余的 . ）因此，如果你可以在具有 n 顶点的稀疏图上给出小于 2^{o(n)} 的运行时间的所述问题的算法，则它意味着3SAT的 2^{o(n)} 算法将是一个主要的算法取得突破，并且会反驳Impagliazzo和Paturi的"Exponential Time Hypothesis" . 因此，对于这个问题中的平凡算法，你不可能真的希望不仅仅是一个恒定因子在指数上的改进 .

    回复于

相关问题