나는 무엇보다 먼저 대학 과제에 대해 명확히하고 싶습니다. 알고리즘을 구현하는 데 도움이되는 정보를 찾고 있습니다. https://www.labri.fr/perso/dorbec/AA/projet-uno.pdf가장 긴 경로에 대한 색상 코딩 알고리즘
은 기본적으로 우리가 수에 대한 카드의 색상과 다른를 나타내는 2 INT 하나로 표시 "카드"의 세트를 가지고 : 그래서 나는 여기에서 찾을 수 캠이 할당을했습니다. 할 일은 UNO 게임처럼 가장 긴 카드 순서를 찾는 것입니다. 다음 카드가 있거나 같은 색이거나 동일한 번호가있는 게임입니다. 일련의 알고리즘이 저주 중에 구현되었지만 마지막으로 구현해야하는 것은 "색상 코딩"이며 현재는 시간이 부족하고 작동 방식이 아직 명확하지 않습니다. 형식을 유지하기 위해 여기에 텍스트의 이미지를 넣을 것입니다. 
에 어떤 도움
감사합니다.
도움이 될 것 같아요. 문제는 가장 긴 경로 문제로 쉽게 변형 될 수 있습니다. 길이 k의 경로를 찾으려면 오랫동안 해결하기가 정말 어려웠습니다. k가 상대적으로 작을지라도, log (n)이라고하면, 사람들은 여전히 그것이 다항식 시간에 가능하지 않다고 생각했다.
기본 아이디어 : 그래프를 많이 색칠하고 우연히 길이가 k 인 경로를 색칠하기를 바랍니다. 글쎄, 그 확률은 매우 작지만, 당신이 그것을 여러 번 반복한다면 실제로 확률은 매우 커집니다.
하지만 먼저 그래프에 색상이있는 경로가 있다고 가정 해 보겠습니다. "색깔"은 무엇을 의미합니까? Colored는 길이가 k-1 인 k 노드가있는 경로가 k 개의 다른 색상으로 채색되어 있음을 의미합니다. 노드 1 (색상 1)에서 시작하면 어떻게됩니까? 당신은 당신의 이웃을보고 그들이 당신과 다른 색깔을 가지고 있는지 볼 것입니다. 그럴 경우, P (1)이라는 세트에 추가하십시오. 당신은 이웃들 중 하나와 계속해서 그들이 색깔 세트에 나타나지 않은 색깔을 가지고 있는지 볼 것입니다. 아직 보지 못했던 새로운 색상을 찾거나 k-1 색상에 이르거나 이미 본 색상 중 하나가 노드 중 하나에 있음을 알면이 작업을 수행 할 수 있습니다. 마지막 경우에는 임무를 중단하고 모든 것이 여전히 좋은 곳으로 돌아갑니다.
중요 : 노드의 색상을 지정합니다. 길이 i의 경로는 i + 1 노드와 i 에지를가집니다.
공식 형식 : P i (v) : = {S는 ([k] i + 1을 선택하십시오. v에서 끝나는 S의 색상으로 채색 된 경로가 있음} P는 경로가 아닙니다. P는 우리가 호출하는 몇 가지 색상 집합을 포함합니다. 이 경우 S는 숫자가 아닙니다. 그것은 다른 색깔의 카디널리티 i + 1의 부분 집합입니다. 예 : P 3 (v) = {{녹색, 빨간색, 검은 색, 노란색}, {분홍색, 주황색, 회색, 노란색}, {...}}처럼 보일 수 있습니다. "노란색"이 두 번 나타납니다. 몇 가지 하위 세트를 계속 사용했다면 "노란색"이 모든 세트에 등장했을 것입니다. 왜? 왜냐하면 그것은 우리의 최종 노드 v! 그래서 P i (v)는 길이 i의 한 경로가 채색되는 모든 다른 색상의 적어도 한 세트 S를 유지합니다.이 경로는 v!
그 의미는 무엇입니까? 우리가 P k-1 (v)를 계산할 수 있고 그 집합이 비어 있지 않다면. 길이 k의 경로가 존재합니다. 굉장해.
그러나 우리는 어떻게 P k-1 (v)를 계산합니까? 그리 어렵지 않습니다. P i (v)를 계산하려면 다음을 입력하십시오. 우리는 무엇이 필요한가? P i-1 (x)가 필요합니다. 엑스? 왜? x는 v의 이웃입니다. ---> g ----> y ---> o -----> x ------> v {녹색, 노란색, 주황색, x의 색상}은 P의 한 부분 집합이라고 말합니다. i-1 (x)이다. R이라고 부르 자. 기억해? P i-1 (x)는 많은 다른 세트를 가질 수있다. {{녹색, 빨간색, 검은 색, 노란색}, {분홍색, 주황색, 회색, 노란색}, {...}}처럼 보일 수 있습니다!
그러면 R과 x, v와의 관계는 정확히 무엇입니까? R은 최대 x까지 이어지는 길이 i-1의 색상 경로를 나타내는 색상 집합입니다. x의 이웃 인 꼭지점 v가 아직 R에 나타나지 않은 색상을 가지고 있다면 R에 추가 할 수 있습니다. 그러나 이제 R은 하나의 색상을 얻었습니다. 크기 | R |은 이제 i + 2입니다. P i (v)의 새로운 부분 집합 중 하나 여야합니다! 왜 지금 v입니까? 음, 경로를 하나의 색상으로 확장하여 해당 세트에 저장하는 것이 더 좋습니다! 그래서 지금까지 본 것 : - 당신은 그 자체가 i + 1 많은 색을 포함하는 부분 집합 S를 포함하는 집합 P i (v)를 가지고 있습니다 (v를 잊지 말것) - 집합 P k -1 (v), 길이 k의 경로가 있고 맥주를 마실 수 있습니다.- P i (v)는 P i-1 (x)에 의해 계산 될 수 있으며, 여기서 x는 v! 그리고 좋은 부분은 우리가 R이라고 부르는 P i-1 (x)의 하위 집합 중 하나에 v의 색이 나타나는지 여부를 확인해야한다는 것입니다.
어떻게 계산합니까? 처음부터? V의 색상 인 P 0 (v)에서 시작합니다. 그런 다음 v의 각 이웃 x에 대해 P 1 (v)를 계산합니다. 당신이 i-1 것을 떠올리면 P 1 (v)는 단지 P 1-1 (x)입니다. P 0 (x)는 다시 x의 색상입니다. x와 v의 색깔이 같지 않다면, 그들은 단지 P 1 (v)의 첫 부분 집합을 형성했습니다! P 2 (v)는 P 0 (y)에 의해 다시 계산되는 P 1 (x)를 계산함으로써 계산됩니다. 여기서 y는 x의 이웃입니다. 우리는 P k-1 (v)에 도달하지 않은 한 계속됩니다.
복잡도 : 이것은 O (2^kkm)에서 실행됩니다. 여기서 m은 가장자리의 수이고 k는 경로의 길이입니다. 이제이 알고리즘을 다항식 시간에 사용하여 k = log n long 인 경로를 검색 할 수 있습니다. 그것이 더 크다면 불행하게도 더 이상 다항식이 아닙니다.
이제 우리는 다항식 시간에 "긴"경로를 찾는 알고리즘을 가지고 있습니다. 하지만 기다려. 경로가 채색되어 있다면 그렇게 할 수 있습니다! 내가 살고있는 곳을 모르지만 세상에는 기본적으로 색이 지정되어 있지 않으며 특히 다른 색의 경로가 아닙니다.
우리가해야만합니다. k 색으로 k 길이의 경로를 채색 할 확률은 얼마입니까?
k가 있습니다. k 가지 색상으로 그래프를 색칠하는 여러 가지 방법. 그러나 k 개의 다른 색상으로 경로를 색칠하는 k^k 가지 방법이 있습니다. 색상이 여러 번 나타날 수 있습니다. 예 : yellow = y 및 green = g을 사용하면 2! = 2 옵션이 있습니다. 색상은 (y, g) 또는 (g, y)가 달라야합니다. 색상이 다를 필요가 없으면 k^k = 2^2 = 4 옵션을가집니다. (y, y), (g, g) 그리고 이미 본 것들. 그래서 Pr [경로는 diff로 채색됩니다. colors] = k!/k^k이며, 이것은 e^-k보다 크다. 이것은 1/e^k와 같다. 확률이 매우 작다는 것에 동의 하시겠습니까? 최초로 성공을 거두려는 예상 횟수는 얼마입니까? 이것은 기대 값이 1/p = e^k 인 기하 분포입니다. e^k 시도 후에 우리는 처음으로 색깔이있는 경로가 있기를 희망 할 수 있다고 생각합니다. 때로는 적지 만 때때로 더 그렇습니다. prob.한 번의 시도에서 실패한 것은 1-e^-k이므로 매우 큰 것입니다. 하지만 우리가 이것을 Te^k 번 실행하면 prob가됩니다. 의 연속적인 실패는 매우 작아진다 : (1-e^-k)^Te^k 따라서, prob이다. 우리는 Te^k 시도 후에 성공할 것이고, 1-e^-T보다 크다. 그리고 그것은 매우 작습니다.
알고리즘의 모양은 어떻게됩니까? 1) 그래프를 k 가지 색상으로 무작위로 색상을 지정합니다. 2) 색깔이있는 경로가 있는지 확인하는 알고리즘을 실행하십시오. 하나가 있다면 그것을 반환하십시오. 그냥 계속하지 않으면. 3) Te^k 시간 동안 1 단계와 2 단계를 반복하십시오. (그것은 재미, 나를 믿어). 실제로 그렇지 않습니다. 컴퓨터로 해보십시오.
이 유형의 알고리즘을 몬테카를로 유형 무작위 알고리즘이라고합니다. 그것의 런타임은 O (Te^k * 2^k * km)이고 false가 될 확률은 "경로가 없습니다 (실제로는 하나가 있습니다)"가 e^-T보다 작습니다 (다시, 매우 작습니다.) 그리고 다시, k = log n에 대해이 무작위 알고리즘은 다항식 런타임을 얻습니다!