可以说我有一组目的地和另一组相应的起点。我需要将每个目的地与一个起点关联起来。一组车辆从每个起点开始向各自的目的地出发，并提供了每辆车的速度。
在网络中，任何时候都不允许两辆在相反方向上行驶的车辆在特定道路上行驶，总之，在道路上不应发生任何碰撞，如果出现这种情况，两辆车辆中的任何一辆都可以在路上发生碰撞时，可以等到另一辆车驶过或走另一条路才能到达目的地。
该图可以认为是道路网络，其中图中的每个边都代表道路，而图中的顶点可以认为是边的交点。
目的是计算满足上述所有约束条件的每辆车到达目的地的最短时间，以及每辆车到达目的地的路径。
解决这个问题的想法？
最佳答案
这是NP难题。
即使在以下同时存在的限制的任意组合下，决定所有汽车是否最多可以在给定的k个时间单位内完成行程的问题也是NP-难的：所有汽车以单位速度行驶，每个边的长度为1，k =3。NP难的问题意味着几乎肯定没有解决每个实例的多项式时间算法。为了说明这一点，我将减少NP难题3SAT：在这个问题中，我们得到了n个子句的合取（AND）形式的布尔表达式，每个子句都是一个析取（OR ）的3个文字，每个文字要么是变量，要么是其取反（NOT）。总共有m个变量，我们可以将每个变量分配为TRUE或FALSE；我们的任务是确定整体表达式是否令人满意-也就是说，是否存在对m个变量的TRUE或FALSE值赋值，导致整体表达式为TRUE。
从任意3SAT实例构造您的问题的实例
假设我们有一个3SAT实例，其中包含n个子句和m个变量。我们可以构造一个您的问题的实例，其中每个变量都成为一个边，沿着该边的流量方向（从左到右或从右到左）对应于变量的值（TRUE或FALSE）。每个子句都变成一个连接到这些可变边的3个两端的小工具。直观地，每个子句小工具都为车辆提供了从其起点（以左侧为起点）出发的三个选项之一，以到达其相应的终点（以右侧为起点）。特别：
首先，删除任何既包含变量又包含否定字面量的子句。这有助于从图中删除长度为2的行程，而不会影响原始表达式的可满足性，因为这样的子句可以通过任何赋值来满足。
对于每个变量x_i，创建两个顶点u_i和v_i，以及边（u_i，v_i）。此构造中的所有边缘都具有重量（距离？）1。
对于所有1 最后，为每个1
我现在声称，只有且仅当您刚刚构造的问题实例的解决方案的持续时间最多为3时，原始3SAT实例才可以满足要求。
3SAT实例为是=>问题实例为是
首先，我将证明如果3SAT实例是可满足的，那么存在一个持续时间为3的问题的刚刚构造好的实例的解决方案。在这种情况下，我们可以假设存在令人满意的赋值Y，因此每1
对您的问题的实例为是=>对3SAT实例为是
现在，我将说明，如果问题的刚刚构建的实例的解决方案的持续时间最多为3，则存在对原始3SAT实例的满意分配。假设对刚刚构造的实例有这样的解决方案：那么显然，每次旅行都必须以最多3个时间单位完成。为了使汽车从s_j到达t_j，它必须使用入射在s_j上的3个边沿中的至少1个和入射在t_j上的3个边沿中的至少1个，因此必须至少使用2个时间单位。此外，由于我们删除了同时包含变量及其否定项的子句，因此对于任何j而言，s_j和t_j都没有顶点相邻，因此至少需要一个边，这意味着3个时间单位是我们希望的最短路径（因为每个边沿都占用1个时间单位）。因此，解决方案中的每个行程都必须精确地沿3个时间单位沿3条边路行驶，而这条路不会因汽车驶入而导致停顿。请注意，在这条路径上的中腿必须是单个可变边，因为从某些u_i到v_i或反之亦然的唯一其他方法包括通过至少2个以上的边“加倍返回”。特别是，对于从s_j开始的行程，它必须是与子句j中的3个文字相对应的3个不同的可变边之一。具体来说，让第j个子句中的文字为a，b和c。令x_i为文字a中的变量。如果a为正，则“从u_i到v_i”是从s_j开始旅行的3个允许行程之一，否则（即，如果a为负）“从v_i到u_i”是。对于其余的文字b和c同样。因此，到目前为止，我们已经确定：
对于每1
我们为3SAT实例构建一个解决方案，如下所示：对于每个变量x_i，如果边缘（u_i，v_i）被从u_i到v_i的一或多辆汽车穿过，则将TRUE分配给y_i；如果从v_i到u_i有一辆或多辆汽车横穿，则将FALSE分配给y_i；否则（如果边缘完全没有交叉），则将任意一个值分配给y_i。我们需要显示两件事：没有为变量同时分配TRUE和FALSE，并且该赋值使表达式采用值TRUE。
首先，可以通过上述规则为变量x_i分配TRUE和FALSE的唯一条件是，至少有一辆汽车在每个方向上越过边缘（u_i，v_i）。假设矛盾是正确的：在解决方案中，某个可变边沿（u_i，v_i）沿相反的方向交叉了2次不同的行车路程。然后，显然两辆车中的至少一辆必须暂停至少1步，以使另一辆车通过此边缘。但是解决方案至少需要4个时间步长，这与我们对最多3个时间步长的持续时间解决方案的假设相抵触，因此，必须确定的是，如果有任何车辆越过边缘（u_i，v_i），那么它们都将在同一时间这样做方向，因此每个变量最多分配TRUE或FALSE之一。
其次，对于每个1
因此，我们刚刚从解决方案中为您的问题实例构建的3SAT问题的变量分配没有矛盾，并且产生了值TRUE：即3SAT公式是可满足的。
包起来
现在我们已经确定对问题“此3SAT表达式是否存在令人满意的分配？”的答案为是。意味着对“是否有一种方法可以在3个时间步以内或少于3个时间步长将所有汽车从其起点到达目的地”的问题回答为“是”，并且对后一个问题的回答为“是”，则对前一个问题的回答为“是”。 。因此，一个问题的“否”答案也暗示另一个问题的“否”答案：也就是说，这些问题是等效的。我们从给定的3SAT实例构造了多项式时间内您问题的实例，因此，如果有某种算法可以解决多项式时间内的问题，那么它也可以用于解决多项式时间内的任何3SAT实例-首先构造这样的算法问题的实例，调用此算法将其作为子例程解决，然后返回答案。因此，您的问题至少与3SAT一样困难，即NP困难。
关于algorithm - 多源-多目的地-无冲突，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39945738/