[인공지능] A* 알고리즘

등록일 2003.01.09 한글 (hwp) | 11페이지 | 가격 3,000원

소개글

A* 알고리즘을 이용한 최단경로 구현입니다.

목차

◎ 정의
◎ 소스내의 추정거리 estimate 부분
◎ 대력적인 의사코드
◎ 지도의 path 부분은 0 이고 path 가 아닌 부분은 1이다. 오른쪽 그림과 비교
◎ 소스코드
◎ 결과화면

본문내용

◎ 대력적인 의사코드
루트 노드만 포함하는 길이가 0인 경로를 구성하는 큐를 형성
큐에 있는 첫번째 경로가 목표노드에 도달 하거나 큐가 공백일 때까지
a. 큐에서 첫번째 경로를 삭제하고 삭제된 경로를 확장하여 새로운 경로들을 만든다.
b. 순환을 갖는 모든 경로를 거절한다
c. 새로운 경로들이 존재하면 큐에 추가한다
d. 둘 이상의 경로가 어느 공통 노드에 도달하면 그 노드에 도달하는데 최소 비용이 들어가는 경로만 남기고 모두 제거한다
e. 그때까지 축적된 비용과 남은 비용에 대한 최저 한계 추측 값을 더한 값으로 큐를 정렬하여 최소 비용 경로를 큐의 맨 앞에 놓음. 만일 목표 노드가 발견되면 성공을 알리고, 그렇지 않으면 실패를 알린다
A* 알고리즘은 출발 노드에서 목표 노드까지 최단 거리를 갖 는 노드를 선택한다. 이를 위한 평가 함수는 F = d + h로 결정 한다. d는 출발 노드에서 현재 노드까지 최소 비용이며, h는 현재 노드에서 목표 노드까지 예측된 최소 비용이다. 만일 h는 현재 노드에서 목표 노드까지의 실제 거리를 초과하지 않는다면 A* 알고리즘은 항상 최단 거리의 경로를 찾아낸다.
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서