01.27

AI

Floyd

모든 node에서 다른 node로 이동 가능한 최단거리를 계산하는 알고리즘
$O(V^3)$의 연산시간을 가지므로 실시간으로 연산하는것은 부담스러움
실시간 연산이 어렵다보니 런타임에 map에 장애물이 추가된다던가 하는 경우의 처리가 어려움
반면 A Star의 경우 실시간연산이 가능하므로 map에 장애물 추가등에 대한 반응이 가능

Map

방향성이 있어야함
예를 들어 PC가 절벽에서 떨어질 수는 있지만 절벽을 거슬러 올라가기는 힘들다
Array 기반 Map과 Graph 기반 Map으로 구현 가능

경로 산출

기본적으로 Floyd 알고리즘은 모든 node에 대한 모든 node로의 최단거리를 계산하는 알고리즘으로 경로를 산출하지는 않음
다만 약간의 변형과 추가적인 메모리를 더 사용한다면 쉽게 경로 산출 역시 가능함

가장 간단한 방법은 Path[A][B]에 vector정보를 저장하는 3차원 방식
메모리 소모량이 $O(V^3)$이지만 $O(1)$의 시간복잡도

또는 최단 경로 트리를 이용해서 산출도 가능
이 경우 $\theta(V)$의 공간복잡도(라고 하는데 개인적으로 $O(V)$인것으로 보임...)와 $\theta(E)$의 시간복잡도로 산출 가능

Reference : https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#%EA%B2%BD%EB%A1%9C_%EB%B3%B5%EC%9B%90

Floyd 알고리즘의 증명

for(int k : vertice)	// 중간 경로
{
	for(int i : vertice)
    {
    	for(int j : vertice)
        {
        	weight[i][j] = min(weight[i][j], weight[i][k] + weight[k][j]);
        }
    }
}

Floyd 알고리즘의 sudo 코드를 보면 i->j로 가는 경로 중 k를 거쳐갈 경우 그 비용이 더 싸다면 경로를 변경하는 알고리즘으로 보인다

즉, 다시말해 $Weight[i][j] = shortest[i][k] + shortest[k][j]$로 보이는데, 이 경우 "임의의 k"에 대하여 $shortest[i][k]$가 보장되지 않는다면 사용할 수 없는 알고리즘일 것이다
이러한 관점에서 위 sudo 코드가 "임의의 k"에 대하여 $shortest[i][k]$가 보장되는가라는 부분에서 의문이 생겼다

결론부터 말하자면 "임의의 k"에 대하여가 아니라 "{ 1, 2, ..., k }의 꼭지점만을 사용했을때"가 중요한 부분이었음
자세한 부분은 Reference 참고

Reference : https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98