S.E.B 0.0.6

$ sudo park . sh·2021년 6월 21일
BFSDFS
0

SEB

목록 보기
6/9

그래프

수학 → 그래프이론 에서 그래프란 ?

  • 객체의 일부 쌍 pair 들이 '연관되어'있는 객체 집합 구조를 말함

위상수학 Topology

연속변환 Continous에 대해 불변인 기하학적 객체의 특성을 연구하는 수학의 한 분야

쾨니히스베르크의 다리문제

  • 프로이센 공국의 쾨니히스베르크에는 프레겔 강이 흐르고 있고
  • 프레겔 강에는 2개의 큰 섬이 있다
  • 이 섬과 도시를 연결하는 7개의 다리가 놓여있다
    • 7개의 다리를 한번씩만 건너서 모두 지나갈 수 있을까? 라는 문제
    • 레온하르트 오일러가 당시까지 알려진 기하학으로 풀수 없을을 알고, 미지의 영역에 그 해법있다는 사실을 간파 → 그래프 이론의 시작

오일러 경로

https://t1.daumcdn.net/cfile/tistory/13614A4A4DB2409F06

위 문제를 수학적 구조로 보면

  • A부터 D까지를 정점 Vertex, a부터 g까지는 간선 Edged 으로 구성된 그래프임을 알 수 있다.

https://t1.daumcdn.net/cfile/tistory/2165353754929F9704

  • 모든 정점이 짝수 개의 차수 Degree를 갖는다면 모든 다리를 한번 씩만 건너서 도달하는 것이 성립한다고 정의했다.
  • 오일러의 정리 Euler's Theorem
    • 칼 히어홀저Carl Hierholzer가 이를 수학적으로 증명한것을 오일러의 정리라 한다
  • 오일러 경로 Eulerian Trail / Eulerian Path
    • 오일러 모든 간선을 한 번씩 방문하는 유한 그래프 Finite Graph를 일컫는다

증명에 따르면 쾨니히스베르크의 다리는 모든 정점이 짝수개의 차수를 갖지 않으므로 오일러 경로가 아니다

해밀턴 경로

  • 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로를 말한다
  • 오일러 경로 → 간선 기준
  • 해밀턴 경로 → 정점 기준

해밀턴 경로를 찾는 문제는 최적 알고리즘이 없는 대표적인 NP-완전 Complete 문제다

  • NP 문제 중 난해Hard인 문제를 완전 문제라고 한다
  • NP 복잡도
    • NP는 Non - deterministic Polynomial time 의 약자로
    • 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합을 말한다
    • NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고
    • 그 역도 성립한다
    • 또한 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로
    • P집합은 NP 집합의 부분이다
      • 이때 P가 NP의 진부분집합(Proper Subset)인지 , 혹은 P와 NP가 같은지에 대해서는 아직 알려지지 않았다.
        • 이 문제는 P-NP 문제로 불리우며 컴퓨터 과학 분야의 대표적인 미해결 문제 중 하나이다

해밀턴 순환 Hamiltonian Path

  • 원래의 출발점으로 돌아오는 경로

외판원 문제 Travelling Salesman Problem

  • 최단거리를 찾는 문제로
    • 각 도시가 표시된 미국 지도가 있을때, 어떤 순서로 방문해야 가장 짧은 거리가 될까? (도시는 20개)
    • 다녀야하는 총 경로의 수 20! 으로 약 240경 번의 경로를 다녀봐야 가장 짧은 경로를 찾을 수 있다.
    • 이는 다이나믹 프로그래밍 기법을 활용하면 좀 더 최적화 할 수 있다.

해밀턴 문제와 외판원 문제의 NP 문제는 왜 다를까?

  • 해밀턴 경로는 한 번만 방문하는 경로
    • 해밀턴 경로가 존재 하는가? 를 묻는 문제
    • 즉, 결정 문제(Decision Problem)로 다항 시간에 정답을 검증 할 수 있다.
    • NP-문제이면서, NP-난해 문제이다
    • 이는 NP-완전 문제의 조건에 부합하므로 NP-완전 문제다
  • 해밀턴 순환은 한 번만 방문하여 출발지로 돌아오는 경로
  • 외판원 문제는 한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로
    • 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 문제
    • 결정 문제가 아니므로 NP문제가 아닐 수 있다
    • 증명할 수 있는 NP-난해 문제이지만 NP 문제가 아닐수 있으므로
    • NP-완전 문제가 아니다
    • 따라서 NP-난해 문제다

위 세 문제는 해밀턴 경로 > 해밀턴 순환 > 외판원 문제 와 같은 포함 관계를 이룬다

NP완전 문제의 조건

  • NP 문제이면
  • NP-난해 문제일때

NP난해 문제의 조건

  • NP-난해 문제이지만 NP 문제가 아닐 수 있을때
  • NP- 완전 문제가 아니므로 NP-난해 문제이다

그래프 순회 Graph Traversals

  • 그래프 탐색Search 라고도 불리며,그래프의 각 정점을 방문하는 과정을 말함

  • 그래프 순회 알고리즘

    • 깊이우선탐색 Depth-First Search
      • 19세기 프랑스의 수학자 찰스 피에르 트레모가 미로 찾기를 풀기 위한 전략을 찾다가 고안
      • BFS보다 일반적으로 널리 쓰임(코테 포함)
        • 스택 구현
        • 재귀 구현
        • 백트래킹
        • 등에 활용
    • 너비우선탐색 Breadth-First Search
      • 큐로 구현
      • 그래프의 최단 경로를 구하는 문제 등에 활용
      • 다익스트라 알고리즘으로 최단 경로 찾는 문제에서 BFS를 활용

  • 그래프 표현 방법

    • 인접 행렬 Adjacency Matrix
    • 인접 리스트 Adjacency List
      • 출발 노드를 키Key 로
      • 도착 노드를 값Value으로
        • 도착 노드는 여러개가 될 수 있으므로 리스트 형태가 된다

DFS 깊이 우선 탐색

  • 일반적으로 스택으로 구현
  • 재귀를 이용하면 더 간단하게 구현 가능
  • 코딩 테스트 시에도 재귀 구현이 더 선호되는 편

재귀를 이용한 DFS 구현 수도코드

  • 수도코드(pseudo-code)란 ?

    • Pseudo 가짜의 란 뜻으로 수도코드는 컴퓨터 프로그램이나 알고리즘이 수행해야할 내용을 우리가 사용하는 언어로 간략히 서술해 놓은것을 말함

    • 언제 쓰는가?

      • 코딩 입력을 시작하기 전, 사고를 좀더 명확히 정립하게 만들어주어 프로그램 설계하는데 도움을 줌

      • 디버그를 수정하고 코드를 재분해 하는데 걸리는 시간을 단축할 수 있음

        의사코드(pseudo-code)란?

#DFS,BFS 구현을 위한 딕셔너리 활용 그래프 구조
graph = {
	1: [2, 3, 4,],
	2: [5],
	3: [5],
	4: [],
	5: [6, 7],
	6: [],
	7: [3],
}
'''
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 is not labeled as discovered then
			recursively call DFS(G, w)

정점 v의 모든 인접 유향(Directed) 간선들을 반복하라
'''
#재귀를 이용한 dfs 함수 선언
def recursive_dfs(v, discovered=[]):
	# 방문했던 정점인 discoverd를 누적된결과로 만들기 위해 리턴하는 형태만 받아오도록 처리
	discovered.append(v)
	for w in graph[v]:
		if not w in discovered:
			discovered = recursive_dfs(w, discobered) 
	return discovered
 
f'recursive dfs: {recursive_dfs(1)}
'''
output
'recursive dfs: [1, 2, 3, 5, 6, 7, 3, 4]'
'''
  • 예시이미지 첨삭 필요

12-7 순회를 위한 그래프

  • 예시이미지 첨삭 필요
    12-8 DFS 구현 그래프

12-8 그림에서 막다른 곳에 도달할 때까지 연속으로 진행되는 탐색은 총 3 번

  • 1 → 2 → 5 → 6 까지 진행 하고 다시 되돌아감 1번
    • 다음 탐색 7 → 3 2번
      • 다시 되돌아가 마지막으로 루트까지 거슬러 올라가서 → 4를 탐샘 3번
        • 종료
  • 최종 결과
    • 1→2→5→6→7→3→4
    • [1, 2, 5, 6, 7, 3, 4]

스택을 이용한 반복 구조로 구현

#DFS,BFS 구현을 위한 딕셔너리 활용 그래프 구조
graph = {
	1: [2, 3, 4,],
	2: [5],
	3: [5],
	4: [],
	5: [6, 7],
	6: [],
	7: [3],
}
'''
반복을 이용한 DFS 구현 수도코드
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):
	discoverd = []
	stack = [start_v]
	while stack: 
		v = stack.pop()
	if v not in discoverd:
		discoverd.append(v)
		for w in graph[v]:
			stack.append(w)
	return discoverd

f'iterative dfs: {iterative_dfs(1)}'
'''
output
'iterative dfs : [1, 4, 3, 5, 7, 6, 2]'
'''
  • 재귀로 구현한코드에 비해 코드가 직관적이고, 실행 속도 또한 더 빠른 편이다
  • 재귀 구현 ↔ 반복 구현 으로 서로 바꿔서 알고리즘 구현이 가능 하다

재귀 DFS 와 스택 DFS 의 차이

  • 재귀 DFS는 사전식 순서 Lexicographical Order 로 방문
  • 반복 DFS는 역순으로 방문
    • 가장 마지막에 삽입된 노드부터 꺼내서 반복 → 인접 노드에서 가장 최근에 담긴 노드순서로 방문
    • 넓이탐색인 BFS 처럼 보일 수 있으나 깊이 우선탐색 이 맞다

BFS 너비 우선 탐색

큐를 이용한 반복 구조로 구현

#DFS,BFS 구현을 위한 딕셔너리 활용 그래프 구조
graph = {
	1: [2, 3, 4,],
	2: [5],
	3: [5],
	4: [],
	5: [6, 7],
	6: [],
	7: [3],
}
'''
큐를 이용한 BFS 수도코드
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 discovered:
				discovered.append(w)
				queue.append(w)
	return discovered

f'iterative bfs: {iterative_bfs(1)}'
'''
output
'iterative bfs: [1, 2, 3, 4, 5, 6, 7]'
'''
  • 1부터 순서대로 각각의 인접 노드를 우선으로 방문하는 너비 우선 탐색이 잘 실행되었음을 확인할 수 있다.

DFS, BFS, 백트래킹(Backtracking)

재귀 구현 불가

  • 재귀를 이용한 BFS 는 가능할까 ?
    • 재귀로 동작하지 않고, 큐를 이용하는 반복 구현만 가능하다

백트래킹 Backtracking

  • 백트래킹은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙Backtrack) 해 정답을 찾아가는 범용적인 알고리즘이다

  • 제약 충족 문제 Constraint Satisfaction Problems에 특히 유용하다

  • 백트래킹은 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다

  • 즉, DFS 는 백트래킹의 골격을 이루는 알고리즘이다

  • 앞서 설명하였듯이 백트래킹은 주로 재귀로 구현한다

    • 알고리즘마다 DFS 변형이 일어나지만, 크게 보아 모두 DFS 범주에 속한다

  • 백트래킹은 가보고 되돌아오고를 반복한다

    • 부르트 포스와 다른점
      • 한번 방문후 가능성이 없는 후보는 포기한다

-예시 이미지 첨삭필요

부르트 포스 방법은 모든 경로를 반복하여 탐색해야 한다

-예시 이미지 첨삭필요

백트래킹 방법은 가능성이 없는 후보는 포기한다

위 그림에서 처럼 가능성이 없는 후보를 포기하는 과정을 트리의 가치지기 Pruning 이라 한다

  • 이는 트리탐색 최적화 문제와도 관련이 깊다

제약 충족 문제 Constraint Satisfaction Problems

  • 백트래킹은 제약 충족 문제를 풀이하는데 필수적인 알고리즘 이다

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

  • 대표적인 제약 충족 문제 : 스도쿠 Sudoku
    • 1 - 9 까지 숫자를 한번만 넣는(제약충족조건) 정답(상태)를 찾는 문제
      • 십자말풀이
      • 8퀸 문제
      • 4색 문제
      • 배낭 문제
      • 문자열 파싱
      • 조합 최적화
      • 등등
profile
$ sudo park . sh
Searching for the Master Algorithm
이전 포스트

SEB 0.0.5

다음 포스트

S.E.B 0.0.7

0개의 댓글