게임인공지능 제 5 장 그래프의 비밀 2008년 4월 28일
그래프 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
그래프 연결그래프 비연결그래프 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
좀더 형식적인 기술 G={N, E} N: 노드(Node)의 집합 E: 엣지(Edge)의 집합 숫자나 문자로 레이블 연결되는 노드로 레이블 가중치(weight) 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
트리 비순환(acyclic) 그래프 그래프의 부분집합 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
그래프 밀도 밀집한(dense) 그래프 성긴(sparse) 그래프 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
다이그래프 방향그래프, digraph, DAG, … 엣지의 정의: 연결되는 노드의 순서쌍 근원(source) 노드 목적(destination) 노드 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
다이그래프 다이그래프를 이용한 무방향성 그래프 표현 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
게임 AI에서의 그래프: 항해 그래프 Navigation graph, navgraph 에이전트가 방문할 수 있는 장소(node)와 장소들 사이의 모든 연결(edge) 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
게임 AI에서의 그래프: 항해 그래프 각 타일의 중심이 node edge에는 각 지형의 정보 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
게임 AI에서의 그래프: 종속 그래프 Dependency graph 자원 관리 유형의 게임 각 자원을 만드는 비용을 각 edge에 할당 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
게임 AI에서의 그래프: 상태 그래프 State graph 시스템의 가능한 상태와 상태들 사이의 전환 시스템의 잠재적인 상태의 집합: 상태 공간 특정한 상태가 가능한지 판단 혹은 특정한 상태까지의 가장 효율적인 경로 탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
게임 AI에서의 그래프: 상태 그래프 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
게임 AI에서의 그래프: 상태 그래프 상태 공간 탐색 그래프의 분기율(branching factor) 하나(혹은 가능한 모두)의 해를 찾기 가장 적은 이동을 요구하는 해를 찾기 그래프의 분기율(branching factor) 각 부모 노드에서 퍼져 나가는 자식 노드의 평균 개수 분기율이 높은 경우 많은 메모리의 빠른 처리 속도 요구 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
그래프 클래스 구현하기 자료 구조 인접 행렬(adjacency matrix) 인접 리스트(adjacency list) 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
그래프 클래스 구현하기 인접 행렬 그래프의 연결 정보를 행렬의 각 원소에 저장 부울리언 or 실수 Sparce 그래프에 부적합 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
그래프 클래스 구현하기 인접 리스트 Space 그래프에 적합 각 노드에 인접하는 에지들의 연결 리스트 저장 게임 AI에서는 대부분 space 그래프 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
GraphNode 클래스 그래프 노드를 위한 기본 클래스 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
NavGraphNode 클래스 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
GraphEdge 클래스 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
GraphEdge 클래스 비용을 따로 계산 하는 예 cost = Distance(NodeA.Position, NodeB.Position); 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
SparseGraph 클래스 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
SparseGraph 클래스 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
SparseGraph 클래스 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
그래프 탐색 알고리즘 그래프의 모든 노드 방문하기 두 노드 사이의 경로 찾기 두 노드 사이의 최적 경로 찾기 무정보 그래프 탐색(uniformed graph search) 맹목적 탐색(blind search) 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 DFS: Depth First Search 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
깊이우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 BFS(Breadth First Search) 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
너비우선탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
비용 기반 그래프 탐색 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
에지 완화 Edge Relaxation 지금까지 발견된 가장 좋은 경로(Best Path found So Far: BPSF) 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
에지 완화 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
최단경로트리 Shortest Path Tree (SPT) 최단 경로를 나타내는 전체 그래프 G의 부트리 (sub-tree) 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 가중 그래프에서 최단 경로를 찾는 알고리즘 SPT에 source node를 추가하고 시작 아직 SPT에 없는 node까지의 최단 경로를 찾아서 SPT에 추가 모든 node로의 최단 경로가 SPT에 저장 특정 목적 node가 주어지는 경우, 해당 node가 SPT에 추가되면 알고리즘 종료 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
Dijkstra 알고리즘 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
특별한 Dijkstra A* Dijkstra A* 지금까지 경로의 비용을 최소화하여 탐색 현재 노드에서 목표까지의 추정된 비용도 고려 추정: 휴리스틱(heuristic) 예) 항해그래프: 목표까지의 직선 거리 휴리스틱 값까지 고려된 비용 F를 기준으로 큐 정렬 F = G (노드에 이르는 누적 비용) + H (휴리스틱) 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
특별한 Dijkstra A* 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
특별한 Dijkstra A* 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
특별한 Dijkstra A*: 휴리스틱 유클리디언 휴리스틱 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
특별한 Dijkstra A*: 휴리스틱 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
특별한 Dijkstra A*: 휴리스틱 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀
맨하탄 거리 휴리스틱 가로와 세로 방향 변이의 합 유클리디언 휴리스틱보다 속도가 빠름 2008-04-29 게임인공지능 - 제 5장 그래프의 비밀