*병* 스토어

*병*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

1개
전체 판매량

6개
최근 3개월 판매량

0개
자료후기 점수

-
자료문의 응답률

-

전체자료 1개

A* 알고리즘을 통한 최단경로탐색 프로그램

졸업연구 논문A* 알고리즘을 이용한최단 경로 탐색지도교수 :학 번 :이 름 :컴퓨터공학2007. 12.20요 약 문A* 알고리즘을 이용한최단 경로 탐색컴퓨터공학전공전자정보학부차량의 수는 계속 증가하고 있고, 이로 인해 네비게이션의 수요 또한 날이 갈수록 높아만 가고 있는 실정이다. 이런 상황에서 사용자에게 정확하고 높은 신뢰도를 갖는 네비게이션 서비스를 제공하기 위해 다양한 기법이 사용되고 있다. 본 논문에서는 최단 경로를 찾기 위해 A* 알고리즘을 선택하였다. A* 알고리즘은 최적우선탐색 방식이 적용된 알고리즘으로 보다 빠르게 최단 경로를 탐색할 수 있고, 휴리스틱 방식을 통해 정확도를 높였다. 본 논문에서는 휴리스틱 값을 위해 각 노드들에 좌표값을 설정해 주었다.< 목 차 >1. 서 론 ---------------------------- 12. 관 련 연 구 ---------------------------- 23. 연 구 내 용 ---------------------------- 34. 구 현 ---------------------------- 45. 결론 및 향후과제 ---------------------- 126. 참 고 문 헌 --------------------------- 131. 서 론지속적으로 늘어나고 있는 네비게이션에 대한 수요에 걸맞게 사용자에게 질 높은 서비스를 제공해야 한다. 정확도와 신속성을 높이기 위해 본 논문에서는 A* 알고리즘을 통해 최단 경로 탐색을 구현하였다. 가장 널리 쓰이고 있는 A* 알고리즘을 직접 구현하면서 본 알고리즘의 원리를 이해하고 더 나아가 수정작업을 거쳐 더욱 만족할만한 결과를 얻을 수도 있을 것이다. 본 논문에서는 좌표만을 통해서 휴리스틱 값을 얻지만 좌표뿐만 아니라 그 외 다양한 요소들, 즉 날씨, 도로상황, 선호도 등을 고려하여 정확도 및 신뢰도를 높일 수 있다.2. 관련연구▣ 다익스트라 알고리즘한 정점에서 다른 모든 정점으로의 최단경로를 구하는 알고리즘-최단경로 찾기[1] 시작 정점에서 가장 인접한 정점 검색. 그 정점까지 거리가 최단거리이다. 지금까지 최단거리가 알려진 정점은 2개(자기 자신과 지금 찾은 정점)가 된다. 최단거리가 알려진 정점들의 집합을 S라 하자.[2] 집합 S에 포함되지 않은 정점 중에서 시작 정점으로부터 가장 가까운 정점을 찾는다. 이 새로운 정점은 집합 S에 바로 이웃한 정점들 중 하나일 것이다. 그 정점까지 거리는 최단거리이며, 그 정점을 집합 S에 포함시킨다.[3] 새로운 정점이 없을 때까지, 즉 모든 정점이 집합 S에 포함될 때까지 과정을 반복한다.▣ 힙A* 알고리즘을 구현하는데 있어서 열린목록(방문할 노드들을 저장함)을 만들기 위해 우선순위 큐를 사용한다. 우선순위 큐를 구현하기 위해서 힙을 사용하였으며 fitness (최고값)의 값을 토대로 노드들을 오름순으로 나열한다.▣ A* 알고리즘본 논문의 핵심 알고리즘으로 최단 거리 탐색을 하기 위해 본 알고리즘을 사용한다. 다익스트라 알고리즘보다 효율이 높으며 최고우선검색 방식을 이용해서 최소의 선택으로 목표점까지 도달할 수 있다.3. 연구내용두 지점간의 최단경로를 구하기 위해 시작점에서 중간 정점 x까지의 최단경로 g(x)를 구해 놓았으면 x로부터 목적점까지의 직선거리를 추정치로 삼아 시작점에서 x를 거쳐 목적점에 도달하는 거리를 추정할 수 있다.A* 알고리즘은 두 함수 g(x)와 h(x)를 사용해 판단한다. g(x)는 앞에서 사용한 g(x)와 같다. h(x)는 정점 x에서 목적점까지의 추정 잔여거리다. 이 추정거리 h(x)는 정점 x에서 목적점까지의 실제 최단거리보다는 크지 않아야 한다. A* 알고리즘은 g(x)+h(x) 값이 가장 작은 정점부터 선택한다.A*의 알고리즘은 다음과 같이 동작한다.검색된 인접노드들을 열린목록에 넣는다.다음 과정을 반복한다.열린목록에서 가장 낮은 f(최고값) 비용을 찾아 선택한다.이를 꺼내 닫힌목록에 넣는다.현재 노드에 인접한 노드들에 대해..만약 인접한 노드에 갈 수 없거나 닫힌 목록상에 있다면 제외, 그렇지 않다면 다음을 계속한다.만약 열린목록에 있지 않다면, 열린목록에 추가한다.만약 열린목록에 있다면, 이 노드가 열린목록에 추가되면 자동으로 f의 값에 의해 나열될 것이다.그만해야 할 때길을 찾는 중 목표노드를 열린목록에 추가하였을 때,열린목록이 비어있게 될 경우 (이때는 목표노드 탐색실패)길 저장하기목표 노드부터 시작으로 각 노드에 저장된 부모노드값을 되추적한다.4. 구 현지도는 위와 같고 각 노드들 사이에는 이음선이 존재한다. 이음선들을 모두 거리값을 갖고 있다. 노드들 또한 좌표를 갖고 있어서 나중에 휴리스틱 값을 계산하는데 이 좌표값들을 사용된다.노드각 노드는 다음과 같은 구조를 갖고 있다. path 변수에는 전에 거쳤던 노드번호가 저장된다.struct Node{int path;int Node_num; //노드번호int bound; //한계값int g;//현재까지의 값int h;//앞으로의 예측값};열린목록은 힙을 사용해서 우선순위큐로 구현하였다. 그리고 닫힌목록은 스택으로 구현했다.-열린목록 주요 구현부분열린목록에서 Enqueue를 실행시 마지막 자기에 노드를 추가하고 정렬을 하기 위해 ReheapUp을 수행한다. 다음을 ReheapUp을 구현한 소스부분이다.void PQType::ReheapUp(int root, int bottom){int parent;if(bottom>root){parent=(bottom-1)/2;//자식노드의 최고값이 부모노드의 최고값보다 작다면if(elements[parent].bound>elements[bottom].bound){//스왑을 실행Swap(elements[parent],elements[bottom]);ReheapUp(root,parent);//ReheapUp 재귀호출}}}열린목록에서 Dequeue를 실행하면 루트노드의 값이 축출되고 그 자리를 마지막 노드가 대체하게 된다. 정렬을 하기 위해 ReheapDown을 수행한다. 다음을 ReheapDown을 구현한 소스이다.void PQType::ReheapDown(int root, int bottom){int minChild;int rightChild;int leftChild;leftChild = root*2+1;rightChild = root*2+2;if(leftChildelements[rightChild].bound)minChild=rightChild; //우측을 minChild로 설정elseminChild=leftChild; //좌측을 minChild로 설정}//루트의 최고값이 minChild의 최고값보다 크다면if (elements[root].bound> elements[minChild].bound){//스왑을 실행Swap(elements[root],elements[minChild]);//ReheapDown 재귀호출ReheapDown(minChild,bottom);}}}-닫힌목록 주요 구현부분닫힌목록의 일반적인 부분은 보통 스택과 동일한다. 하지만 닫힌목록에 이미 저장돼 있는지의 여부를 판단하는 Closed_chk 함수를 추가하였다. 이 함수는 탐색부분을 실행하기 전에 이미 닫힌목록에 포함된 노드들을 제외하는 if문에 사용된다.bool Stack::Closed_chk(int x, int &index){bool exist;exist=false;for(int i=0;i

공학/기술| 2008.01.10| 27페이지| 2,500원| 조회(1,064)

휴리스틱, A* 알고리즘, 최단경로탐색, 최적우선트리, 열린목록

미리보기

닫기