최단 경로 구하는 알고리즘들 질문이 있습니다.

  • mihaly
    mihaly

    JMBook으로 최단경로를 구하는 알고리즘들을 공부하고 있습니다.
    다익스트라, 벨만-포드, 프로이드 알고리즘까지 봤는데요.
    책을 다 안 읽고 DRUNKEN 문제를 풀려고 했는데 벨만-포드 알고리즘으로 시도를 했었습니다.
    근데 안 풀리더라고요 잘 풀리는 것 같은 느낌은 들었는데.
    그래서 좀 생각을 해봤는데 벨만-포드 알고리즘으로 풀리지 않는 경우가 있더라고요.
    왜 풀리지 않을까 생각을 해보니 s를 시작점이라 하고 두 정점 u, v이 있고 s부터 v까지의 최단 경로가 s -> ... -> u -> v라고 했을 때 이 경로에서의 s -> ... -> u가 s에서 u까지의 최단경로가 아닐 수도 있더라고요.
    그래서 생긴 의문점인데 벨만-포드 알고리즘은 경로의 성질이 optimal structure여야 적용할 수 있는 알고리즘인가요?
    그리고 프로이드 알고리즘도 공부했는데 그것도 optimal structure의 성질을 이용하는 것 같은데 맞는건가요?

    요약: 최단 경로 알고리즘들이 optimal structure에만 적용이 가능한 것인지?

    감사합니다.


    6년 전
9개의 댓글이 있습니다.
  • Being
    Being

    벨만-포드 알고리즘의 수행 도중에는 s ---> v 까지의 중간 계산된 최단 거리는 s ---> u -> v 가 아니거나 u가 아닌 다른 정점인 x를 거친 경로인 s ---> x -> v 를 따를 수 있지만, 알고리즘의 수행이 종료되면 모든 정점에 대한 최단 경로는 정상적으로 계산됩니다.

    다른 말로, 벨만-포드는 각 바깥 루프가 수행될 때마다 최단 경로를 구성하는 간선의 수가 1, 2, .., V - 1개 이하인 최단 경로를(엄밀히 말하면, 간선의 수가 i개 이하인 최단 경로보다 좋거나 같은 경로를) 계산함으로써 최단 경로를 계산하는 알고리즘입니다. 따라서 질문해주신 바와 같은 경우는 u -> v 간선이 s ---> u 까지의 최단 경로가 갱신될 때마다 계속해서 relax 될 것이므로 발생하지 않습니다.


    6년 전 link
  • Being
    Being

    그리고 optimal structure에 대해 질문 주신 내용은 optimal substructure 를 의도하신 것 같은데요, 벨만-포드 같은 알고리즘들은 그래프가 특정 조건을 만족하기만 하면(e.g. 벨만 포드의 경우 음수 사이클이 없다면) 계산하는 값의 정의를 잘 잡음으로써 optimal substructure를 구성합니다. 즉, 간선의 수가 i개 이하인 최단 경로(보다 좋거나 같은 경로)가 최적이어야 i+1개 이하인 것을 구할 수 있다고 설명드리면 이해되실지 모르겠네요.


    6년 전 link
  • mihaly
    mihaly

    //Being
    답변 감사합니다. optimal substructure였네요. "계산하는 값의 정의를 잘 잡음으로써 optimal substructure를 구성합니다." 이 말은 즉 optimal substructure을 구성해야만 적용할 수 있다는 말일까요?
    DRUNKEN 문제에서
    5 5
    1 10 30 100 1
    1 2 30
    1 3 20
    2 4 20
    3 4 20
    4 5 5
    1
    1 5

    입력을 벨만-포드 알고리즘으로 구해봤는데 145가 나와야하는데 155가 답으로 나와서요. 이 경우가 제가 생각했던 본문에 썼던 경우이고요.


    6년 전 link
  • mihaly
    mihaly

    아 그리고 제가 본문에서 말한 벨만-포드가 제대로 답을 못 찾는 경우는 일반적인 최단 경로 문제가 아닌 DRUNKEN 문제에서의 최단 경로를 말한 것이었습니다.


    6년 전 link
  • Being
    Being

    구현하신 알고리즘의 각 수행 단계별 계산을 다시 한 번 검토해 보시길 바랍니다 :)


    6년 전 link
  • Being
    Being

    아 그렇군요. 그런데 이 경우 벨만-포드를 어떻게 적용하셨는지 궁금하네요. 주어진 문제가 '그냥 최단 경로를 계산하라'는 문제가 아니었기 때문에, 모델이나 알고리즘에 어떤 변형을 가해서 계산하셨을 텐데 어떤 의도로 푸셨는지 전달이 잘 되지 않은 것 같습니다.


    6년 전 link
  • mihaly
    mihaly

    핵심적인 코드만 적으면 아래와 같습니다.
    naive하게 생각해서 경로 길이 합과 그 경로 상의 delay값의 최고값을 저장하고 이를 relaxation의 조건으로 활용했는데 뭔가 잘못된 접근인 것 같긴 하네요.

    // Initialization
      fill(upper, upper + v, pINF);
      fill(delay, delay + v, 0);
    
      // Solve
      upper[from] = 0;
      int init_delay = d[from];
      d[from] = 0;
      for ( int i = 0; i < v - 1; i++ ) {
        bool relaxed = false;
        for ( int j = 0; j < v; j++ )  {
          for ( vector< pair<int, int> >::iterator it = m[j].begin();
                it != m[j].end(); it++ ) {
            if ( upper[j] == pINF ) continue;
            if ( upper[j] + it->second + max(delay[j], d[j]) < upper[it->first] + delay[it->first] ) {
              upper[it->first] = upper[j] + it->second;
              delay[it->first] = max(delay[j], d[j]);
              relaxed = true;
            }
          }
        }
        if ( !relaxed ) break;
      }
    
      cout << upper[to] + delay[to] << endl;
    
      // Ending
      d[from] = init_delay;
    

    생각을 더 해봐야겠습니다.


    6년 전 link
  • Being
    Being

    이 경우 부분 경로의 delay의 최고값이 다른 여러 가지 경우가 있을 수 있는데, 해당하는 경우들 중에서 한 가지만 저장하셨으므로 말씀해주신 바와 같이 optimal substructure 성질이 성립하지 않게 되겠지요. 달리 말하면 이 경우에 '현재까지의 delay의 최고값'은 최적화하기 위한 목표값이라기보다는 현재 상태에 더 가까운 값입니다.


    6년 전 link
  • mihaly
    mihaly

    감사합니다. 주어진 문제를 어떻게 optimal substructure로 재구성하는지가 핵심이 되겠군요. 더 열심히 생각해봐야겠네요.


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.