|
탐색트리를 작성하면 아래 그림과 같다. 그림에서 원 내부의 좌표는 노드를 의미한다. 원의 우측 숫자는 해당 노드의 평가함수값이다. ①~⑪은 OPEN에서 꺼내어 목표노드인가를 검사하는 순서이다. 화살표 옆의 파란색 수는 즉, 시작노드에서
|
|
|
노드 에 도달하는 비용은 고려되지 않는다. 따라서 시작 노드에서 대상 노드까지의 최적 경로를 검색하는 것은 보장되지 않는다.
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라.
[1단계]
[2단계]
[3단
|
|
|
대한 정보를 사용하지 않는 방법
넓이우선, 깊이우선, 균일비용 탐색 등
2. 경험적 탐색방법
목표노드에 이르기 위한 정보를 이용해 탐색하는 방법
언덕오르기, 최적우선, A* 알고리즘 등
3. 균일비용탐색(비용)
출발노드로부터 경로비용이 최
|
|
|
노드탐색
TNode node = nodes[id].next;
while (null != node)
{
int nextTransfer = transfer;
// 환승
if (nodeNames[id].Equals(nodeNames[node.key]))
{ //역이름이같다면환승값을올려준다.
++nextTransfer;
}
// 현재까지의최적거리보다빠르거나, 같을때환승갯수가작다면
if (-1 == minTi
|
|
|
Ⅰ. 이진탐색트리의 생성 및 노드 삽입
1. 이진탐색트리의 정의
이진탐색트리는 이진 트리로서 공백이 가능하다. 만약 공백이 아니라면 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않으며, 왼쪽 서브트리에는 루트보다 작은
|
|
 |
탐색트리로 자식노드가 최대 2개인 트리로 왼쪽 자식노드가 부모 노드가 가진 값보다 작고 오른쪽 자식노드가 부모노드가 가진 값보다 큰 조건을 만족하는 이진트리 구조
balanced tree일때는 logN(탐색할때 마다 데이터양이 1/2씩 감소하기 때문
|
|
메뉴펼치기
