이제 깊이우선탐색 알고리즘의 Heuristic 을 구현합시다.
초기 경험 정보를 생성하는 함수를 작성합시다.
|
1 2 3 |
Heuristic *MakeInitHeuristic(Graph *graph,Vertex start,Vertex goal) { Heuristic *heu = 0; |
경험 정보 크기의 메모리를 할당합니다.
|
1 |
heu = (Heuristic *)malloc(sizeof(Heuristic)); |
이동 경로를 보관할 동적 배열을 생성합니다.
|
1 |
heu->exprs = New_Array(); |
그래프와 출발점, 도착점을 설정합니다.
|
1 2 3 |
heu->graph = graph; heu->start = start; heu->goal = goal; |
출발점을 이동 경로에 보관합니다.
|
1 |
Array_PushBack(heu->exprs,(Element)start); |
그리고 현재까지의 총 거리를 0으로 설정한 후에 경험 정보를 반환합니다.
|
1 2 3 |
heu->total_weight = 0; return heu; } |
동적으로 생성한 경험 정보를 소멸하는 함수를 작성합시다.
|
1 2 |
void DeleteHeuristic(Heuristic *now) { |
이동 경로를 보관하기 위해 할당했던 동적 배열을 소멸한 후에 자신의 메모리를 해제합니다.
|
1 2 3 |
Delete_Array(now->exprs); free(now); } |
현재 경험 정보에서 수행할 수 있는 다음 경험 목록을 조사하는 함수를 작성합시다.
|
1 2 3 4 5 6 |
void FindNextHeuristics(Heuristic *now, Array *next_heus) { Array *next_vts = 0; Iterator seek=0, end=0; Vertex next_vt; Heuristic *next; |
현재 정점에서 갈 수 있는 이웃 정점 목록을 보관하기 위한 배열을 생성합니다.
|
1 |
next_vts = New_Array(); |
그래프에서 현재 정점의 이웃하는 정점 목록을 구합니다.
|
1 |
Graph_FindNeighvor(now->graph,GetLastVertex(now),next_vts); |
이웃 정점 목록의 시작과 끝을 구합니다.
|
1 2 |
seek = Array_Begin(next_vts); end = Array_End(next_vts); |
순차적으로 이동하면서 이웃 정점을 구합니다.
|
1 2 3 |
for(seek = seek; seek != end; ++seek) { next_vt = (Vertex)(*seek); |
만약 이웃 정점을 방문하지 않았을 때 처리를 합시다. 그리고 특정 정점을 방문한 것인지 확인하는 함수는 별도로 작성합시다.
|
1 2 |
if( !IsExistVertex(now,next_vt) ) { |
현재 경험 정보에 특정 정점을 방문하는 경험 정보를 생성합니다. 이 부분도 별도의 함수로 작성합니다.
|
1 |
next = MakeNextHeu(now,next_vt); |
생성한 다음 경험 정보를 배열에 보관합니다.
|
1 2 3 4 |
Array_PushBack(next_heus,next); } } } |
특정 정점을 방문하였는지 확인하는 함수를 작성합시다.
|
1 2 3 4 |
int IsExistVertex(Heuristic *now, Vertex vt) { Iterator seek=0, end=0; Vertex expr_vt; |
방문한 경로의 시작과 끝을 구하세요.
|
1 2 |
seek = Array_Begin(now->exprs); end = Array_End(now->exprs); |
그리고 순차적으로 이동하면서 방문한 정점을 구합니다.
|
1 2 3 |
for(seek = seek; seek != end; ++seek) { expr_vt = (Vertex)(*seek); |
입력 인자로 받은 정점과 같은 정점이면 이미 방문한 정점이므로 1을 반환합니다.
|
1 2 3 4 5 6 7 |
if(strcmp(expr_vt,vt)==0) { return 1; } } return 0; } |
현재 경험 정보에 특정 정점을 방문하는 다음 경험 정보를 생성하는 함수를 작성합시다.
|
1 2 3 4 5 |
Heuristic *MakeNextHeu(Heuristic *now,Vertex vt) { Heuristic *heu = 0; Iterator seek=0, end=0; Vertex expr_vt; |
먼저 초기 경험 정보를 생성합니다.
|
1 |
heu = MakeInitHeuristic(now->graph,now->start,now->goal); |
입력 인자로 받은 경험 정보의 방문한 경로의 시작과 끝을 구합니다.
|
1 2 |
seek = Array_Begin(now->exprs); end = Array_End(now->exprs); |
시작 위치의 정점을 구합니다.
|
1 |
expr_vt = (Vertex)(*seek); |
초기 경험 정보에서는 출발점을 방문한 상태로 출발합니다. 따라서 seek를 다음 위치로 이동한 후에 순차적으로 정점을 구합니다.
|
1 2 3 |
for(seek++; seek != end; ++seek) { expr_vt = (Vertex)(*seek); |
새로 생성한 경험 정보의 이동 경로 보관 배열에 정점을 추가합니다. 이 처리를 통해 입력 인자로 받은 경험 정보와 같은 이동 경로를 갖습니다.
|
1 2 |
Array_PushBack(heu->exprs,(Element)expr_vt); } |
새로 생성한 경험 정보의 총 거리를 입력 인자로 받은 경험 정보의 총 거리로 설정합니다.
|
1 |
heu->total_weight = now->total_weight; |
총 거리에 마지막 방문한 정점과 새로 추가할 정점의 거리를 더합니다.
|
1 |
heu->total_weight += Graph_GetWeight(heu->graph,expr_vt,vt); |
그리고 입력 인자로 받은 정점을 방문한 정점 목록에 추가합니다.
|
1 2 3 |
Array_PushBack(heu->exprs,(Element)vt); return heu; } |
마지막 방문한 정점을 구하는 함수를 작성합시다.
|
1 2 |
Vertex GetLastVertex(Heuristic *now) { |
배열의 마지막 위치를 구합니다.
|
1 |
Iterator end = Array_End(now->exprs); |
주의할 점은 마지막 위치는 마지막 보관한 자료의 다음 위치입니다. 따라서 위치를 1 감소합니다.
|
1 |
--end; |
해당 위치에 보관한 정점을 반환합니다.
|
1 2 |
return (Vertex)(*end); } |
도착점에 도달했는지 확인하는 함수를 작성합시다.
|
1 2 |
int IsGoal(Heuristic *now) { |
마지막 정점이 도착점인지 비교한 값이 차이가 없는지 여부를 반환합니다.
|
1 2 |
return strcmp(now->goal,GetLastVertex(now))==0; } |
경험 정보를 출력하는 함수를 작성합시다.
|
1 2 3 |
void ViewHeuristic(Heuristic *now) { Iterator seek=0, end=0; |
총 거리를 출력합시다.
|
1 |
printf("총 거리:%d ",now->total_weight); |
이동 경로의 시작과 끝을 구합니다.
|
1 2 |
seek = Array_Begin(now->exprs); end = Array_End(now->exprs); |
순차적으로 방문한 정점을 출력합니다.
|
1 2 3 4 |
for(seek = seek; seek != end; ++seek) { printf("%s ",(Vertex)*seek); } |
다음 출력할 내용과 구분하기 위해 개행문자를 출력합시다.
|
1 2 |
printf("\n"); } |
학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.