Vertex
를 기준으로 한다.
NP
란 비결정론적 튜링 기계
로 다항 시간
안에 풀 수 있는 판정 문제의 집합
이다.
최적 알고리즘이 없는 대표적인 NP(Non-deterministic-Polynomial-time)-Complete
문제이다.
NP-완전 = NP-난해(hard) and NP
NP
에 속하는 문제는 결정론적 튜링 기계
로 다항 시간
에 검증이 가능하고 그 역도 성립한다
.
결정론적 튜링 기계
로 다항 시간
안에 풀수 있는 문제는 비결정론적 튜링 기계
로도 다항 시간
안에 풀 수 있으므로 P 집합은 NP의 부분집합
이다.
원래의 출발점으로 돌아오는 경로를 특별히 Hamiltonian Cycle
이라 하는데 이중에서도 특히 최단 거리를 찾는 문제
는 알고리즘 분야에서는 Travelling Salesman Problem
로도 알려져있다.
해밀턴 경로
: 한 번만 방문하는 경로
해밀턴 순환
: 한 번만 방문하여 출발지로 돌아오는 경로
외판원 문제
: 한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로
stack
이나 재귀
를 이용하여 구현한다.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)
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
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)
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(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)
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
포기(Backtrack)
해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제(Contraint Satisfactoin Problem)
에 특히 유용하다.Backtracking
은 DFS
와 같은 방식으로 탐색하는 모든 방법을 뜻하며, DFS
는 Backtracking
의 골격을 이루는 알고리즘이다.가지치기(Pruning)
이라고 하며 트리의 탐색 최적화 문제
와 관련이 깊다.