쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색 http://academy.hanb.co.kr.

Slides:



Advertisements
Similar presentations
1 ‘ 우리나라의 주요공업 ’ - 정도웅, 주민혁, 안수진, 백경민, 엄다운, 박경찬 -.
Advertisements

14 장. 그래프 알고리즘 Internet Computing KUT Youn-Hee Han.
탐색 (Lecture Note #2) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides
알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
이진 나무 구조 강윤섭 2008년 5월 23일.
주요 내용 기본 용어 이진 트리(binary tree) 이진 탐색 트리(binary search tree)
15 장. 알고리즘의 설계 알고리즘 설계 학습목표 기본 패턴 패턴의 한계점 일곱 가지 패턴의 알고리즘 설계 기법을 이해한다.
Shortest Path Algorithm
공부할 내용 조상들이 살던 곳 자연과 잘 어울리는 한옥 지방에 따라 서로 다른 집의 모양 섬 지방의 집
사랑, 데이트와 성적 자율성 :데이트 성폭력!!! 성폭력예방교육 전문강사 / 여성학 전공 신 순 옥.
퇴계와 율곡의 사회사상 비교 남 일 재 동서대학교 교수/ 정치학 박사 1. 퇴계 이황과 율곡 이이의 약전(略傳)
되추적(Backtracking).
501. 군인들의 세상 502. 민정 이양과 한일회담 이선용.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
CHAP 10:그래프 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
자료구조론 10장 그래프(graph).
되추적(Backtracking).
쉽게 배우는 알고리즘 9장. 그래프 알고리즘.
Chapter 10 그래프(graph) SANGJI University Kwangman KO
강의 #9 그래프(Graph).
컴퓨터과학 전공탐색 배상원.
알고리즘(Algorithm) – Backtracking (되추적)
그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문
CHAP 10 : 그래프.
CHAP 10: 그래프(part 2) 순천향대학교 하상호.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
C언어 응용 제 11 주 그래프1.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
9장. 특징 선택 오일석, 패턴인식, 교보문고, © 오일석, 전북대학교 컴퓨터공학.
CHAP 10:그래프 (2) 순천향대학교 하상호.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
쉽게 배우는 알고리즘 7장. 상호 배타적 집합의 처리.
8장. 상호 배타적 집합의 처리.
주요 내용 왜 그래프인가? 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색.
Homework #5 (1/3) Backtracking, Branch-and-Bound
시뮬레이션 기반 가상 보조기구 알고리즘 최적화
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
정치개혁의 가능성 논의 권력구조 개편을 통하여 본 -개헌을 통한 정부형태의 변화를 중심으로 [한국정치론] 윤성이 교수님
20 장 네트워킹과 인터네트워킹 장치 20.1 리피터(Repeaters) 20.2 브리지(Bridges)
게임인공지능 제 5 장 그래프의 비밀 2008년 4월 28일.
수학 2 학년 2 학기 도형의 성질 > 삼각형의 성질 ( 2 / 3 ) 삼각형의 외심 성질.
트리.
수학10-나 1학년 2학기 Ⅱ.부등식의 영역 1. 부등식의 영역(2/5) 부등식 영역 수업계획 수업활동.
알고리즘 알고리즘이란 무엇인가?.
제 7 장 네트워크 이론과 응용.
노년기 발달 장안대 행정법률과 세류반 정 오 손
0-1 Knapsack – 개선된 BFS 기반 알고리즘
알고리즘 강의 슬라이드 5 되추적 Backtracking
문서 클러스터링 일본언어문화학과 서동진.
보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)
Ch.06 Branch-and-Bound (분기한정법) (Ch.05-7 포함)
5장. 선택 알고리즘.
 Branch-and-Bound (분기한정)
태국 문학 욜라다 왓짜니 싸란차나 팟차라와라이 끼따야펀 르앙다우 타니다.
Homework #5 (1/3) Backtracking, Branch-and-Bound
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
[CPA340] Algorithms and Practice Youn-Hee Han
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
컴퓨터공학과 손민정 Computer Graphics Lab 이승용 교수님
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
워밍업 실뭉치 전달게임.
제 9 장 그래프.
음파성명학 최종욱.
[CPA340] Algorithms and Practice Youn-Hee Han
문제풀이방식-맹목적 탐색 Ai4.
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
C++ Espresso 제15장 STL 알고리즘.
Presentation transcript:

쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색 http://academy.hanb.co.kr

12장. 상태공간 트리의 탐색 인공지능은 미국인들 특유의 천진난만함의 표현이다. -에드거 다익스트라

학습목표 상태공간 트리가 무엇인지 이해한다. 백트래킹 기법의 작동 원리를 이해한다. 한정분기의 작동 원리를 이해하고, 백트래킹에 비해 장점이 무엇인지 이해하도록 한다. A* 알고리즘의 작동 원리를 이해하고, 어떤 문제들이 A* 알고리즘의 적용 대상인지 감지하도록 한다.

State-Space Tree State-space tree (상태공간트리) 이 장에서 배우는 세가지 상태공간 탐색 기법 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리 이 장에서 배우는 세가지 상태공간 탐색 기법 Backtracking Branch-and-bound A* algorithm

TSP의 예 1 1 1 2 2 2 4 4 4 3 3 3 5 6 5 6 5 6 TSP 예제 해의 예 최적해

TSP와 Adjacency Matrix의 예 1 2 3 4 5 1 3 4 2 5 10 25 14 21 11 30 8 9 7 18 10 30 25 14 21 18 7 9 8 11 3 1 2 3 4 5

사전적 탐색의 State-Space Tree 1 1 2 12 22 32 1-2 1-3 1-4 1-5 3 6 9 39 1-2-3 1-2-4 1-2-5 … … … 1-5-4 4 5 7 8 10 11 40 41 1-5-4-3 1-2-3-4 1-2-3-5 1-2-4-3 1-2-4-5 1-2-5-3 1-2-5-4 1-5-4-2 … 48 44 61 54 45 40 63 63 1-2-3-4-5-1 1-2-3-5-4-1 1-2-4-3-5-1 1-2-4-5-3-1 1-2-5-3-4-1 1-2-5-4-3-1 1-5-4-2-3-1 1-5-4-3-2-1

Backtracking DFS 또는 그와 유사한 스타일의 탐색을 총칭한다 Go as deeply as possible, backtrack if impossible 가능한 지점까지 탐색하다가 막히면 되돌아간다 예 Maze, 8-Queens problem, Map coloring, …

Maze maze Branching tree 그래프로 모델링한 미로 S T 1 2 3 S 4 4 5 3 5 T 6 T 1 2 7 8 9 7 9 S Branching tree 그래프로 모델링한 미로 8

maze(v) { visited[v] ← YES; if (v = T) then {print “성공!”; exit( );} for each x ∈ L(v) ▷ L(v) : 정점 v의 인접 정점 집합 if (visited[x] = NO) then { prev[x] ← v; maze(x); }

Coloring Problem Graph에서 인접한 vertex는 같은 색을 칠할 수 없다 k 개의 색상을 사용해서 전체 graph를 칠할 수 있는가?

Coloring Problem의 예: Map Coloring 1 1 4 2 2 3 4 3 6 5 6 5 (c) 연결관계를 정점과 간선으로 나타낸 것 (d) (c)와 동일한 그래프

if (i = n) then {return TRUE;} else { result ← FALSE; kColoring(i , c) ▷ i: 정점, c: color ▷ 질문: 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색 c로 칠하려면 k 개의 색으로 충분한가? {   if (valid(i, c)) then { color[i] ← c; if (i = n) then {return TRUE;} else { result ← FALSE; d ← 1;  ▷ d: color while (result = FALSE and d ≤ k) { result ← kColoring(i+1, d);   ▷ i+1: 다음 정점   d++; } return result; } else {return FALSE;}

▷ 정점 i와 j 사이에 간선이 있고, 두 정점이 같은 색이면 안된다 valid(i, c) ▷ i: 정점, c: color ▷ 질문: 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색 c로 칠하려면 이들과 색이 겹치지 않는가? { for j ← 1 to i-1 { ▷ 정점 i와 j 사이에 간선이 있고, 두 정점이 같은 색이면 안된다 if ((i, j) ∈ E and color[j] = c) then return FALSE; } return TRUE;

State-Space Tree 1 1, 1 2 3 2, 1 2, 2 4 5 3, 1 3, 2 TSP-사전식탐색.wmf 1 6 7 4, 1 4, 2 2 3 4 8 5, 1 5 6 9 10 11 6, 1 6, 2 6, 3

Branch-and-Bound 분기branch와 한정bound의 결합 Backtracking과 공통점, 차이점 분기를 한정시켜 쓸데없는 시간 낭비를 줄이는 방법 Backtracking과 공통점, 차이점 공통점 경우들을 차례로 나열하는 방법 필요 차이점 Backtracking – 가보고 더 이상 진행이 되지 않으면 돌아온다 Branch-&-Bound – 최적해를 찾을 가능성이 없으면 분기는 하지 않는다

P6 P1 P6 P1 P5 P5 P2 P2 P4 P4 P3 P3 어느 시점에 가능한 선택들 최적해를 포함하지 않아 제외하는 선택들

TSP 예제를 대상으로 한 Branch-and-Bound 탐색의 예 (State-Space Tree) 1 1 (33) 0+33 10 19 18 2 1-2 1-3 1-4 1-5 (33) 10+23 (33) 10+23 TSP-한정트리.wmf (53) 30+23 (48) 25+23 6 9 3 17 11 14 1-2-3 1-2-4 1-2-5 1-3-2 1-3-4 1-3-5 (35) 19+16 (37) 24+13 (44) 31+13 (33) 20+13 (33) 17+16 (44) 28+16 7 8 4 5 12 13 15 16 1-2-3-4 1-2-3-5 1-2-5-3 1-2-5-4 1-3-4-2 1-3-4-5 1-3-5-2 1-3-5-4 1-2-3-4-5-1 1-2-3-5-4-1 1-2-5-3-4-1 1-2-5-4-3-1 1-3-4-2-5-1 1-3-4-5-2-1 1-3-5-2-4-1 1-3-5-4-2-1 48 44 45 40 52 40 58 43

A* Algorithm Best-First-Search 각 정점이 매력함수값 g(x)를 갖고 있다 방문하지 않은 정점들 중 g(x) 값이 가장 매력적인 것부터 방문한다 A* algorithm은 best-first search에 목적점에 이르는 잔여추정거리를 고려하는 알고리즘이다 Vertex x로부터 목적점에 이르는 잔여거리의 추정치 h(x)는 실제치보다 크면 안된다

Shortest Path 문제 Remind: Dijkstra algorithm A* algorithm에서는 목적점이 하나다 시작점은 하나 시작점으로부터 다른 모든 vertex에 이르는 최단경로를 구한다 (목적점이 하나가 아니다) A* algorithm에서는 목적점이 하나다

Dijkstra Algorithm의 작동 예 30 23 25 24 18 28 20 29 39 40 16 10 19 17 30 23 25 24 18 28 20 29 39 40 16 10 19 17 ∞ s t 다익스트라1.wmf 30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17 30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17

30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17 30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17 41 다익스트라2.wmf 30 23 25 24 18 28 20 29 39 61 40 16 10 19 17 41 64 50 30 23 25 24 18 28 20 29 39 ∞ 40 16 10 19 17 41 50

다익스트라2.wmf 19 19 10 10 30 24 30 24 20 10 30 20 10 30 17 16 41 41 20 17 16 20 23 18 23 18 17 25 23 61 17 25 23 28 61 28 20 28 20 28 17 64 17 64 25 39 25 39 25 29 40 25 29 40 50 50

A* Algorithm의 작동 예 ∞ ∞ 추정 잔여거리 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 19 24 20 10 61 24 40 20 10 30 16 17 20 52 19 23 18 25 28 20 28 68 34 17 39 19 52 25 29 A-star1.wmf 40 39 (71) ∞ 19 19 (70) 10 ∞ ∞ 24 30 24 20 10 30 20 10 30 ∞ 16 ∞ 16 ∞ 17 20 17 20 23 18 23 18 ∞ 25 ∞ ∞ 17 25 23 ∞ 28 20 28 28 20 28 (85) 17 ∞ (57) ∞ 17 ∞ 25 39 39 25 29 40 (77) 25 29 40 ∞ ∞

추정잔여거리를 사용함으로써 탐색의 단계가 현저히 줄었다 (71) (71) 19 (70) 19 (70) 10 10 30 24 30 24 20 10 30 (60) 20 10 30 (60) A-star2.wmf 16 41 41 17 20 17 16 20 23 18 23 18 17 25 23 28 61 17 25 23 61 28 20 28 20 28 (85) (57) (85) (57) 17 ∞ 17 ∞ 25 25 39 39 (77) 25 29 40 (77) 25 29 40 50 50 (89) (89) 추정잔여거리를 사용함으로써 탐색의 단계가 현저히 줄었다

TSP 예제를 대상으로 한 A* Algorithm 탐색의 예 (State-Space Tree) 1 1 (33) 0+33 2 3 1-2 1-3 1-4 1-5 (33) 10+23 TSP-A-Star.wmf (33) 10+23 (53) 30+23 (48) 25+23 7 4 5 6 1-2-3 1-2-4 1-2-5 1-3-2 1-3-4 1-3-5 (35) 19+16 (37) 24+13 (44) 31+13 (33) 20+13 (44) 28+16 (33) 17+16 8 1-2-3-4 1-2-3-5 1-2-5-3 1-2-5-4 1-3-4-2 1-3-4-5 1-3-5-2 1-3-5-4 1-2-3-4-5-1 1-2-3-5-4-1 1-2-5-3-4-1 1-2-5-4-3-1 1-3-4-2-5-1 1-3-4-5-2-1 1-3-5-2-4-1 1-3-5-4-2-1 48 44 45 40 52 40 58 43

A* Algorithm이 첫 Leaf Node를 방문하는 순간 종료되는 이유 영역과 영역의 leaf node들이 모두 40 보다 커질 수 없는 이유를 이해할 것 1-5 (48) 25+23 A-Star-따지기 1-2-5 1-3-5 (33) 20+13 (35) 19+16 … 1-2-5-3 1-2-5-4 … 1-3-5-2 1-3-5-4 … 125341 125431 125341 125431 152351 152431 153241 153421 154231 154321 45 40 58 41 방문된 leaf node 계산된 leaf node들 계산되지 않은 leaf node들

Thank you