[Algorithm] 상태 공간 탐색

상태 공간 탐색

상태 공간 탐색은 인공지능을 포함한 컴퓨터공학에서 사용되는 전략으로 문제에서 정의될 수 있는 모든 상황을 상태로 정의한다. 그 후 각각의 상태에서 수행할 수 있는 모든 선택을 행동으로 정의하여 원하는 속성을 갖는 목표 상태에 도달하기까지 여러 가지 전략으로 행동들을 선택해나가는 탐색 과정이다. 일반적으로 가능한 해 중 가장 최적의 해를 찾는 형태인 최적화 문제(Optimization Problem)를 해결하기 위해 많이 사용된다. 문제는 굉장히 다양한 방법으로 정의될 수 있지만, 탐색 과정 중에 얻는 정보들을 적절하게 이용하여 각 문제를 해결할 수 있다. 먼저 틱택토(Tic-Tac-Toe) 게임을 예로 들어보자. 틱택토는 두 명이 번갈아 가며 O와 X를 3 x 3 게임판에 놓아서 같은 글자를 가로, 세로, 혹은 대각선상에 놓이도록 하는 게임이다. 이 게임에서 나타날 수 있는 모든 상태를 표현하려면 어떻게 해야 할까?

먼저 시작상태를 준다면 그 시작 상태에서 선택할 수 있는 모든 행동들을 선택해본다. 각 행동으로 인해 파생된 모든 새로운 상태들에 대해 다시 선택할 수 있는 모든 행동들을 선택해본다. 이 과정을 재귀적으로 반복한다면 모든 상태와 행동들을 트리 형태로 표현할 수 있다. 이 트리를 상태 공간 트리(State Space Tree) 혹은 게임 트리(Game Tree) 라고 부른다. 또한, 각 행동들을 어떤 전략으로 선택하는지에 따라 서로 다른 순서로, 서로 다른 상태들을 탐색하게 될 수 있는데 이 다양한 탐색 방법들을 상태 공간탐색(State Space Search)이라 부른다. 상태 공간탐색은 일반적으로 컴퓨터공학의 전통적인 그래프 탐색 방법과는 구분되는데, 이유는 그래프 탐색의 경우 가능한 상태들이 이미 명시적으로 모두 정의되어있는 반면, 상태 공간탐색에서의 상태들은 상태들이 미리 표현해두기에는 너무 많고, 상태 또한 암시적인 경우가 많기 때문이다.

 

틱택토에 대한 상태공간트리

 

그렇다면 이렇게 탐색을 하는 것이 어떤 의미가 있을까?

모든 상태를 순회하는 것만으로도 충분히 의미가 있다. 틱택토 게임의 모든 상태를 방문하는 과정 중에는 자신이 이기는 상태들도 방문할 수 있을 것이다. 또한, 이기는 상태 중에서도 가장 최소의 행동으로 이기는 행동조합도 찾을 수 있을 것이다. 상태 공간의 크기가 컴퓨터가 감당할 수 있을 정도로 작다면, 모든 상태가 표현될 수 있고 알고리즘을 통해 반드시 이기는 전략을 찾을 수 있다. 상태 공간탐색을 활용하면 일반적인 방법으로는 표현하기 힘든 까다로운 문제에 대해서도 모든 상태를 표현해낼 수 있다. 체스, 장기, 바둑과 같은 보드게임부터 LOL, 오버워치, 스타크래프트와 같은 복잡한 게임까지도 다 표현이 가능하다. 심지어 우리가 사는 이 세상까지도 표현이 가능하다. 물론 세계가 복잡해질수록 탐색해야 하는 상태 공간의 크기가 기하급수적으로 커지기 때문에 완전 탐색은 불가능하겠지만, 일단 표현이 가능하다는 점을 통해 현실의 문제를 컴퓨터공학의 문제로 대응시킬 수 있고, 또한 여러 전략적인 탐색 방법들이 있기 때문에 큰 탐색공간에 대해서도 어느 정도 감당이 가능하다. (그렇기 때문에 이 상태 공간탐색의 전략들은 인공지능 분야의 가장 기초적인 지식으로써 활용된다)

알고리즘 문제에서도 상태 공간에 대해 다루는 문제들이 자주 등장하는데, 다음과 같은 항목들로 문제가 구성된다.

1. 해당 게임을 클리어할 수 있는지 확인하기.

2. 해당 게임을 해결하기 위한 최소행동 수 찾기.

3. 해당 게임을 해결하기 위한 최적 행동 집합을 나열하기. 등등의 형태로 등장한다. 여기서 조금 더 심화한 문제들은 중간중간에 순열, 조합과 같은 경우의 수가 섞이거나, 표현해야 하는 상태나 행동들이 조금 더 복잡해지거나, 기본적인 탐색 방법보다 좀 더 전략적인 탐색 방법을 요구하는 형태로 구성된다.

알고리즘 문제에서의 상태 공간탐색 문제를 해결하기 위해 가장 중요한 것들은 다음과 같다.

1. 상태 공간을 표현하기 위한 파라미터가 무엇인지 정확하게 파악해야 한다.

2. 상태 공간의 크기를 파악해야 한다.

3. 선택할 수 있는 행동들을 정확히 파악해야 한다.

4. 문제를 해결하기 위한 가장 적절한 탐색 방법을 찾고 설계해야 한다. (일반적으로는 상태 공간탐색과 그래프 탐색은 구분되지만 만약 상태 공간의 크기가 충분히 그래프로 대응시킬 수 있는 정도라면 상태 => 노드, 행동 => 간선으로, 미리 그래프에 대응시켜놓고 문제를 해결하는 것도 좋은 전략이 될 것이다.)

 

상태 공간

상태 공간은 상태, 행동, 행동에 대한 비용으로 표현된다.

 

상태

상태는 상태 공간을 표현하기 위한 가장 근본적인 개념으로 여러 상태 표현을 위한 파라미터의 조합을 통해 구성되며 이 조합은 유일해야 한다. 예를 들어 틱택토와 같은 게임에서의 상태는 다음과 같은 9개의 공간을 갖는 하나의 배열로 구성될 수 있을 것이다.

enum Mark
{
    Blank, O, X 
};

vector<Mark> state(9);

 

9개의 공간을 위에서부터 3개씩 틱택토의 게임판 위치로 가정하고 사용할 수 있을 것이다. 또한 각 상태는 유일하며, 게임에서 등장할 수 있는 모든 상황을 O, X, Blank의 조합으로 표현할 수 있다. 이렇게 계산한다면 틱택토 게임의 모든 상태의 개수는 3 ^ 9 = 19683이다.

하지만 좀 더 들여다보면 존재할 수 없는 상태들이 있다는 것을 알 수 있다. 틱택토라는 게임 자체가  두 명의 플레이어가 각각 O, X를 마킹하는 게임이기 때문에, 마크의 개수가 다른 마크의 개수 + 1 보다 많아질 수 없다. 예를들면 전체 보드가 X로 마킹된다거나 하는 일은 일어날 수 없다는 의미이다. 이러한 조건까지 모두 계산한다면 상태의 개수는 더 줄어들 것이다. (문제를 해결함에 있어서는 먼저 상태의 개수가 최악의 경우 얼마까지 늘어날 수 있는지 추산할 필요가 있다. 그러므로 처음에는 러프하게 계산하는 방법으로 접근하는것이 효과적일 것이다.)

 

구현적인 관점에서 생각해보자. 상태 데이터는 최대한 추상 데이터 타입에 근접한 형태로 대부분의 연산자를 지원해야 한다. 동등 연산자가 구현되어 있거나 유일 키가 제공되어야 방문 배열, 방문 해시 테이블 등에 이용될 수 있을 것이고,
비교 연산자가 구현되어 있어야 정렬, 이진 트리, 우선순위 큐에 이용될 수 있을 것이다. 그리고 같은 상태를 표현하는 여러 가지 값이 생겨서는 안 된다. 예를 들어 유리수 구조체의 경우 분자와 분모로 수를 표현하는데, (1, 2)와 (2, 4)는 개념적으로 같은 값이다. 이렇게 개념적으로 같은 데이터가 다른 데이터로 표현되는 상황은 나중에 치명적인 버그로 나타날 수 있음으로 미리미리 같은 값으로 정규화하여 저장하는 것이 좋다.

 

행동

행동은 각 상태에서 취할 수 있는 선택을 의미한다. 틱택토와 같은 게임에서 예를 들어보자. 완전히 빈 게임판에서 취할 수 있는 선택은 0번 위치부터 8번 위치까지 총 9가지의 위치를 선택할 수 있을 것이다. 하지만 이미 게임이 어느 정도 진행되어 게임판에 6개의 칸이 점유된 상태라면 선택할 수 있는 위치는 6가지 밖에 없을 것이다. 또한 자신이 시작으로 선택한 마크가 O인지 X인지에 따라 선택한 위치에 세팅할 수 있는 값이 달라질 것이다. 이처럼 행동을 정의하는 레벨에서는 다양한 조건들이 고려되어야 하고, 그러한 조건들을 뚫고 처리된 행동들에 따라 다음 상태들이 생성될 것이다.

State : {S1, S2, ... SN}

Action : {A1, A2, ... AK}

NextState : State X (Action 중 조건을 만족하는 원소)

 

 

비용

비용은 상태 공간 내, 어떤 상태에서 어떤 행동을 선택했을 때, 필요한 비용을 의미한다.

보드게임과 같은 단순한 게임들은 턴 수가 비용으로 대응되어 일반적으로 대부분의 행동에 대한 비용이 1로 계산되지만, 스타크래프트와 같은 복잡한 게임이라면, 각 상태에서 취할 수 있는 행동들이 매우 다양할 것이고, 그에 따른 비용도 달라질 수 있을 것이다. 이처럼 비용이라는 개념을 행동에 부과할 수 있다면, 각 행동들에 대한 우선순의를 결정할 수 있고, 현실에서의 어려운 문제들도 해결할 수 있다.

 

실제 예제

실제 게임 예제들을 통해 상태 공간을 어떻게 정의하는지 확인해보자.

 

미로 찾기

미로 찾기에서 상태는 어떻게 표현할 수 있을까? 

미로찾기 문제가 어떻게 구성되는지에 따라 다르겠지만, 일반적인 2차원 배열 미로찾기 문제에서는 미로 위의 모든 탐색 위치들이 모든 탐색 가능한 상태들이 될 것이다. 상태 공간의 크기는 i, j의 범위를 M, N이라 하였을 때,  (M * N)이 될 것이다.

struct State
{
    int i, j;
};

그렇다면 미로를 표현하는 게임판 데이터는 왜 상태에 포함되지 않는 것일까?
만약 탐색 과정 중에 미로 게임판이 동적으로 변한다면 변하는 데이터도 상태에 추가되어야 할 것이다. 그리고 변하는 데이터가 많다면 게임판을 통째로 상태에 넣어야 하는 상황도 가정할 수 있다. 하지만, 일반적인 알고리즘 문제에서는 게임판은 정적인 데이터로 한번 결정된 상태로 변하지 않기 때문에 굳이 상태 데이터에 넣어줄 필요는 없다. (가끔 문제에서 게임판이 일부 변하는 형태로도 등장하는데, 이럴 때에도 굳이 상태 데이터를 크게 가져가는 것보다는 그 해당 부분만 따로 처리하는 방향으로 설계하는 게 낫다.)

 

행동은 어떻게 표현할 수 있을까??

상하좌우로 이동할 수 있는 미로찾기 문제에서는 다음과 같이 표현될 것이다.

    vector<pair<int, int>> actions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

 

식인종 가족 강건너기

다음 문제를 보자.

두 개의 섬이 있고 한쪽 섬에는 조련사, 사자, 아빠, 딸, 엄마, 아들과 배가 있다.
이 사람들은 반대편 섬으로 이동해야 하는데 문제가 있다.
만약 조련사가 없을 경우 사자는 모두을 잡아먹는다.
아빠가 없을 경우 엄마가 아들을 죽인다.
엄마가 없을 경우 아빠가 딸을 죽인다.
하지만 배를 움직일 수 있는 사람은 엄마, 아빠, 조련사 이 셋뿐이다.
그리고 보트에는 2명만 탑승할 수 있다.
아무도 죽지 않으며 반대편 섬으로 가려면 어떻게 이동시켜야 할까?

[섬A]                      [섬B]
조련사  ㅣ              ㅣ    
사자    ㅣ              ㅣ
아빠    ㅣ      강      ㅣ   
딸      ㅣ(배)          ㅣ
엄마    ㅣ              ㅣ
아들    ㅣ              ㅣ

이 문제에서 상태는 어떻게 표현할 수 있을까?

상태는 모든 상황을 표현할 수 있을 정도의 데이터로 설계하여야 한다.

조련사	=>	왼쪽에 있는 경우, 오른쪽에 있는 경우
사자	=>	왼쪽에 있는 경우, 오른쪽에 있는 경우
...
아들	=>	왼쪽에 있는 경우, 오른쪽에 있는 경우
보트	=>	왼쪽에 있는 경우, 오른쪽에 있는 경우

즉 현재 상태공간의 모든 객체들은 각각 왼쪽, 오른쪽에 위치할 수 있다.

그러므로 다음과 같이 bool 배열로 표현할 수 있을 것이다.

상태공간의 크기는 2 ^ 7 = 128 이다.

vector<bool> state;

 

하지만, 객체의 개수가 7개 밖에 되지 않기 때문에, 현재 상태에 대해서는 배열보다 더 효과적인 자료구조가 있다.

바로 비트마스크이다.

typedef bitset<7> State;
State state;

이런 최적해를 요구하는 형태의 문제에는 일반적으로 BFS를 이용한다. BFS는 탐색과정중에 목표상태에 도달하는 순간 그때까지의 최소깊이를 알 수 있는데, 이는 최적해로서 활용되기 때문이다.

이 문제에서 행동은 어떻게 표현할 수 있을까?

현재 배가 있는 위치를 기준으로, 하나의 객체를 이동시키는 방법 + 두 객체를 이동시키는 방법이 있을 것이다.

{ Mom },
{ Dad },
{ Son },
{ Daughter },
{ Trainer },
{ Lion },
{ Mom, Dad },
{ Mom, Son },
{ Mom, Daughter },
{ Mom, Trainer },
{ Mom, Lion },
{ Dad, Son },
{ Dad, Daughter },
{ Dad, Trainer },
{ Dad, Lion },
{ Son, Daughter },
{ Son, Trainer },
{ Son, Lion },
{ Daughter, Trainer },
{ Daughter, Lion },
{ Trainer, Lion }

이 조합들 중에서 현재 배가 있는 섬과 같은 섬에 있는 객체들만 이동이 가능할 것이고, 추가로 이동 시 배를 조종할 수 있는 객체가 있어야만 다음 상태로 넘어갈 수 있기 때문에 행동 조합은 위처럼 나열할 수 있겠지만, 실제 수행되는 행동은 게임 상태에 따라 달라질 것이다.

 

 

체스

체스 게임을 생각해보자.

 

체스에서 가능한 상태는 어떻게 표현될 수 있을까?

단순하게 생각하면 체스판을 통채로 상태에 넣어볼 수 있을 것이다. 가능한 각 체스 심볼종류 + 공백을 갖는 2차원 배열로 나타낼 수 있다.

enum ChessSymbols
{
    None, 
    WhiteKing, WhiteQueen, WhiteRook, WhiteBishop, WhiteKnight, WhitePawn,
    BlackKing, BlackQueen, BlackRook, BlackBishop, BlackKnight, BlackPawn
};

vector<vector<ChessSymbols>> state;

이렇게 하면 상태의 크기는 11 ^ 64이 될 것이다. 조금 더 좋은 방법은 없을까?

다음 링크를 참고하자.

https://en.wikipedia.org/wiki/Board_representation_(computer_chess) 

Board representation (computer chess) - Wikipedia

 

체스에서 가능한 모든 행동은 어떤 것들이 있을까?

현재 자신의 진영이 흑색진영이라 가정했을 때, 자신이 갖고있는 모든 심볼들에 대해 각 심볼들이 이동할 수 있는 모든 위치들이 행동 집합이 될 것이다.

 

탐색 방법

상태공간을 탐색하기 위해서 다양한 방법들이 존재한다.

각 탐색방법들은 상태공간이 어떤 형태로 정의되는지, 문제에서 요구하는 것이 무엇인지에 따라 달라질 수 있다.

 

방문 테이블

상태 공간을 탐색함에 있어서 이미 탐색한 상태를 다시 탐색하지 않도록 하기 위해 각 상태에 방문 기록을 남기게 된다.

이런 테이블을 방문 테이블이라 부르고 그래프가 구현되어 있는 경우 다음처럼 각 노드에 대한 방문 여부를 표현한다.

int N = 100;
vector<int> visited(N, false);

 

하지만 상태 공간은 그래프처럼 단순한 노드번호로 표현되지 않는 경우도 많다. 미로 찾기와 같이 위치 정보를 상태로 이용하는 예제의 방문 테이블을 다음과 같은 형태일 것이다. 이진트리의 키로서 이용될 수 있도록 하기 위해 비교 연산자를 추가하였다.

struct State
{
    int i, j;
    bool operator<(const State& other) const
    {
    	if(i == j)
        	return j < other.j;
    	return i < other.i;
    }
};

set<State> visited;

 

 

식인종 예제에서의 방문 테이블은 어떤 형태일까?

비트가 7개인 값을 이용하므로 128개의 공간을 갖는 배열로 방문 테이블을 만들 수 있을 것이다. 이용할 때에는 이진수 비트마스크의 값을 인덱스로 이용하면 된다. 이처럼 방문 테이블은 상태 데이터가 어떻게 정의되느냐에 따라 얼마든지 달라질 수 있다.

typedef bitset<7> State;
State state;

vector<bool> visited(128);

 

 

너비우선탐색

너비우선탐색은(Breadth First Search) 시작 노드로부터 가장 근처에 있는 노드들을 우선적으로 탐색하는 탐색전략이다.

가장 근처의 노드들이 모두 방문이 되었다면, 다음으로는 방금 방문된 노드들 근처의 노드들을 방문한다.

 

 

다음과 같은 순서로 노드를 방문하게 된다. 이러한 방문특성 덕분에 BFS를 이용하여 어떤 노드에 도달했다는 것은 최소 횟수로 그 노드에 도달한 것이 된다. 이 이유로 BFS는 최적해를 찾는 탐색 문제에서 자주 이용된다.

노드 탐색 순서
0 1 2 3 4 5 6

 

일반적으로 큐를 이용하여 구현한다. 위 트리를 양방향 그래프로 만들고 구현해보자. 그 후 각 노드에 대해 인접행렬에서 1인 노드들에 대해 큐를 이용하여 탐색을 수행한다. 또한 이미 방문된 노드를 다시 방문하지 않도록 하기 위해, 방문 배열에 기록한다. 형태는 다음과 같다.

상태 정의

BFS(시작상태, 목표상태)
    방문기록 테이블
    큐
    push(시작 상태)
    
    while !큐.empty():
        현재 상태 = 큐.top()
        상태에 대한 처리
        
        모든 가능한 행동에 대해:
            큐.push(다음 상태)
            방문기록[다음 상태]
        큐.pop()
        

 

소스코드 (BFS)

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/5-BFS-adjmatrix.cpp

insooneelife/AlgorithmTutorial

 

역추적 테이블

상태 공간을 탐색하는 과정에서 어떤 목표 상태에 도달할 때까지의 행동 조합을 순서대로 나열해봐야 하는 상황도 생길 수 있다. 이 문제를 해결하기 위해 역추적 테이블(Backtrack Table)을 이용하면 된다. 역추적 테이블은 탐색 도중 한 상태에 도달했을 때 이전에 어떤 상태로부터 현재 상태로 오게 되었는지를 기록하는 것이다.

탐색 과정 중 Table[현재 상태] = 이전 상태의 형태로 기록해나간다면, 어떤 최적 목표 상태에 도달했을 경우, 이 테이블을 최종 상태로부터 역추적하여 시작 상태까지의 상태 경로를 구할 수 있다.

일반적으로 다음과 같은 형태로 구현된다.

// 역추적 테이블 (현재상태, 이전상태)
map<State, State> backtrack;

 

소스코드 (역추적 테이블)

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/StateSpaceSearch/3-BFS-Path.cpp

insooneelife/AlgorithmTutorial

 

 

미로찾기 예제

다음과 같은 미로가 주어졌을 때, 이 미로의 (0, 0) 위치에서 (N - 1, N - 1) 위치까지 도달하기 위한 최소 이동 횟수를 구해보자. 이 문제는 BFS를 이용하여 최적해를 구할 수 있다.

const int N = 6;
int arr[N][N] =
{
    1,0,1,1,1,1,
    1,0,1,0,1,0,
    1,0,1,0,1,1,
    1,1,1,0,1,1,
    0,0,1,0,0,1,
    0,0,1,1,0,1
};

 

소스코드 (미로찾기 BFS)

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/StateSpaceSearch/2-BFS-Maze.cpp

insooneelife/AlgorithmTutorial

 

 

식인종 가족 강건너기

이 문제도 BFS를 이용하여 최적해를 구할 수 있다.

 

소스코드 (식인종 가족 강건너기)

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/StateSpaceSearch/Solutions/Custom/%EC%8B%9D%EC%9D%B8%EC%A2%85%20%EA%B0%80%EC%A1%B1%EC%9D%98%20%EA%B0%95%EA%B1%B4%EB%84%88%EA%B8%B0.cpp

insooneelife/AlgorithmTutorial

 

 

 

심화된 탐색 방법들

양방향 탐색

양방향 탐색(Bidirectional Search)은 방향성 그래프에서 초기 정점에서 목표 정점까지의 최단 경로를 찾는 그래프 검색 알고리즘이다. 단순한 BFS 탐색과 달리 하나는 초기 상태에서 앞으로 탐색하고, 하나는 목표 상태에서 뒤로 탐색하여 두 탐색이 만나면 중지된다. 이 접근 방식이 유용한 이유는 대부분의 경우에 더 빠르기 때문이다. 예를 들어 두 검색 모두 분기 계수 b로 트리가 확장된다고 가정하고, 시작에서 목표까지의 거리가 d 인 검색 문제에서 양방향 탐색의 복잡성은 O (b ^ d / 2) 이다. 이 양방향 탐색 시간의 합은 처음부터 목표까지 단일 탬색에서 발생하는 O (b ^ d) 복잡성보다 훨씬 적다.

 

일반 BFS와 양방향 BFS

 

식인종과 선교사

다음 문제를 양방향 탐색으로 해결해보자.

m 명의 선교사와 m 명의 식인종이 나룻배를 타고 강을 건너려고 하는데, 
나룻배에는 n 명 밖에는 탈 수가 없다. 
만일 강의 어느 쪽에서라도 식인종의 수가 선교사의 수보다 많으면 식인종들은 선교사들을 잡아먹게 된다.
이 때 선교사들이 잡혀먹히지 않고 무사히 강을 건너려면 어떻게 해야 하는가?

 

소스코드 (식인종과 선교사)

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/StateSpaceSearch/Solutions/Custom/%EC%8B%9D%EC%9D%B8%EC%A2%85%EA%B3%BC%20%EC%84%A0%EA%B5%90%EC%82%AC.cpp

insooneelife/AlgorithmTutorial

 

 

 

Lowest Cost First Search

한 상태에서 다른 상태들로의 탐색을 위한 비용이 서로 다른 경우, 이 탐색방법을 이용할 수 있다.

현재 선택할 수 있는 행동들 중 탐색비용이 가장 작은 행동들 위주로 선택하여 탐색하는 것이다.

다음 문제를 보자.

https://www.acmicpc.net/problem/2665

2665번: 미로만들기

 

시작 위치에서 끝 위치까지 미로를 찾으며 도달해야하는데, 중간에 미로가 막혀있다면 부수고 지나가야 한다. 이런 형태의 문제를 쉽게 접근하는 방법으로 Lowest Cost First Search를 이용할 수 있다. 일반적인 BFS에서는 큐를 이용하여 탐색하는데, 이 탐색방법에서는 우선순위 큐를 이용한다. 미로에서 지나갈 수 있는 영역을 높은 우선순위 값으로 큐에 넣고, 막혀있는 영역은 낮은 우선순위 값으로 큐에 넣으며 BFS를 수행한다면, 모든 열린 영역이 다 탐색되었을 때부터 막힌 영역을 탐색하기 시작한다. 그러다 열린 영역을 한번이라도 방문하면, 다시 모든 연결된 열린 영역을 방문하게 된다.

 

소스코드 (LCFS)

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/StateSpaceSearch/4-LCFS.cpp

insooneelife/AlgorithmTutorial

 

휴리스틱 탐색

Best First Search

A* search

휴리스틱 가지치기

MST 휴리스틱

 

 

 

이미지 출처 

https://leetcode.com/problems/word-ladder/discuss/390860/3-solution-or-Explanation-or-Easy-to-understand