인공지능3 인공지능 탐색 알고리즘 4-Local Search 이제부터는 현실적인 문제를 해결하는 알고리즘입니다. Local Search는 반복적인 개선알고리즘입니다. 탐색경로가 아닌 최적화 문제의 경우 쓰입니다. 우선 한가지 상태를 나열해 놓고 조금씩 수정하면서 최적의 해를 찾는 알고리즘입니다. 예를 들어 A, B, C, D, E 5개의 도시를 한번씩 최단거리로 방문하는 경우를 찾는 예에서 임의로 순서를 정해 놓습니다. 그리고 인접한 도시들의 순서를 바꿔가며 최적의 해를 찾는 방법입니다. n-queens 문제의 경우에도 쓰입니다. 아래 그래프를 보시면 어떻게 상태를 바꾸느냐에 따라 최적의 해를 풀수도 있지만 정체에 빠지기도 합니다. 1. Hill-climbing Search Hill-climbing Search는 최적의 해를 찾아 값이 증가하는 방향이나 감소하는 .. 2017. 4. 14. 인공지능 탐색 알고리즘 3-Informed Search Uninformed Search가 f(n)=g(n)+h(n)에서 h(n)=0이었다면 Informed Search는 h(n)이 0이 아닌 값을 같은 알고리즘입니다. h(n)은 heuristic 함수로 현재 노드부터 목표(goal)까지의 추정비용입니다. 1. Greedy Best-first Search 이 알고리즘은 무조건 가장 좋은 것만 선택하는 알고리즘입니다. 길찾기 문제에 유용하며 h(n)값은 목표(goal)까지의 직선거리를 사용합니다. 그리고 g(n)에 대해서는 무시하고 계산을 합니다. g(n)=0. Arad에서 Bucharest까지 가는 길찾기 문제입니다. 그리고 오른쪽은 Bucharest까지 각 노드별 추정거리 값입니다. 이 값을 h(n)으로 이용하여 문제를 푸는 겁니다. 초기 Arad에서 g(n.. 2017. 4. 14. 인공지능 탐색 알고리즘 1-기본 우선 검색 알고리즘의 종류에 대해 알아보기 전에 검색알고리즘에 대한 간단한 용어에 대해 알아 보려고 합니다. 먼저 그림을 보시면 Arad에서 Bucharest까지 가는 최적의 길을 찾으려고 합니다. 각 노드간의 숫자는 거리입니다. 따라서 가장 적은숫자(가장 빠른길)로 가는 길을 찾으려고 합니다. 위 그림처럼 초기 상태에는 Arad 밖에 없고, Arad에서 갈 수 있는길은 Sibu, Timisoara, Zerind 3군데입니다. 그리고 밑으로 내려와 갈 수 있는 길을 보면, 각각의 길에서 Arad가 또 반복되게 됩니다. 이렇게 되면 그 밑에서 무한루프에 걸리게 됩니다. 이러한 탐색(Search)을 Tree Search라고 하고, 이전에 나왔던 걸 배제하는 탐색(Search)을 Graph Search라고 합.. 2017. 4. 13. 이전 1 다음 인기글
