7.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);