[카테고리:] <span>C언어 알고리즘</span>

이제 앞에서 작성한 Heuristic을 이용하여 깊이우선탐색 알고리즘을 작성합시다.

먼저 알고리즘에 사용할 그래프를 생성하여 구성하는 함수를 작성합시다.

Graph * InitSimulation()
{
    Graph *graph = New_Graph();
    Graph_AddVertex(graph,"A");
    Graph_AddVertex(graph,"B");
    Graph_AddVertex(graph,"C");
    Graph_AddVertex(graph,"D");
    Graph_AddVertex(graph,"E");
    Graph_AddVertex(graph,"F");
    Graph_AddVertex(graph,"G");
    Graph_AddVertex(graph,"H");

    Graph_AddEdge(graph,"A","B",5);
    Graph_AddEdge(graph,"A","D",4);
    Graph_AddEdge(graph,"A","E",4);
    Graph_AddEdge(graph,"B","D",4);
    Graph_AddEdge(graph,"B","H",2);
    Graph_AddEdge(graph,"C","D",2);
    Graph_AddEdge(graph,"C","G",3);
    Graph_AddEdge(graph,"D","H",2);
    Graph_AddEdge(graph,"D","E",3);
    Graph_AddEdge(graph,"D","F",3);
    Graph_AddEdge(graph,"E","F",3);
    Graph_AddEdge(graph,"F","G",6);
    Graph_AddEdge(graph,"G","H",3);

    Graph_View(graph);
    return graph;
}

깊이우선탐색(DFS) 알고리즘 테스트 코드 작성 전에 다시 한 번 동적 알고리즘의 의사코드를 확인합시다.

동적 알고리즘

초기 경험 정보를 생성

스택에 초기 경험 정보 Push

반복(스택이 빌 때까지)

스택에서 경험 정보를 Pop

꺼낸 온 경험에서 발생할 수 있는 다음 경험 정보 조사

반복(다음 경험 정보들을 순차적으로)

조건(결과에 도달하지 않았다면)

스택에 경험 정보를 Push

그렇지 않다면

결과에 보관

int main()
{
    EHStack *ehs = 0;
    Heuristic *heu = 0;
    Graph *graph = 0;
    Array *next_heus = 0;
    Iterator seek=0, end=0;

알고리즘 테스트에 사용할 그래프를 생성합니다.

    graph = InitSimulation();

스택을 생성합니다.

    ehs = New_EHStack();

초기 경험 정보를 생성합니다. 여기에서는 A점을 출발점으로 하고 H점을 도착점으로 할게요.

    heu = MakeInitHeuristic(graph,"A","H");

초기 경험 정보를 스택에 보관합니다.

    EHStack_Push(ehs,heu);

스택에 경험 정보가 남아있다면 반복 수행합니다.

    while( ! EHStack_IsEmpty(ehs) )
    {

스택에 보관한 경험 정보를 꺼내옵니다.

         heu = (Heuristic *)EHStack_Pop(ehs);

다음 경험 정보 목록을 보관할 동작 배열을 생성합니다.

         next_heus = New_Array();

현재 경험 정보에서 수행할 수 있는 다음 경험 정보 목록을 구합니다.

         FindNextHeuristics(heu,next_heus);

조사한 다음 경험 정보 목록의 시작과 끝을 구합니다.

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

순차적으로 이동하면서 다음 경험 정보를 구합니다.

        for(seek=seek; seek != end; ++seek)
        {
            heu = (Heuristic *)(*seek);

만약 도착점에 도달하면 경험 정보를 출력하고 소멸합시다.

            if(IsGoal(heu))
            {
                ViewHeuristic(heu);
                DeleteHeuristic(heu);
            }

도착점에 도달하지 않았다면 스택에 보관합니다.

            else
            {
                EHStack_Push(ehs,heu);
            }
        }

임시로 다음 경험 정보 목록을 보관했던 배열을 소멸합니다.

        Delete_Array(next_heus);
    }
    Delete_Graph(graph);
    Delete_EHStack(ehs);
    return 0;
}

다음은 테스트에 사용한 그래프와 실행 결과입니다.

실행 결과

총 거리:16 A E F G H 
총 거리:23 A E F G C D H 
총 거리:24 A E F G C D B H 
총 거리:15 A E F D H 
총 거리:18 A E F D C G H 
총 거리:16 A E F D B H 
총 거리:12 A E D H 
총 거리:19 A E D F G H 
총 거리:15 A E D C G H 
총 거리:13 A E D B H 
총 거리:9 A D H 
총 거리:16 A D F G H 
총 거리:19 A D E F G H 
총 거리:12 A D C G H 
총 거리:10 A D B H 
총 거리:7 A B H 
총 거리:14 A B D H 
총 거리:21 A B D F G H 
총 거리:24 A B D E F G H 
총 거리:17 A B D C G H