Hamiltonian Path

• Vertex를 기준으로 한다.

• NP란 비결정론적 튜링 기계로 다항 시간안에 풀 수 있는 판정 문제의 집합이다.

• 최적 알고리즘이 없는 대표적인 NP(Non-deterministic-Polynomial-time)-Complete 문제이다.

• NP-완전 = NP-난해(hard) and NP

• NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고 그 역도 성립한다.

• 결정론적 튜링 기계로 다항 시간안에 풀수 있는 문제는 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로 P 집합은 NP의 부분집합이다.

• 원래의 출발점으로 돌아오는 경로를 특별히 Hamiltonian Cycle이라 하는데 이중에서도 특히 최단 거리를 찾는 문제는 알고리즘 분야에서는 Travelling Salesman Problem로도 알려져있다.

• 해밀턴 경로 : 한 번만 방문하는 경로

• 해밀턴 순환 : 한 번만 방문하여 출발지로 돌아오는 경로

• 외판원 문제 : 한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로

Graph Traversals

DFS

• 일반적으로 stack이나 재귀를 이용하여 구현한다.

재귀 pseudo code

DFS(G, v)
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w in not labeled as discovered then
            recursively cll DFS(G, w)

재귀 Python 구현

def recursive_dfs(v, discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if w not in discovered:
            discovered = recursive_dfs(w, discovered)
    return discovered

Stack pseudo code

DFS-iterative(G, v)
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do
                S.push(w)

Stack Python 구현

def iterative_dfs(start_v):
    discovered = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    return discovered

BFS

• 반복 구조로 구현할 때는 Queue를 이용한다.
• 재귀를 사용한 구현은 불가능하다.

Queue pseudo code

BFS(G, start_v)
    let Q be a queue
    label start_v as discovered
    Q.enqueue(start_v)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
            if w is not labeled as discovered then
                label w as discovered
                w.parent := v
                Q.enqueue(w)

Queue python code

def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in discoverd:
                discovered.append(w)
                queue.append(w)
    return discovered

Backtracking

Introduction

• 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(Backtrack)해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제(Contraint Satisfactoin Problem)에 특히 유용하다.
• Backtracking은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻하며, DFS는 Backtracking의 골격을 이루는 알고리즘이다.
• 보통 재귀로 구현하며 기본적으로 모두 DFS의 범주에 속한다.
• 불필요한 후보를 제거하는 것을 가지치기(Pruning)이라고 하며 트리의 탐색 최적화 문제와 관련이 깊다.

Constraint Satisfaction Problems

Definition

• 수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제를 일컫는다.