[C언어 알고리즘] 6.2.5 깊이우선탐색(DFS) 알고리즘의 경험(Heuristic) 정보 설계

[C언어 알고리즘] 6.2.5 깊이우선탐색(DFS) 알고리즘의 경험(Heuristic) 정보 설계

---

 동적 알고리즘에서는 경험 정보를 설계하는 것이 매우 중요합니다. DFS 알고리즘에서의 경험 정보는 그래프에서 출발점과 도착점 사이에 이동 경로를 기억하고 있어야 합니다. 여기에서는 이동 경로를 배열을 이용하여 보관하기로 할게요. 그리고 총 이동 거리도 멤버로 구성합시다.

typedef struct _Heuristic Heuristic;

struct _Heuristic

{

    Array *exprs;

    Graph *graph;

    Vertex start;

    Vertex goal;

    int total_weight;

};

 

 초기 경험 정보를 생성하는 함수를 제공합시다. 초기 경험 정보를 생성하려면 그래프와 출발지, 도착점을 알아야 합니다.

Heuristic *MakeInitHeuristic(Graph *graph,Vertex start,Vertex goal);

 

 동적으로 생성한 경험 정보를 소멸하는 함수도 제공합시다.

void DeleteHeuristic(Heuristic *now);

 

 현재 경험 정보에서 경험할 수 있는 다음 경험 정보 목록을 찾는 함수를 제공합시다. 입력 인자로 현재 경험 정보와 다음 경험 정보 목록을 보관할 배열을 받습니다.

void FindNextHeuristics(Heuristic *now, Array *next_heus);

 

 가장 최근에 경험한 정점을 구하는 함수도 제공합시다.

Vertex GetLastVertex(Heuristic *now);

 

 도착점에 도달했는지 확인하는 함수도 제공합시다.

int IsGoal(Heuristic *now);

 

 그리고 경험 정보의 총 거리와 이동 경로를 출력하는 함수를 제공합시다.

void ViewHeuristic(Heuristic *now);