证明在给定的边分组约束下生成 2 条最短路径的 NP 完全性？
Prove NP-Completeness of generating 2 shortest routes over given edge grouping constraints?
我一直在尝试解决以下问题，但没有成功，即 NP-Complete 或 NP-Hard。
问题如下：
给你一个图 G(V,E)，要求你生成从起始节点 S 到节点 T 的两条路线。边 E 被分成 K 个不相交的集合。让我们将两条路由称为 R1 和 R2。同一组中不能有边 E1 和 E2，使得 E1 在路径 R1 中，E2 在 R2 中（简单来说，每个组只能被一条路径使用）。此外，R1 和 R2 之间不能共享任何节点。我们正在寻找 R1 和 R2 的最短组合路径长度 (Minimize (len(R1) + len(R2)) ).
我已经尝试将子集总和和独立集减少到这个但没有成功。
首先，感谢您发布一个非常有趣的问题。完成这个过程很有趣！
我想出的减少是从 3SAT 到你的问题。直观地，归约工作如下：我们构建一个由两个平行的、级联的节点系列组成的图（我们称它们为左分支和右分支）。左分支边缘对应公式中的变量，右分支边缘对应公式中的子句。我们将构建图表，使两条路径对应于为满足所有子句的公式选择变量赋值。
强制变量取值的左分支构建如下。对于每个变量 x，构建一个如下所示的小工具：
*
true --> / \ <-- false
* *
\ /
*
从顶部节点开始，我们将 "left" 表示 "x is true"，"right" 表示 "x is false." 我们将为每个变量构建此小工具的一个副本link 他们从上到下。因此，从链的顶部到底部的路径对应于为命题公式选择变量赋值。
右边的分支也是类似的搭建。假设我们有一个子句 x &lor; y &l; z。然后我们构建这个小工具：
*
/|\
* * *
\|/
*
这里左边的分支对应"x is true,"中间的分支对应"y is true"，右边的分支对应"z is true."思路是我们至少需要有一个每个子句的真实文字，我们将通过选择要走的路径来选择哪个文字。
现在，我们构建约束集。对于每个变量 x，我们要确保如果在左分支中我们说 x 为真，我们不会在右分支中遵循 x 应该为假的边。因此，我们将创建一个约束集，其中包含来自左分支的边 "x is true" 和来自右分支的 "x is false" 的所有副本。我们将类似地创建第二个约束集，其中包含来自左分支的边 "x is false" 和来自右分支的所有标记为 "x is true" 的边。这些约束集共同确保如果我们通过左分支和右分支选择一条路径，我们为每个变量选择一个值（通过左分支的路径）并为每个子句选择至少一个真实文字（通过右分支）。
为了完成所有事情，我们将创建一个新的起始节点 S 和一个新的终端节点 T，link将 S 连接到左分支中的第一个节点和右分支中的第一个节点，然后 link 将左右分支中的最后一个节点转移到 T。现在，当且仅当存在从 S 到 T 的两条节点不相交路径并遵守所有约束条件时，公式才有令人满意的赋值。做一些快速的数学表明，如果公式有 n 个变量和 m 个子句，那么通过左分支的路径长度将为 2n + 2，通过右分支的路径长度将为 2m + 2，因此公式当且仅当存在一对从 S 到 T 的节点不相交路径且总长度为 2n + 2m + 4 时才可满足。请注意，如果公式不可满足，则根本不存在合法路径。
希望对您有所帮助！
我一直在尝试解决以下问题，但没有成功，即 NP-Complete 或 NP-Hard。
问题如下：
给你一个图 G(V,E)，要求你生成从起始节点 S 到节点 T 的两条路线。边 E 被分成 K 个不相交的集合。让我们将两条路由称为 R1 和 R2。同一组中不能有边 E1 和 E2，使得 E1 在路径 R1 中，E2 在 R2 中（简单来说，每个组只能被一条路径使用）。此外，R1 和 R2 之间不能共享任何节点。我们正在寻找 R1 和 R2 的最短组合路径长度 (Minimize (len(R1) + len(R2)) ).
我已经尝试将子集总和和独立集减少到这个但没有成功。
首先，感谢您发布一个非常有趣的问题。完成这个过程很有趣！
我想出的减少是从 3SAT 到你的问题。直观地，归约工作如下：我们构建一个由两个平行的、级联的节点系列组成的图（我们称它们为左分支和右分支）。左分支边缘对应公式中的变量，右分支边缘对应公式中的子句。我们将构建图表，使两条路径对应于为满足所有子句的公式选择变量赋值。
强制变量取值的左分支构建如下。对于每个变量 x，构建一个如下所示的小工具：
*
true --> / \ <-- false
* *
\ /
*
从顶部节点开始，我们将 "left" 表示 "x is true"，"right" 表示 "x is false." 我们将为每个变量构建此小工具的一个副本link 他们从上到下。因此，从链的顶部到底部的路径对应于为命题公式选择变量赋值。
右边的分支也是类似的搭建。假设我们有一个子句 x &lor; y &l; z。然后我们构建这个小工具：
*
/|\
* * *
\|/
*
这里左边的分支对应"x is true,"中间的分支对应"y is true"，右边的分支对应"z is true."思路是我们至少需要有一个每个子句的真实文字，我们将通过选择要走的路径来选择哪个文字。
现在，我们构建约束集。对于每个变量 x，我们要确保如果在左分支中我们说 x 为真，我们不会在右分支中遵循 x 应该为假的边。因此，我们将创建一个约束集，其中包含来自左分支的边 "x is true" 和来自右分支的 "x is false" 的所有副本。我们将类似地创建第二个约束集，其中包含来自左分支的边 "x is false" 和来自右分支的所有标记为 "x is true" 的边。这些约束集共同确保如果我们通过左分支和右分支选择一条路径，我们为每个变量选择一个值（通过左分支的路径）并为每个子句选择至少一个真实文字（通过右分支）。
为了完成所有事情，我们将创建一个新的起始节点 S 和一个新的终端节点 T，link将 S 连接到左分支中的第一个节点和右分支中的第一个节点，然后 link 将左右分支中的最后一个节点转移到 T。现在，当且仅当存在从 S 到 T 的两条节点不相交路径并遵守所有约束条件时，公式才有令人满意的赋值。做一些快速的数学表明，如果公式有 n 个变量和 m 个子句，那么通过左分支的路径长度将为 2n + 2，通过右分支的路径长度将为 2m + 2，因此公式当且仅当存在一对从 S 到 T 的节点不相交路径且总长度为 2n + 2m + 4 时才可满足。请注意，如果公式不可满足，则根本不存在合法路径。
希望对您有所帮助！