중국어 우체부 문제에 대한 파티션/쌍을 어떻게 생성해야합니까?

Question

저는 Chinese Postman problem을 해결하는 클래스를위한 프로그램을 만들고 있습니다. 우리의 과제는 하드 코딩 된 그래프를 위해 그것을 해결하는 프로그램을 작성하는 것만을 요구하지만, 나는 그것을 일반적인 경우에 대해 스스로 해결하려고하고있다.

나를 괴롭히는 부분은 이상한 꼭지점에 대한 쌍의 파티션을 생성하는 것입니다. 예를 들어

, 나는 그래프에서 다음 라벨이 이상한 verticies가 있다면 : 나는 모든 가능한 짝 나는이 정점으로 만들 수/파티션을 찾을 필요가

1 2 3 4 5 6 

합니다.

n = num of odd verticies 
    k = n/2 
    i = ((2k)(2k-1)(2k-2)...(k+1))/2^n 

그래서, 위의 6 홀수 verticies 주어, 우리는 우리가 i = 15 파티션을 생성 할 필요가 있음을 알 수 :

나는 주어진 i paritions을해야 알아 냈어요.

1 2 3 4 5 6 
1 2 3 5 4 6 
1 2 3 6 4 5 
... 
1 6 ... 

그런 다음, 각 파티션에 대해, 나는 각 쌍을 가지고 그들 사이의 최단 거리를 찾아 해당 파티션 그들을 합계 : 같은

15 개의 칸막이가 보일 것이다. 쌍 사이의 총 거리가 가장 작은 파티션을 선택하고 홀수 꼭지점 사이의 최단 경로 (선택한 파티션에서 발견됨) 사이의 모든 에지를 두 배로 만듭니다.

우편 배달부가 두 번 걸어야 할 가장자리를 나타냅니다. 처음에는

은 내가이 파티션 생성하기위한 적절한 알고리즘을 일했다고 생각 :

1. 시작 증가하는 순서로 정렬 된 모든 홀수 verticies과를

   12 34 56

2. 선택 현재 최대 버텍스가있는 쌍 뒤의 쌍

3. 12 [34] 56은 동일한 선택된 쌍의 왼쪽 을 모두 남겨 1.하여 쌍 번째 자리 수를 늘리고 선택된 쌍의 세트에서 나머지 번호의 오른쪽에있는 모든 할 주문은 로 늘어납니다.

12 35 46

를 반복하지만,이 결함이 있습니다.

는

[16] .. ..

나는이 경우에 중단됩니다 밖으로 작동 알고리즘, 아닌를 생성 예를 들어, 내가 마지막에 도달 할 때 선택 쌍 (예) 가장 왼쪽 위치에있는 것을 깨달았다 시작하는 쌍의 나머지 부분은 변경하기 위해 왼쪽에 쌍이 없기 때문에 [16] 시작합니다.

그래서 드로잉 보드로 돌아갑니다.

이전에이 문제를 연구 한 사람이라면 누구나이 파티션을 생성 할 때 올바른 방향으로 나를 안내 할 수있는 정보가 있습니까?

Answer 1

재귀 알고리즘을 사용하여 파티션을 구성 할 수 있습니다.

가장 낮은 노드,이 경우 노드 1을 사용하십시오. 이것은 다른 비어있는 노드 (2 - 6) 중 하나와 쌍을 이루어야합니다. 이 노드들 각각에 대해 match 1로 생성 한 다음 나머지 4 개 요소에 대해 동일한 알고리즘을 사용하여 나머지 4 개 요소의 모든 쌍을 찾습니다. 파이썬에서

는 :

def get_pairs(s): 
    if not s: yield [] 
    else: 
     i = min(s) 
     for j in s - set([i]): 
      for r in get_pairs(s - set([i, j])): 
       yield [(i, j)] + r 

for x in get_pairs(set([1,2,3,4,5,6])): 
    print x 

이 다음과 같은 솔루션을 생성

[(1, 2), (3, 4), (5, 6)] 
[(1, 2), (3, 5), (4, 6)] 
[(1, 2), (3, 6), (4, 5)] 
[(1, 3), (2, 4), (5, 6)] 
[(1, 3), (2, 5), (4, 6)] 
[(1, 3), (2, 6), (4, 5)] 
[(1, 4), (2, 3), (5, 6)] 
[(1, 4), (2, 5), (3, 6)] 
[(1, 4), (2, 6), (3, 5)] 
[(1, 5), (2, 3), (4, 6)] 
[(1, 5), (2, 4), (3, 6)] 
[(1, 5), (2, 6), (3, 4)] 
[(1, 6), (2, 3), (4, 5)] 
[(1, 6), (2, 4), (3, 5)] 
[(1, 6), (2, 5), (3, 4)]