9개의 댓글이 있습니다.

• 
  Being

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

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

  
  10년 전 link

• 
  Being

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

  
  10년 전 link

• 
  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가 답으로 나와서요. 이 경우가 제가 생각했던 본문에 썼던 경우이고요.

  
  10년 전 link

• 
  mihaly

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

  
  10년 전 link

• 
  Being

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

  
  10년 전 link

• 
  Being

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

  
  10년 전 link

• 
  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;
  

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

  
  10년 전 link

• 
  Being

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

  
  10년 전 link

• 
  mihaly

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

  
  10년 전 link

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