算法 - 具有或有成本的最短路径
Algorithms - Shortest Path with Contingent Costs
我正在寻找一种有效的算法来解决以下问题：
给定一个有向加权图 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.
这道题是NP-hard，明明是NP。证明是一个相对简单的小工具减少。
这或多或少排除了对该问题的琐碎的强力算法进行重大改进的可能性。那么，当您在这里说 "efficient" 时，您到底希望得到什么？
===
证明
可能是问题陈述不知何故不清楚，所以 OP 关心的版本实际上不是 NP 完全的。所以我会给出一些证明的细节。
出于技术原因，通常当我们想要显示搜索问题是 NP-hard 时，我们实际上是针对可与搜索问题互约的相关决策问题来做的。这里的判定问题是"Given a directed weighted graph as described with associated edge-weight changing data, and a numeric value V, does the shortest path have value at most V?"。很明显，如果你有一个解决搜索问题的算法，你就可以很容易地解决决策问题，如果你有一个解决决策问题的算法，你就可以用它来解决搜索问题——你可以使用二分搜索来确定V 的最优值的精度大于输入数字，然后通过删除边并检查最优解值是否更改以确定边是否在路径中来更改问题实例。所以在sequel我说说决定版本的问题。
问题出在NP
首先要看到它在 NP 中，我们希望看到决策问题的 "yes" 个实例在多项式时间内是可证明的。这里的证书只是最短路径。很容易看出，最短路径不需要比图本身更多的位来描述。计算任何特定路径的值也很容易，您只需遍历路径的步骤并检查当时下一条边的值是多少。所以问题出在NP.
问题是NP-hard
为了看出它是 NP-hard，我们从 3SAT 减少到决策问题。这就是确定 CNF 形式的布尔公式的可满足性问题，其中每个子句最多有 3 个文字。有关 3SAT 的完整定义，请参见此处：https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
我将描述的缩减是一个转换，它采用 3SAT 的实例并产生决策问题的输入，其中 属性 3SAT 实例是可满足的当且仅当最短路径值小于指定阈值。
对于任何给定的 3SAT 公式，我们将生成的图形具有以下高级结构。对于每个变量，将有一个 "cloud" 个与其关联的顶点，这些顶点以某种方式连接，其中一些顶点在 M 中。图形的排列使得最短路径必须恰好通过每个云一次，首先穿过 x1 的云，然后穿过 x2 的云，依此类推。然后，公式的每个子句也有一个（不同排列的）云。通过最后一个变量的云后，路径必须连续通过子句的云。然后到达终点站。
基本思想是，当通过云计算变量xi时，恰好有两种不同的可能路径，选择代表对真值xi的承诺。可变云的所有边成本都是相同的，因此它不会直接影响路径值。但是，由于其中一些在 M 中，因此那里的路径选择会改变稍后在子句云中的成本。子句云强制如果我们选择的变量不满足子句，那么我们要付出代价。
变量云看起来像这样：
*_*_*_*
/ \
Entry * * Exit
\ /
*_*_*_*
其中，星星是顶点，线是边，所有的边都指向右边，并且具有相同的成本，我们可以将其设为零，或者如果这是一个问题，它们都可以成为一个，这并不重要。这里我在两条路径上显示了 4 个顶点，但实际上顶点的数量将取决于一些因素，正如我们将看到的。
条款云看起来像这样：
*
/ \
Entry *_*_* Exit
\ /
*
其中，所有边再次指向右侧。
3 个中心顶点中的每一个都是 "labelled"（在我们看来）并且对应于子句中的三个文字之一。所有这些边的成本再次为 0。
想法是，当我遍历变量云并为该变量选择一个值时，如果我不满足某些子句的文字，则子句云中相应边的成本应该去向上。因此，只要我至少真正满足子句，我就有一条从入口到出口的路径，成本为 0。如果每个文字都被这个赋值遗漏，那么我必须支付大于零的费用。也许，100 或什么的，这并不重要。
现在回到变量云，xi 的变量云在中间部分有 2m 个顶点，其中 m 是 xi 的子句数出现在。然后，根据它在第k个这样的子句中是正面还是负面出现，顶部或底部路径的第k个顶点在M中并改变相应子句云中的边，成本为 100 或任何其他固定值。
整个图表是通过简单地将变量和子句云在它们的入口-出口节点连续粘贴在一起而制成的。例如，阈值是 50。
关键是，如果对 3SAT 实例有一个令人满意的分配，那么我们可以从中构造一条通过成本为 0 的图实例的路径，因为我们从不在顶点云中支付任何费用，而且我们总是可以在每个子句云中选择一个子句得到满足的路径，我们也不在那里支付任何费用。如果对 3SAT 实例没有令人满意的分配，那么任何路径都必须在某个点弄错一个子句，然后至少支付 100。因此，如果我们将阈值设置为 50 并生成该实例的那部分，则减少是合理的。
如果问题陈述实际上不允许 0 成本边，我们可以轻松地更改解决方案，使其仅具有正成本边。因为，任何路径从开始到结束的边总数对于每条路径都是相同的。因此，如果我们将每条边成本加 1，并将阈值改为 50 + 长度，则什么都没有改变。
正如 David Eisenstat 在评论中指出的那样，可以使用向所有边缘添加固定值并调整阈值的相同技巧来发现问题也非常不可近似。
运行时间影响
如果您在分配给每个变量云的顶点数量方面经济实惠，则缩减将具有 n 个变量（因此输入长度 O(n)）的 3SAT 实例也用于图形实例O(n) 个顶点，并且图是稀疏的。 （100n 个顶点应该绰绰有余。）因此，如果您可以在 [=23] 的稀疏图上用 运行 时间小于 2^{o(n)} 的时间给出所述问题的算法=] 顶点，它意味着 3SAT 的 2^{o(n)} 算法，这将是算法的重大突破，并将反驳 Impagliazzo 和 Paturi 的 "Exponential Time Hypothesis"。因此，对于这个问题中的普通算法，您真的只能希望得到指数常数因子的改进。
我正在寻找一种有效的算法来解决以下问题：
给定一个有向加权图 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.
这道题是NP-hard，明明是NP。证明是一个相对简单的小工具减少。
这或多或少排除了对该问题的琐碎的强力算法进行重大改进的可能性。那么，当您在这里说 "efficient" 时，您到底希望得到什么？
===
证明
可能是问题陈述不知何故不清楚，所以 OP 关心的版本实际上不是 NP 完全的。所以我会给出一些证明的细节。
出于技术原因，通常当我们想要显示搜索问题是 NP-hard 时，我们实际上是针对可与搜索问题互约的相关决策问题来做的。这里的判定问题是"Given a directed weighted graph as described with associated edge-weight changing data, and a numeric value V, does the shortest path have value at most V?"。很明显，如果你有一个解决搜索问题的算法，你就可以很容易地解决决策问题，如果你有一个解决决策问题的算法，你就可以用它来解决搜索问题——你可以使用二分搜索来确定V 的最优值的精度大于输入数字，然后通过删除边并检查最优解值是否更改以确定边是否在路径中来更改问题实例。所以在sequel我说说决定版本的问题。
问题出在NP
首先要看到它在 NP 中，我们希望看到决策问题的 "yes" 个实例在多项式时间内是可证明的。这里的证书只是最短路径。很容易看出，最短路径不需要比图本身更多的位来描述。计算任何特定路径的值也很容易，您只需遍历路径的步骤并检查当时下一条边的值是多少。所以问题出在NP.
问题是NP-hard
为了看出它是 NP-hard，我们从 3SAT 减少到决策问题。这就是确定 CNF 形式的布尔公式的可满足性问题，其中每个子句最多有 3 个文字。有关 3SAT 的完整定义，请参见此处：https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
我将描述的缩减是一个转换，它采用 3SAT 的实例并产生决策问题的输入，其中 属性 3SAT 实例是可满足的当且仅当最短路径值小于指定阈值。
对于任何给定的 3SAT 公式，我们将生成的图形具有以下高级结构。对于每个变量，将有一个 "cloud" 个与其关联的顶点，这些顶点以某种方式连接，其中一些顶点在 M 中。图形的排列使得最短路径必须恰好通过每个云一次，首先穿过 x1 的云，然后穿过 x2 的云，依此类推。然后，公式的每个子句也有一个（不同排列的）云。通过最后一个变量的云后，路径必须连续通过子句的云。然后到达终点站。
基本思想是，当通过云计算变量xi时，恰好有两种不同的可能路径，选择代表对真值xi的承诺。可变云的所有边成本都是相同的，因此它不会直接影响路径值。但是，由于其中一些在 M 中，因此那里的路径选择会改变稍后在子句云中的成本。子句云强制如果我们选择的变量不满足子句，那么我们要付出代价。
变量云看起来像这样：
*_*_*_*
/ \
Entry * * Exit
\ /
*_*_*_*
其中，星星是顶点，线是边，所有的边都指向右边，并且具有相同的成本，我们可以将其设为零，或者如果这是一个问题，它们都可以成为一个，这并不重要。这里我在两条路径上显示了 4 个顶点，但实际上顶点的数量将取决于一些因素，正如我们将看到的。
条款云看起来像这样：
*
/ \
Entry *_*_* Exit
\ /
*
其中，所有边再次指向右侧。
3 个中心顶点中的每一个都是 "labelled"（在我们看来）并且对应于子句中的三个文字之一。所有这些边的成本再次为 0。
想法是，当我遍历变量云并为该变量选择一个值时，如果我不满足某些子句的文字，则子句云中相应边的成本应该去向上。因此，只要我至少真正满足子句，我就有一条从入口到出口的路径，成本为 0。如果每个文字都被这个赋值遗漏，那么我必须支付大于零的费用。也许，100 或什么的，这并不重要。
现在回到变量云，xi 的变量云在中间部分有 2m 个顶点，其中 m 是 xi 的子句数出现在。然后，根据它在第k个这样的子句中是正面还是负面出现，顶部或底部路径的第k个顶点在M中并改变相应子句云中的边，成本为 100 或任何其他固定值。
整个图表是通过简单地将变量和子句云在它们的入口-出口节点连续粘贴在一起而制成的。例如，阈值是 50。
关键是，如果对 3SAT 实例有一个令人满意的分配，那么我们可以从中构造一条通过成本为 0 的图实例的路径，因为我们从不在顶点云中支付任何费用，而且我们总是可以在每个子句云中选择一个子句得到满足的路径，我们也不在那里支付任何费用。如果对 3SAT 实例没有令人满意的分配，那么任何路径都必须在某个点弄错一个子句，然后至少支付 100。因此，如果我们将阈值设置为 50 并生成该实例的那部分，则减少是合理的。
如果问题陈述实际上不允许 0 成本边，我们可以轻松地更改解决方案，使其仅具有正成本边。因为，任何路径从开始到结束的边总数对于每条路径都是相同的。因此，如果我们将每条边成本加 1，并将阈值改为 50 + 长度，则什么都没有改变。
正如 David Eisenstat 在评论中指出的那样，可以使用向所有边缘添加固定值并调整阈值的相同技巧来发现问题也非常不可近似。
运行时间影响
如果您在分配给每个变量云的顶点数量方面经济实惠，则缩减将具有 n 个变量（因此输入长度 O(n)）的 3SAT 实例也用于图形实例O(n) 个顶点，并且图是稀疏的。 （100n 个顶点应该绰绰有余。）因此，如果您可以在 [=23] 的稀疏图上用 运行 时间小于 2^{o(n)} 的时间给出所述问题的算法=] 顶点，它意味着 3SAT 的 2^{o(n)} 算法，这将是算法的重大突破，并将反驳 Impagliazzo 和 Paturi 的 "Exponential Time Hypothesis"。因此，对于这个问题中的普通算法，您真的只能希望得到指数常数因子的改进。