그래프

Question

내가 해결하기 위해 노력하고있어 문제가 적어도 다채로운 경로를 찾기 이것이다 : 그래프 G = (V, E)을 감안할 때

모든 가장자리 10 색 중 하나에 색, 그리고되도록 두 정점 : s, t.

최소의 색상을 처리하는 s에서 t까지 (가장 짧은) 경로를 생성하는 알고리즘을 찾아야합니다.

첫 번째 중복 등 두 가지 색상 만의 가장자리 ... 등이 포함됩니다 하나 개의 색상

두 번째의 가장자리를 포함합니다 :

내 생각은 그래프 10 시간을 복제하는 것이 었습니다.

또한 외부 노드 : s '를 모든 복제본의 모든 "s"노드에 연결합니다.

그러나이 접근법에서 10 배가 아니라 10 정도의 그래프를 복제해야한다는 생각이 들었습니다. (또는 어쩌면 2^10도?) 시간의 모든 조합에 대한 색상.

그래서 이것을 해결할 효율적인 알고리즘은 무엇입니까?

Answer 1

편집 : 아래 제안 된 방법대로 작동하지 않습니다.

이 방법을 시도해보십시오. 정확성에 대해 확신하지 못합니다.

같은 색으로 같고 가장자리를 공유하는 노드를 병합하는 것으로 시작하십시오. 그러면 그래프가 축소되어 u 및 v 둘 다 서로 다른 색상을 갖는 모서리 (u-> v) 만 포함됩니다.

그런 다음 그래프의 모든 가장자리에 일정한 무게를줍니다. 그래프 위로 dijkstra를 실행하고 방문한 색상을 추적하고 새로운 색상을 방문 할 때마다 방문한 색상에서 사용되지 않은 색상의 세트가 아닌 방문한 색상의 새로운 높은 가중치로 전체 방문되지 않은 그래프를 업데이트하십시오.

Answer 2

문제의 일반적인 형태가 NP 때문에 어려운 문제를 해결할 수있는 알고리즘이 없다고 생각합니다. 즉, 임의로 채색 된 그래프에서 최소 색상 세트를 만나는 두 꼭지점 사이의 최단 경로를 찾는 것이 NP입니다.

따라서 약간 더 나은 알고리즘이 있지만 그래프의 1024 가지 변형 (10 가지 색상의 각 하위 집합마다 하나씩)을 해결하려는 아이디어는 합리적 일 수 있습니다.

증거가

증명은 타격 문제를 줄임으로써 작동합니다. 타격 세트 문제는 NP 완료이므로 문제를 줄이면 NP가 어렵다는 것을 알 수 있습니다.

타격 세트 문제는 세트 X1 ... Xn을 취합니다. 각 세트는 우주 U의 요소로 구성되며, 모든 세트 i에 대해 최소 세트 {x1, ..., xk}를 찾도록 요청받습니다. aj는 Xi의 xj이다.

그래프의 색상은 U의 요소가됩니다. 그래프 자체가 n + 1 개의 꼭지점으로 구성됩니다. 이들은 X0 (아래의 표기법의 편의를 위해 명명 된 시작 노드)와 X1 ... Xn을 나타내는 정점이됩니다.

Xi + 1의 각 x에 대해 Xi를 색상 x의 가장자리로 Xi + 1에 연결하십시오.

이 그래프에서 X0에서 Xn까지의 모든 경로는 길이가 n이지만 최소 색상 수를 사용하는 경로는 정확히 최소 타격 세트와 일치합니다.

노드 사이에 여러 가장자리가 포함되도록 그래프의 정의를 확장합니다. 그렇지 않은 경우 생성 된 그래프의 각 가장자리 중간에 추가 노드를 추가합니다.