나는 처음 엔 Wikipedia에서 얻은 Bellman-Ford 알고리즘의 유명한 엔화의 최적화를 발견 한 후 운동 섹션의 여러 교과서에서 같은 개선을 발견했습니다 (예를 들어, 이것은 24-1 Cormen에서는 Web exercise N5으로, Sedgewick의 "알고리즘"에서는 Web exercise N5).Bellman-Ford에 대한 엔의 개선
여기 개선 같습니다
엔의 제 개선 먼저 모든 정점에 어떤 임의의 선형 순서를 할당하고, 두 개의 서브 세트들로 전체 에지들의 세트를 분할한다. 제 1 서브 세트 (Ef)는 모든 엣지 (vi, vj)를 포함하여, i<j; 두 번째 요소 인 Eb는 i> j와 같은 모서리 (vi, vj)를 포함합니다. 각 꼭지점은 v1, v2, ..., v | V |의 순서로 방문하여 Ef의 각 꼭지점에서 각 나가는 가장자리를 이완시킵니다. 그런 다음 각 정점을 v | V |, v | V | -1, ..., v1 순서로 방문하여 Eb의 각 정점에서 각 나가는 가장자리를 완화합니다. 알고리즘의 메인 루프의 각 반복은 첫 번째 이후에, 이완 된 거리가 정확한 최단 경로 거리와 일치하는 에지 세트에 적어도 두 개의 에지를 추가한다 : 하나는 Ef로부터 하나는 Eb로부터 하나. 이 수정은 알고리즘의 주 루프의 최악의 반복 횟수를 | V | - 1 - | V |/2.
불행히도, 나는이 경계 | V |/2의 증명을 찾을 수 없었고, 또한 반례를 발견 한 것 같습니다. 나는 그것이 틀렸다는 것을 확신하지만, 정확히 어디에서 볼 수는 없습니다.
반례는 단지 1에서 n까지의 꼭지점과 초기 꼭지점 1로 표시된 경로 그래프에 불과합니다. 따라서 i가 1에서 n-1 범위 인 경우 E = {(i, i + 1)}입니다. 이 경우 정점 집합은 E (E_f = E)와 같고 뒤쪽 정점 집합은 빈 집합입니다. 알고리즘의 각 반복은 올바르게 계산 된 거리를 하나만 추가하므로 n-1 시간에 알고리즘이 완료되며 제안 된 경계 n/2와 모순됩니다.
내가 뭘 잘못하고 있니?
UPD : 그래서 실수는 매우 어리 석습니다. 나는 꼭지점을 통한 반복을 고려하지 않았고, 경로 비용의 즉각적인 업데이트로 반복을 고려했습니다. 나는이 주제를 삭제하지 않고있다. 왜냐하면 누군가가이 개선안을 재미있게 볼 수 있기 때문이다.
네, 단지 몇 시간 만 반복 대신 모든 비용을 즉시 업데이트한다고 생각했습니다. 어쨌든 고마워. –
@svinja 왜 최적화가 없으면 첫 번째 반복에서 올바른 최단 경로를 모두 찾습니다 ?? 마지막 가장자리에서 첫 가장자리로 긴장을 풀면 사건은 VE입니다. – shawn
@shawn, 당신 말이 맞아, 1에서 n까지의 정점과 초기 정점 1로 라벨이 붙은 정점을 읽었다 고 생각한다. (그래서, E = {(i, i + 1)} 1에서 n-1까지) * "는 마치 가장자리가 정렬 된 (1,2), (2,3) ...인데 E = {}가 순서를 나타내지는 않으며 정점 만 올바르게 정렬됩니다 (Yen의 경우에만 도움이 됨). 개량). 그래서 최적화가 없다면 우리가 말한대로 최악의 순서로 가장자리를 이완시킬 수 있습니다. 나는 그 부분을 제거했다. – svinja