差異制約

Question

假設我們想用貝爾曼 - 福特，以儘量減少max_i X_I - min_i X_I

在變量X_1，X_2，... x_n（可變的總n個）

受m形式限制x_i - x_j < = c_ {i，j}

其中c_ {i，j}是一個指定的常數，可以是負數。

我如何能證明貝爾曼 - 福特可以用來解決此類問題的O（N * M）的時間？

我曾嘗試以下：

創建一個節點i爲每個變量X_I

使源節點s

創建從s 0重量邊緣到所有其它節點

不知道該怎麼做後...請幫助，謝謝。

Answer 1

這裏是我的做法，但我不認爲這是O（m * n個），但它可能會引導你在正確的方向。嘗試在畫圖好事，假設我們有以下限制：

相應的約束圖如下所示：

現在請注意，在你的情況有一套完整的約束，所以約束圖將是一個完整的圖。現在我們將考慮問題中圖中的路徑。現在考慮從x_i開始到x_j結束的路徑。這通過點x_i1，x_i2 ...，x_ik。所以我們的路徑是{x_i，x_i1，...，x_ik，x_j}。由於設置了不等式的方式，這條路徑給了我們一個新的約束（x_i_x_i1）+（x_i1_x_i2）+ ... +（x_ik_x_j）= x_i_x_j。

即使我們有一個約束x_i-x_j < = c [i，j]，我們可以通過其他約束的線性組合來找到更緊的約束，這些約束由路徑這個完整的圖。

因此，修復任何頂點x_i並找到最緊的約束條件，即通過bellman ford指向任何其他頂點的最短路徑。然後爲所有我做這件事，並採取最低限度。

Answer 2

在一般的情況下，你不能使用Bellman-Ford算法針對此問題。在anil的回答中提到了一個反例（本頁）。在他的回答中提到的圖中，我們有一個負圓（sum of weights = -1）：x1->x2->x3->x4->x5->x1，所以我們不能使用Bellman-Ford算法對於這種類型的圖形和問題。