[알고리즘 C언어] 6.2.6 깊이우선탐색(DFS) 알고리즘의 경험 정보 구현

이제 깊이우선탐색 알고리즘의 Heuristic 을 구현합시다.

초기 경험 정보를 생성하는 함수를 작성합시다.

Heuristic *MakeInitHeuristic(Graph *graph,Vertex start,Vertex goal)
{
    Heuristic *heu = 0;

경험 정보 크기의 메모리를 할당합니다.

    heu = (Heuristic *)malloc(sizeof(Heuristic));

이동 경로를 보관할 동적 배열을 생성합니다.

    heu->exprs = New_Array();

그래프와 출발점, 도착점을 설정합니다.

    heu->graph = graph;
    heu->start = start;
    heu->goal = goal;

출발점을 이동 경로에 보관합니다.

    Array_PushBack(heu->exprs,(Element)start);

그리고 현재까지의 총 거리를 0으로 설정한 후에 경험 정보를 반환합니다.

    heu->total_weight = 0;
    return heu;
}

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

void DeleteHeuristic(Heuristic *now)
{

이동 경로를 보관하기 위해 할당했던 동적 배열을 소멸한 후에 자신의 메모리를 해제합니다.

    Delete_Array(now->exprs);
    free(now);
}

현재 경험 정보에서 수행할 수 있는 다음 경험 목록을 조사하는 함수를 작성합시다.

void FindNextHeuristics(Heuristic *now, Array *next_heus)
{
    Array *next_vts = 0;
    Iterator seek=0, end=0;
    Vertex next_vt;
    Heuristic *next;

현재 정점에서 갈 수 있는 이웃 정점 목록을 보관하기 위한 배열을 생성합니다.

    next_vts = New_Array();

그래프에서 현재 정점의 이웃하는 정점 목록을 구합니다.

    Graph_FindNeighvor(now->graph,GetLastVertex(now),next_vts);

이웃 정점 목록의 시작과 끝을 구합니다.

    seek = Array_Begin(next_vts);
    end = Array_End(next_vts);

순차적으로 이동하면서 이웃 정점을 구합니다.

    for(seek = seek; seek != end; ++seek)
    {
        next_vt = (Vertex)(*seek);

만약 이웃 정점을 방문하지 않았을 때 처리를 합시다. 그리고 특정 정점을 방문한 것인지 확인하는 함수는 별도로 작성합시다.

        if( !IsExistVertex(now,next_vt) )
        {

현재 경험 정보에 특정 정점을 방문하는 경험 정보를 생성합니다. 이 부분도 별도의 함수로 작성합니다.

            next = MakeNextHeu(now,next_vt);

생성한 다음 경험 정보를 배열에 보관합니다.

            Array_PushBack(next_heus,next);
        }
    }
}

특정 정점을 방문하였는지 확인하는 함수를 작성합시다.

int IsExistVertex(Heuristic *now, Vertex vt)
{
    Iterator seek=0, end=0;
    Vertex expr_vt;

방문한 경로의 시작과 끝을 구하세요.

    seek = Array_Begin(now->exprs);
    end = Array_End(now->exprs);

그리고 순차적으로 이동하면서 방문한 정점을 구합니다.

    for(seek = seek; seek != end; ++seek)
    {
        expr_vt = (Vertex)(*seek);

입력 인자로 받은 정점과 같은 정점이면 이미 방문한 정점이므로 1을 반환합니다.

        if(strcmp(expr_vt,vt)==0)
        {
            return 1;
        }
    }
    return 0;
}

현재 경험 정보에 특정 정점을 방문하는 다음 경험 정보를 생성하는 함수를 작성합시다.

Heuristic *MakeNextHeu(Heuristic *now,Vertex vt)
{
    Heuristic *heu = 0;
    Iterator seek=0, end=0;
    Vertex expr_vt;

먼저 초기 경험 정보를 생성합니다.

    heu = MakeInitHeuristic(now->graph,now->start,now->goal);

입력 인자로 받은 경험 정보의 방문한 경로의 시작과 끝을 구합니다.

    seek = Array_Begin(now->exprs);
    end = Array_End(now->exprs);

시작 위치의 정점을 구합니다.

    expr_vt = (Vertex)(*seek);

초기 경험 정보에서는 출발점을 방문한 상태로 출발합니다. 따라서 seek를 다음 위치로 이동한 후에 순차적으로 정점을 구합니다.

    for(seek++; seek != end; ++seek)
    {
        expr_vt = (Vertex)(*seek);

새로 생성한 경험 정보의 이동 경로 보관 배열에 정점을 추가합니다. 이 처리를 통해 입력 인자로 받은 경험 정보와 같은 이동 경로를 갖습니다.

        Array_PushBack(heu->exprs,(Element)expr_vt);
    }

새로 생성한 경험 정보의 총 거리를 입력 인자로 받은 경험 정보의 총 거리로 설정합니다.

    heu->total_weight = now->total_weight;

총 거리에 마지막 방문한 정점과 새로 추가할 정점의 거리를 더합니다.

    heu->total_weight += Graph_GetWeight(heu->graph,expr_vt,vt);

그리고 입력 인자로 받은 정점을 방문한 정점 목록에 추가합니다.

    Array_PushBack(heu->exprs,(Element)vt);
    return heu;
}

마지막 방문한 정점을 구하는 함수를 작성합시다.

Vertex GetLastVertex(Heuristic *now)
{

배열의 마지막 위치를 구합니다.

    Iterator end = Array_End(now->exprs);

주의할 점은 마지막 위치는 마지막 보관한 자료의 다음 위치입니다. 따라서 위치를 1 감소합니다.

    --end;

해당 위치에 보관한 정점을 반환합니다.

    return  (Vertex)(*end);
}

도착점에 도달했는지 확인하는 함수를 작성합시다.

int IsGoal(Heuristic *now)
{

마지막 정점이 도착점인지 비교한 값이 차이가 없는지 여부를 반환합니다.

    return strcmp(now->goal,GetLastVertex(now))==0;
}

경험 정보를 출력하는 함수를 작성합시다.

void ViewHeuristic(Heuristic *now)
{
    Iterator seek=0, end=0;

총 거리를 출력합시다.

    printf("총 거리:%d ",now->total_weight);

이동 경로의 시작과 끝을 구합니다.

    seek = Array_Begin(now->exprs);
    end = Array_End(now->exprs);

순차적으로 방문한 정점을 출력합니다.

    for(seek = seek; seek != end; ++seek)
    {
        printf("%s ",(Vertex)*seek);
    }

다음 출력할 내용과 구분하기 위해 개행문자를 출력합시다.

    printf("\n");
}