탐색 (Lecture Note #2) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides

Slides:



Advertisements
Similar presentations
Big Data & Hadoop. 1. Data Type by Sectors Expected Value using Big Data.
Advertisements

1 탐색 (Lecture Note #4) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides by SciTech Media.
인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 탐색 (Search) 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해 에 이르기 위한 경로를 찾아가는.
UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현
이산수학 (2012년 2학기) : 강의 소개 담당교수: 류승택 (60주년 기념관: 18407)
되추적(Backtracking).
Entity Relationship Diagram
(Numerical Analysis of Nonlinear Equation)
연결리스트(linked list).
컴퓨터 프로그래밍 기초 [Final] 기말고사
Windows Server 장. 사고를 대비한 데이터 백업.
경영사례 및 영업협상 방법론.
되추적(Backtracking).
Chapter 02 순환 (Recursion).
CHAPTER 02 OpenCV 개요 PART 01 영상 처리 개요 및 OpenCV 소개.
컴퓨터과학 전공탐색 배상원.
1. 현대 생활과 응용 윤리의 필요성 2. 윤리 문제의 탐구와 실천 3. 윤리 문제에 대한 다양한 접근
그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
보조저장장치 구조(Secondary Storage Structure)
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
탐색 (Search) 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해에 이르기 위한 경로를 찾아가는 과정
9장. 특징 선택 오일석, 패턴인식, 교보문고, © 오일석, 전북대학교 컴퓨터공학.
CHAP 10:그래프 (2) 순천향대학교 하상호.
자바 5.0 프로그래밍.
프로그래밍 개요
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
뇌를 자극하는 Windows Server 2012 R2
쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색.
‘Chess’를 읽고 컴퓨터공학부 배상수.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
Metal Forming CAE Lab., Gyeongsang National University
3D 프린팅 프로그래밍 01 – 기본 명령어 강사: 김영준 목원대학교 겸임교수.
Hanoi Tower.
20 장 네트워킹과 인터네트워킹 장치 20.1 리피터(Repeaters) 20.2 브리지(Bridges)
3강. 컴퓨터와의 기본적인 소통수단 - I 연산자란? 컴퓨터와 소통하기 위한 다양한 방법들
경영과학(Ⅰ) 제9장 네트워크모형 서 론 최단경로문제 최소걸침나무문제 최대흐름문제 secom.hanbat.ac.kr.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
미분방정식.
Teaming pms.
알고리즘 알고리즘이란 무엇인가?.
약식 진리표를 이용한 타당성 증명 진리표 그리기 방법의 한계
탐색 (Lecture Note #3) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
Support Vector Machine
Ch.06 Branch-and-Bound (분기한정법) (Ch.05-7 포함)
창의적 공학 설계 < 사용자 중심의 공학설계 > : Creative Engineering Design
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
12 그리드 시스템.
탐색 (Search) 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해에 이르기 위한 경로를 찾아가는 과정
의미론적 관점 * TV에서 ‘푸른 빛이 아닌 청자빛’이란 표현을 들었을 경우
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
컴퓨터공학과 손민정 Computer Graphics Lab 이승용 교수님
실습 UBLAB.
왜 ‘프로그래밍’을 ‘비이공계 학생’이 알아야 하는가?
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
제 4 장 Record.
쉽게 배우는 알고리즘 12장. 상태공간 트리의 탐색
수치해석 ch3 환경공학과 김지숙.
1. 강의 소개 컴퓨팅적 사고와 문제해결.
수학 2 학년 1 학기 문자와 식 > 미지수가 2개인 연립방정식 ( 1 / 1 ) 연립일차방정식의 해.
 6장. SQL 쿼리.
문제풀이방식-맹목적 탐색 Ai4.
(Permutations and Combinations)
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
퍼지 이론 (Lecture Note #12) 인공지능 이복주 단국대학교 컴퓨터공학과
문제의 표현 Ai3.
이 은 Tyler 교육과정 개발 모형 이 은
Presentation transcript:

탐색 (Lecture Note #2) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides by SciTech Media 탐색 (Lecture Note #2) 인공지능 이복주 단국대학교 컴퓨터공학과

Outline 탐색 문제 해결 상태 공간 탐색 기법 휴리스틱 기법 게임 트리 기법 알파베타 탐색 문제 제약 조건 만족 문제

탐색 (Search) 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해에 이르기 위한 경로를 찾아가는 과정 탐색은 인공 지능적 문제해결에서 주요한 수단 초기의 서양 장기, 근래의 비행기표 예약 시스템 해를 찾는 과정의 효율성과 찾은 해의 적합성까지 포함 다른 분야와의 관계 (학자에 따라서) 계획 (planning)은 탐색의 특수한 경우 탐색은 학습 (learning)의 특수한 경우

문제 해결 문제 해결 예제 2.1: 하노이 타워 인간의 지적 문제해결 캄보디아 하노이 근처 사원, 64개의 원반, 5개 기둥 ‘1+2’: 인공지능적 문제 해결로 볼 수 없다. 하노이 탑 문제: 인공지능적 탐색이 필요 예제 2.1: 하노이 타워 캄보디아 하노이 근처 사원, 64개의 원반, 5개 기둥 한번에 하나의 원반 옮김, 작은 원반이 밑에 가는 경우 없음

예제: 하노이 타워 예제 2.1: 간단한 하노이 타워 문제 답: m(d1, p2), m(d2, p3), m(d1, p3) 문제해결을 위한 가능한 동작의 정의 d1 d2 동작 작용 m(d1,p1) d1을 p1으로 옮긴다. m(d1,p2) d1을 p2로 옮긴다. m(d1,p3) d1을 p3로 옮긴다. m(d2,p1) d2를 p1으로 옮긴다. m(d2,p2) d2를 p2로 옮긴다. m(d2,p3) d2를 p3로 옮긴다. p1 p2 p3 (a) 초기상태 p1 p2 p3 (b) 목표상태

문제 해결 문제 해결 직접적 기법 인공지능적 해법 주어진 초기 상태로부터 문제 해를 위한 순차적 수행을 위한 프로그래밍 예: m(d1, p2), m(d2, p3), m(d1, p3)을 프로그램 화 초기상태가 다르면 프로그램 수정 필요 1+2 를 해결하는 것과 비슷 인공지능적 방법이 아님 (거의 모든 기존의 프로그램에 의한 문제 해결방식) 인공지능적 해법 문제 상태와 요구하는 목표 상태만으로 컴퓨터가 문제 해결

탐색에 의한 문제 해결 탐색에 의한 문제 해결 문제의 해에 도달하기 위한 탐색과정을 직접 수행함으로써 보다 포괄적(일반적)이며 자동화된 해결방안 탐색에 의한 문제 해결법과 직접적 해결은 활용 영역이 다름 문제해결 과정 중에 지적 판단이 요구되는 경우 탐색기법이 유용 완벽한 의미의 지능적 기계보다는 인간의 지능이 어느 정도 개입하는 시스템 개발이 보다 현실적이다 탐색의 방식은 인간이 결정 문제해결의 최적의 방법보다 적당한 방법을 찾는 것이 쉽고, 인간의 문제 해결 방식과 상통하는 바가 있다

상태공간 (state space) 상태공간 (state space) 상태: 문제의 풀이과정 중의 고유한 요소 (상황) 상태의 집합을 상태공간 상태공간의 도입은 문제의 형식화에 유리 하노이 타워: ((p1에 있는 원반) (p2에 있는 원반) (p3에 있는 원반)) 초기상태 = ((d1,d2)()()) 목표상태 = (()()(d1,d2)) 초기상태에 연산자(규칙) 적용  상태 변이  목표상태

상태 트리 예 예제 2.1 상태 트리 예 (그림 2.2) ((d1,d2)()()) m(d1,p2) m(d1,p3)

상태공간 (state space) 상태공간 (state space) (계속) 트리 구조 뿌리노드에서 목표노드까지 도달하는 과정 각 상태: 노드 (node) 문제의 초기 상태 = 뿌리 노드 (root node) 적용 가능한 연산자나 조건 = 가지 (branch) 확장 (expansion): 부모 노드에서 자녀 노드를 얻는 것 열린 노드 (open node): 확장 전 노드 닫힌 노드 (closed node): 확장 된 노드 뿌리노드에서 목표노드까지 도달하는 과정 트리 전체의 모양을 완성할 필요는 없음 트리의 크기가 문제해결의 효율성과 관련 트리에서의 노드의 재생성은 문제 야기  그래프구조 탐색의 효율을 저하, 무한루프에 빠질 가능성

상태 그래프 예 그림 2.3 상태 그래프 예 ((d1,d2)( )( )) m(d1,p1) m(d1,p1) m(d1,p2)

탐색기법 기본적 탐색기법 어떤 연산자를 선택할 것인가 경로 선택의 고려사항 탐색 기법으로 해결할 수 있는 문제 분류 해의 경로는 짧아야 한다 탐색의 소요 경비는 적어야 한다 해가 있다면 탐색으로 반드시 찾아야 한다 탐색 기법으로 해결할 수 있는 문제 분류 경로 발견 (path finding) 문제: e.g., 8-puzzle 게임 (game) 문제: e.g., chess, 바둑 두 명의 참여자가 자신의 이익을 극대화하려 경쟁 제약조건 만족(constraint satisfaction) 문제: e.g., 8-queen 목표에 이르는 경로를 찾는 것이 아니라 목표 자체를 발견하는 것

탐색기법 무작위 탐색 (random search or blind search) 트리에 의한 탐색 무작위로 경로 선택 영국박물관 알고리즘 (BMA: British Museum Algorithm) 일반적으로 최악의 방법이라고 생각되지만 탐색 영역이 작은 (축소될 수 있는) 문제에는 유용할 수도 있다 예: 예제 2.1의 하노이 타워 (2개의 원반) 트리에 의한 탐색 일반적인 탐색기법 깊이우선 (depth-first) 탐색, 너비우선 (breadth-first) 탐색

깊이 우선 탐색 (depth-first search: DFS) 탐색 트리의 수직방향으로 점차 깊은 곳까지 목표노드를 찾아 탐색해 나가는 기법(backtracking이 존재)

깊이 우선 탐색 (depth-first search: DFS) 장점 저장공간의 수요가 비교적 작다 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수도 있다 단점 해가 없는 경로에 깊이 빠질 우려 (depth bound 설정) 해에 이르는 경로가 다수인 경우 얻어진 해가 최단 경로가 된다는 보장이 없다 예제 2.2.: 평균 탐색 노드 수 (가지: b개, 목표노드 깊이: d) 목표가 최좌측: d+1 (1) 목표가 최우측: 1+b+b2+ … +bd = (bd+1-1)/(b-1) (2) 평균: {(1) + (2)} / 2

너비우선 탐색(breadth-first search: BFS) 탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 횡방향으로 탐색을 진행해 나가는 방식

너비우선 탐색(breadth-first search : BFS) 장점 해에 이르는 경로가 다수인 경우에도 최단경로를 보장 해가 존재하면 반드시 찾을 수 있다 노드의 수가 적고 얕은 깊이에 해가 존재할 때 유리 단점 노드의 수가 늘어나면 탐색시간이 비현실적이다 기억공간에 대한 요구가 과중 예제 2.3: 평균 탐색 노드 수 (가지: b개, 목표노드 깊이: d) d 깊이 목표를 위한 평균 노드 수 = (d-1깊이까지 총 노드수) + (d 깊이에서의 노드 평균수) d-1까지의 총수: 1+b+b2+ … +bd-1 = (bd-1)/(b-1) (1) d 에서의 평균 수: (1+ bd)/2 (2)

탐색의 방향 탐색의 방향 전향 추론 (forward reasoning) 후향 추론 (backward reasoning) 초기상태에서 목표상태로 탐색 후향 추론 (backward reasoning) 목표상태에서 초기상태로 탐색 주어진 문제의 성격에 따라 좌우된다 시작 상태의 단순성과 복잡성 비교 예제 2.4: 런던을 거쳐 도버로 여행가는 길 찾기 (그림 2.6) 후향 추론이 더 유리 노리지 코벤트리 캠브리지 노스앰톤 콜체스트 마케트 옥스포드 런던 브리스톨 캔터베리 도버 솔즈베리 포츠머스 사우스앰톤 헤이스팅즈

휴리스틱 기법 휴리스틱 (heuristic) 기법 논리적으로 혹은 수학적으로 증명할 수 없으나 경험이나 직관에 의해 효율적으로 해를 얻을 수 있으리라는 기대를 갖게 하는 어떤 근거에 의한 방법 용도 정의하기 힘든 문제: 예, 직업선택, 예산지출 맹목적인 기법(blind search)으로 풀기에는 비현실적인 문제 인간의 사고형태는 대부분 휴리스틱이다 해법이 유일하지 않으며, 최적의 해를 보장할 수 없다 해의 결정에 허용치를 부과하는 방법이 유용하다

휴리스틱 기법 휴리스틱 (heuristic) 기법: TSP (Traveling Salesman Problem) n=3: A-B-C-A, A-C-B-A 같은 경로  1가지 n=4: 3 가지 n=5: 12 가지 n개의 도시 순회 방문  (n-1)!/2 n=20  60,822,550,204,416,000 가능한 경로를 구한 후 가능성 생각: 시간 너무 많이 걸림

휴리스틱 기법 외판원 방문 예에서 휴리스틱 사용 1. 임의의 도시를 출발지로 한다 2. 다음 방문 도시는 지금까지 방문하지 않은 도시 중에서 현재 위치에서 가장 가까운 도시부터 먼저 방문 3. 더 이상 방문할 도시가 없으면 끝내고, 아니면 2 로 간다

휴리스틱 기법 외판원 방문 예에서 휴리스틱 사용 위의 절차를 표 2.2 에 적용 (그림 2.8) 해: 광주, 목포, 전주, 대전, 광주

Summary 탐색 문제 해결 하노이 타워 상태 공간 탐색 기법 깊이 우선 탐색 너비 우선 탐색 휴리스틱 기법