在图形中查找最少的彩色路径 [英] Find least colorful path in a graph

问题描述

我要解决的问题是:

给出一个图形G =(V，E)，以使每个 edge 都用10种颜色之一着色，并用两个顶点s，t着色.

Given a graph G = (V,E) such that every edge is colored in one of 10 colors, and two vertices: s, t.

我需要找到一种算法，该算法可以产生从s到t的(最短)路径，并且所涉及的颜色最少.

I need to find an algorithm that produces a (shortest) path from s to t, that goes over a minimal amount of colors.

我的想法是将图形重复10次:

My idea was to duplicate the graph 10 times:

第一个重复项将仅包含一种颜色的边缘

The first duplicate will include only edges of one color

第二个将只包括两种颜色的边缘...等等.

The second will include only edges of two colors... and so on.

另外，我将一个外部节点:s'连接到每个重复项中的每个"s"节点.

Also, I connect an outer node: s' to every "s" node in every duplicate.

但是，发生在我身上的是，对于这种方法，我需要将图表复制的次数不是10次而是10次左右！每种颜色的组合(甚至可能是2 ^ 10?)次.

But, it has occurred to me that for this approach I need to duplicate the graph not 10 times but around 10! (or maybe even 2^10?) times for every combination of colors.

那么解决这个问题的有效算法是什么?

So what would be an efficient algorithm to solve this?

推荐答案

我不认为有一个简单的算法可以解决此问题，因为问题的一般形式是NP难题.也就是说，在任意着色的图形中，找到两个顶点之间接触最短颜色集的最短路径是NP困难的.

I don't believe there's an easy algorithm to solve this, since the general form of the problem is NP hard. That is, in an arbitrarily colored graph, finding a shortest path between two vertices which touches a minimal set of colors is NP hard.

因此，虽然可能有更好的算法，但您想解决图形的1024个变体(10种颜色的每个子集一个)的想法可能是合理的.

Thus, while it's possible there's slightly better algorithms, your idea of solving 1024 variants of the graph (one for each subset of of your 10 colors) is likely to be reasonable.

证明可以通过减少命中率设置问题来起作用.命中集问题是NP已完成，因此对问题的简化表明您的问题是NP困难.

The proof works by reducing the hitting set problem to it. The hitting set problem is NP complete, so the reduction to your problem shows your problem is NP hard.

回想一下，命中集问题需要集合X1 ... Xn，每个集合都包含来自某个宇宙U的元素，并且要求一个集合找到一个最小集合{x1，...，xk}，这样对于所有i，都存在aj这样Xi中的xj.

Recall that the hitting set problem takes sets X1...Xn, each with elements from some universe U and one is asked to find a minimal set {x1, ..., xk} such that for all i, there's a j such that xj in Xi.

图形中的颜色将是U的元素.让图形本身包含n + 1个顶点.这些将是X0(一个起始节点，下面仅出于表示方便的目的而命名)，并表示X1 ... Xn的顶点.

The colors in the graph will be elements of U. Let the graph itself consist of n+1 vertices. These will be X0 (a start node, named only for notational convenience below) and vertices representing X1 ... Xn.

对于Xi + 1中的每个x，请使用颜色x的边缘将Xi连接到Xi + 1.

For each x in Xi+1, connect Xi to Xi+1 with an edge of color x.

然后在此图中，从X0到Xn的所有路径的长度均为n，但是使用最少颜色的路径恰好是最小命中集.

Then in this graph, all paths from X0 to Xn have length n, but one that uses a minimal number of colors corresponds exactly a minimum hitting set.

请注意，这扩展了图的定义，以包括节点之间的多个边.如果这样还不行，则可以在构造图的每个边缘的中间添加一个额外的节点.

Note that this expands the definition of graph to include multiple edges between nodes. If that's not ok then one add an extra node in the middle of each edge of the constructed graph.

这篇关于在图形中查找最少的彩色路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！