탐색 알고리즘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. 인공지능 탐색 알고리즘 2-Uninformed Search 탐색알고리즘은 크게 2종류가 있습니다. Uninformed Search와 Informed Search 먼저 알아볼 알고리즘은 Uninformed Search입니다. f(n)=g(n)+h(n) 일때, h(n)=0인 탐색 알고리즘입니다. Uninformed Search는 Blind Search라고도 합니다. 현재상태에서 goal까지 가는 스텝이나 경로비용(h(n))에 대한 정보가 없이, 이미 지나온 비용(g(n))에 대한 것으로만 평가하는 탐색 알고리즘입니다. 1.Breadth-first Search 이름에서 알수 있듯이 깊이가 얕은 것부터 전개해 나가는 탐색 알고리즘입니다. Frontier는 FIFO queue로 구현되는데, 위 그림에서 아래 파란색이 현재 상태의 queue입니다. 처음 A를 전개하기전엔 .. 2017. 4. 14. 이전 1 다음 인기글
