최적경로 알고리즘 질문입니다!

출발점, 도착점이 있고

출발점에서 출발하여, 모든 정점을 지나고, 도착점에 도착하는

최단경로를 구하는 문제를 DFS로 풀긴했습니다.

그런데 실행시간이 1000ms 넘게 나오는데 비해 10ms 로 나오는분들이 있어서

코드를 보니까 다익스트라 알고리즘을 사용했습니다.

그런데 다익스트라는 모든 정점을 지나는 방식이 아닌 최단거리니까

다익스트라를 그대로 사용하면은 안된다 생각하고있습니다..

어떤 방식을 사용할지 감이 안잡히는데

팁 조금 부탁드립니다~

1답변

  • 좋아요

    1

    싫어요
    채택취소하기

    잘 알고 계십니다. 다익스트라 알고리즘은 모든 점을 지나는 것이 아닌, 그냥 목적지까지 가장 빠르게 도달하는 알고리즘이죠.

    모든 점을 다 거쳐야만 한다면, 이건 순회 세일즈맨 문제(Travelling salesman problem, TSP. ,스펠링 맞는지 몰것음.) 입니다. 단, 원래 점으로 되돌아 올 필요는 없으니, 약간 변형된 순회 세일즈맨 문제입니다.

    이건 수학적으로 NP 하드에 해당하며, 경우의 수를 다 때려박는 것 외에는 최적을 한방에 찾아내는 알고리즘 따위는 없습니다.

    저라면 이렇게 풀겠습니다.

    1. 적당히 대충 솔류션을 하나 찾는다.
    2. 1의 코스트를 기록
    3. 유전알고리즘으로 1~2 과정을 몇 번 반복.
    4. 이제 꽤 괜찮은 코스트를 가진 경로를 하나 찾았을 거임. 여기까지는 굉장히 신속하게 풀림. 이 수 차례에 걸쳐 찾아낸 미니멈 코스트를 V라고 한다.(아직 V는 최적해라고 증명되지 않았다)
    5. 이제 모든 경우의 수를 다 탐색하되, 단 아래와 같은 조건을 어길 경우, 이미 싹수가 노란 솔류션이므로 탐색을 중단하고 바로 다음 단계로 넘어간다.
    - [지금 방문하고 있는 노드까지의 코스트] + [전체 패스 코스트 중 미니멈패스코스트]*[남은노드수] >= V 일 경우, 싹수가 노랗다.
    
    - 지금 방문한 노드가, 들어오기만 하고 나갈 방법이 없는 노드일 경우
    
    1. 5의 조건을 다 뚫고, 모든 노드를 다 방문했는데 , 그 코스트가 V보다 작다면, V를 업데이트하고 지금부터 개선된 V로 나머지 경우의 수를 다 방문한다.

    2. 더 이상 조합이 없으면 종료한다. 지금까지 찾아낸 V와 그 경로가 최적경로.

    H = { [전체 패스 코스트 중 미니멈패스 코스트]* [남은 노드 수] } 는 가장 옵티미스틱하게 남은 경로의 길이를 예측하는 부분인데, 이 부분을 개선하면 좀 더 성능이 나을 겁니다. 예를 들어서 전체 패스 길이에 대한 리스트를 가지고 있으면서 그걸 소팅해서 작은 순서로 정렬한 리스트를 가지고 , 순서대로 어큐뮬레이트 해 놓은 리스트를 만든 다음에, H 대신에 남은 노드 수에 해당하는 리스트의 요소를 가지고 와서 더해준다던가 해도 되겠죠.

    요는, 얼마나 싹수가 노란 놈을 빨리 판단해서 끝까지 다 탐색하지 않고 중간에 잘라내는가 입니다.

    그 외에는, 멀티코어를 활용해서 짤 수 있다면, 역시 극적으로 시간이 줄어들 겁니다.

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

작성한 답변에 다른 개발자들이 댓글을 작성하거나 댓글에 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.