3.8 Back Tracking Algorithm(역추적 알고리즘) - 3.8.1 Finding Hamiltonian Paths(해밀턴 경로)

CS - 3. Common Algorithms - 3.8 Back Tracking Algorithm - 3.8.1 Finding Hamiltonian Paths

역추적 알고리즘 - 해밀턴 경로

Back Tracking Algorithm

Back tracking algorithms are used to solve problems that can be broken down into smaller sub-problems. The algorithm tries to solve each sub-problem and if it fails, it backtracks and tries to solve the sub-problem in a different way.

역추적 알고리즘은 더 작은 하위 문제로 나눌 수 있는 문제를 푸는 데 사용됩니다. 알고리즘은 각 하위 문제를 해결하려고 시도하고 실패하면 역추적하여 다른 방식으로 하위 문제를 해결하려고 시도합니다.

 

Finding Hamiltonian Paths

Hamiltonian paths are paths that visit every node in a graph exactly once. They are named after the famous mathematician Hamilton. Hamiltonian paths are a special case of Hamiltonian cycles, which are cycles that visit every node in a graph exactly once.

해밀턴 경로는 그래프의 모든 노드를 정확히 한 번만 방문하는 경로입니다. 유명한 수학자 해밀턴의 이름을 따서 명명되었습니다. 해밀턴 경로는 그래프의 모든 노드를 정확히 한 번씩 방문하는 주기인 해밀턴 사이클의 특수한 경우입니다.

 

 

1. Hamiltionian Paths? 해밀턴 경로?

해밀턴 경로( Hamiltionian Paths)는 그래프 이론에서 볼 수 있는 개념입니다. 이는 그래프 내의 모든 정점을 정확히 한 번씩 방문하는 경로를 의미합니다. 이러한 경로를 찾는 방법을 다룹니다.

 

2. Back Tracking Algorithm (백트래킹 알고리즘)

백트래킹 알고리즘은 문제의 해결 방법을 찾기 위해, 가능한 모든 해를 깊이 우선 탐색을 하는 알고리즘입니다. 만약 특정 단계에서 해결책이 아닌 경우로 판단되면, 알고리즘은 '이전 단계로 돌아가서(Back Tracking)' 다른 경로를 탐색 하게 됩니다.

 

In Python

def hamiltonian(G, start=None, visited=None, path=None):
    # visited가 None일 경우, 새로운 set을 생성
    # 이 set은 이미 방문한 노드를 저장하기 위한 용도
    if visited is None:
        visited = set()

    # path가 None일 경우, 시작 노드만을 포함하는 리스트를 생성
    # 이 리스트는 경로를 저장하기 위한 용도
    if path is None:
        path = [start]

    # 시작 노드를 방문한 노드 set에 추가
    visited.add(start)

    # 만약 모든 노드를 방문했다면, 현재까지의 경로를 반환
    if len(visited) == len(G):
        return path

    # 시작 노드의 이웃 노드를 순회
    for neighbor in G[start]:
        # 만약 이웃 노드가 아직 방문하지 않았다면,
        if neighbor not in visited:
            # 이웃 노드를 시작 노드로 하여 재귀적으로 함수를 호출
            # 이 때, 방문한 노드 set와 경로 리스트는 복사하여 전달
            result_path = hamiltonian(G, neighbor, visited.copy(), path + [neighbor])

            # 만약 결과 경로가 존재한다면, 그 경로를 반환
            if result_path:
                return result_path

    # 모든 이웃 노드를 순회한 후에도 해밀턴 경로를 찾지 못했다면, None을 반환
    return None

 

 

G = {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2]}

이러한
G = {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2]} 간단한 그래프의 해밀턴 경로를 살펴보자.

 

0 - 1 - 3 -2 로 모든 노드를 연결된 순서로 돌았다. 

 

좀더 복잡한 그래프를 예시로 보자.

 

G = {0: [1, 5], 1: [0, 2], 2: [1, 3, 4], 3: [2, 4, 7], 4: [2, 3, 5, 6], 5: [0, 4, 6], 6: [4, 5, 7], 7: [3, 6]}

 

 

여러 해밀턴 경로가 있을 수 있다.

 

 

활용

 

해밀턴 경로는 여러 문제에 활용 됩니다.

 

가장 유명한 문제인

외판원 문제(Travelingman Problem) 

 외판원이 판매를 위해 방문해야하는 곳을 모두 들르면서 가장 짧은 경로를 찾는 문제입니다.

 

경로 최적화 

- 창고의 적재 최적화, 설계 회로등등 다양한 곳에 사용될 수 있습니다.