通过任意权重函数找到最佳路径？ [英] Find best path by arbitrary weight function?

问题描述

如何通过任意权重函数找到最佳路径？这意味着一个函数说明路径的好程度，例如边缘颜色的数量。该函数将永远不会比其所有子路径更好地对路径进行评分。

How can I find the best path by an arbitrary weight function? That means a function that says how "good" a path is, for example number of edge colors. The function will never score a path "better" than all of its subpaths.

我使用了Dijkstra-Algorithm，但使用了score函数而不是长度来确定哪个路径将接下来进行扩展，但是我不确定这是否是最佳解决方案，或者在某些情况下永远找不到最佳路径。

I used the Dijkstra-Algorithm but with the score function instead of the length determining which path will be expanded next, but Im not sure if it is the best solution or if there are cases where the best path will never be found.

推荐答案

您要描述的特定问题-在两个节点之间找到一条路径以使使用的颜色数量最少-是 NP -困难的。这意味着，假设 P ≠ NP ，没有用于解决此问题的多项式时间算法，尤其是Dijkstra的算法在这里不起作用。

The particular problem you're describing - finding a path between two nodes that minimizes the number of colors used - is NP-hard. This means that, assuming P ≠ NP, there is no polynomial-time algorithm for solving this problem, and in particular Dijkstra's algorithm won't work here.

这表明了这一点，这是基于 Paul Hankin对于相关问题的出色回答。我们将把命中集问题简化为查找图形中颜色最少的s-t路径的问题。在命中集问题中，为您提供了集合S ₁ ，...，S _n 的集合，其中包含总共m个元素和一个数字k，然后询问是否有可能选择k个元素，使每个集合S _i 至少包含其中一个。

Here's a reduction that shows this, which is based on this excellent answer by Paul Hankin for a related problem. We're going to reduce the hitting set problem to the problem of finding the least-colorful s-t path in a graph. In the hitting set problem, you're given a collection of sets S₁, ..., S_n containing a total of m elements and a number k, then asked whether it's possible to pick k elements such that each set S_i contains at least one of them.

约简如下。我们将构建一个图形并为节点上m + 1种颜色之一上色。第一种颜色（我们称其为黑色）是无意义的中性色。剩下的m种颜色将对应于集合中的不同元素。

The reduction works as follows. We're going to build a graph and color the nodes one of m+1 colors. The first color (we'll call it black) is a neutral color with no meaning. The remaining m colors will then correspond to the different elements from the sets.

我们将构造一个小配件链，每套S _i ，它对应于从S _i 中选择某些元素。每个小工具的工作方式如下：

We'll construct a chain of "gadgets," one per set S_i, which correspond to choosing some element from S_i. Here's how each gadget works:

• 每个小工具都有一个开始节点s _i ，颜色为黑色，末端为节点f _i ，也被染成黑色。


• 对于每个元素x∈ S _i ，我们给定与元素x相关联的颜色添加新节点x _i 。然后，我们从s _i 到x _i 以及x _i 和t _i 添加一条边。

• Each gadget has a start node s_i, colored black, and an end node f_i, also colored black.
• For each element x ∈ S_i, we add a new node x_i given the color associated with element x. We then add an edge from s_i to x_i and from x_i and t_i.

现在，想象一下从s _i 到t _i 的过程。为此，您需要执行两个步骤，分别访问两个黑色节点（s _i 和t _i ）和一个颜色不同的节点。遍历该有色节点对应于选择x _i 作为击中集中的元素之一。

Now, imagine walking from s_i to t_i. You have to take two steps to do this, visiting two black nodes (s_i and t_i) and one node of a different color. Walking through that colored node corresponds to selecting x_i as one of the elements of your hitting set.

要完成所有操作，请连接所有通过将f ₁ 链接到s ₂ ，f ₂ 链接到s ₃ 等来串联小工具。现在，查看从s ₁ 到f _n 的任何路径。如果您可以在图表中找到最多使用k + 1种颜色的路径，则其中一种颜色将为黑色，而其他k种颜色则对应于k个元素的集合，这些元素共同包含每个集合S中的一个元素 _i 。您已经找到了击球组合-太好了！在另一方面，假设您有一个大小为k的击中组。然后从s ₁ 转到f _n ，在每个点处进行选择，在该点处必须选择一个与击中集中的项之一相对应的有色节点。然后，您最多将使用k + 1种颜色：黑色加上击中设置的颜色。

To finish things up, wire up all the gadgets in series by linking f₁ to s₂, f₂ to s₃, etc. Now, look at any path from s₁ to f_n. If you can find a path through the graph that uses at most k+1 colors, one of those colors will be black, and the other k colors correspond to a collection of k elements that collectively contain one element out of each of the sets S_i. You've found your hitting set - great! On the flipside, imagine you have a hitting set of size k. Then walk from s₁ to f_n, making the choice at each point at which you have to pick a colored node corresponding to one of the items from the hitting set. Then you'll use at most k+1 colors: black plus the hitting set colors.

此图包含s _i 的2n个节点和t _i 个节点，再为每个集合的每个元素增加一个节点，并且边缘数量线性。因此，对于命中集的实例，它是多项式大小的，因此这是从命中集到您的问题的多项式时间缩减。

This graph contains 2n nodes for the s_i and t_i nodes, plus one node for each element of each set, with a linear number of edges. It's therefore polynomially-sized with respect to the instance of hitting set, so this is a polynomial-time reduction from hitting set to your problem.

对（可能）感到抱歉否定结果！

Sorry for the (probably) negative result!

这篇关于通过任意权重函数找到最佳路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！