최단 경로 전략

최단 경로 전략

• 너비 우선탐색 대신 최댄 경로 문제를 풀기 위해 쓸 수 있는 2가지 방법

양방향 탐색 - 역방향   

1. 문제
1. 역뱡향 간선(?)을 찾아 내기 어려운 문제 
2. 너비의 노드가 각 3개씩있고, 깊이가 20일때 마지막 연산은 3^20이 된다. 이를 양방향에서 탐색하여 2*(3^(20/2))로 만들어 준다.

점점 깊어지는 탐색 - 너비의 규모가 큰 탐색에서 깊이우선 탐색을 해야 메모리를 줄일 수 있다.

1. 문제
1. 가까운 순서대로 방문하지 않으므로 최단거리인지확신할 수없다.
2. 정점을 방문했는지 확인하지 않는다?
2. 해결 - 점점 깊어지는 탐색
1. 휴리스틱을 이용한 가지치기방법으로 사용하는 방법
2. 최단거리 best를 임의로 정해놓고 best를 넘으면 다시 길로 가고, 다 돌았는데 best값이 없으면 best++

탐색방법 선택하기

1. 너비우선탐색을 최 우선으로 고려(메모리로 시간을 산다.)
2. 깊이가 정해져있고, 메모리와 시간이 많이 걸리면 양방향 탐색을 한다.
3. 두 탐색이 메모리사용이나 시간이 많이 걸릴 경우 점점 깊어지는 탐색을 한다.

상태에 대한 여러연산을 최대한 효율적으로

배열, 일대일대응, 비트마스크 -> 가능한 적은 양의 메모리를 사용해야 한다.