最小平均重量週期 - 直觀解釋

Question

在有向圖中，我們正在尋找具有最低平均邊權重的週期。例如，節點1和2的路徑從1到2的長度爲2和長度爲4的從2到1的節點的最小平均週期爲3.

不尋找複雜的方法（卡爾普），但一個簡單的回溯剪枝解決方案。解釋如下：「在當前運行平均值大於最佳找到的平均重量週期成本的情況下，可以通過重要的修剪來回溯。」

但是，爲什麼此方法有效？如果我們正處於一個週期的一半，並且體重超過了最佳找到的平均值，那麼我們是否有可能達到這樣一種情況，即我們當前的週期可能低於最佳平均值？

編輯：這是一個樣本問題：http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031

Answer 1

允許對於給定的圖最優解是具有平均邊緣權重X.一個週期

沒有與邊緣e_1，e_2一些最佳週期... e_n ，例如avg(e_i) = X。

對於我的證明，我假設所有索引模n，所以e_(n + 1)是e_1。

比方說，我們的啓發式無法找到這個解決方案，這意味着：每個i（我們採取了先不論邊緣）存在這樣j（我們遵循所有邊緣從i到j到目前爲止），在平均邊緣重序列e_i ... e_j大於X（啓發式修剪此解決方案）。

然後我們可以顯示平均邊權重不能等於X.讓我們取一個未被啓發式修剪的最長連續子序列（每個元素的平均邊權重不大於X）。至少有一個e_i <= X，所以存在這樣的子序列。對於這樣的子序列的第一個元素e_k，存在p，例如avg(e_k ... e_p) > X。我們先拿這樣的p。現在讓我們取k' = p + 1並獲得另一個p'。我們將重複這個過程，直到我們再次觸及我們最初的k。最終p可能不會超過初始k，這意味着最終子序列包含初始[e_k, e_p - 1]，這與我們的e_k的構建相矛盾。現在我們的序列e_1 ... e_n完全覆蓋了非重疊的子序列e_k ... e_p,e_k'...e_p'等，每個人的平均邊權重大於X.所以我們有一個矛盾，即avg(e_i) = X。

至於你的問題：

如果我們中途一個週期，重量超過最佳 發現平均，是不是有可能，有小，重量輕的邊緣，我們可以 達成情況我們目前的週期可以低於最好的 發現的意思？

當然是了。但是我們可以安全地修剪這個解決方案，因爲稍後我們會發現從另一個邊緣開始的同一個循環，這不會被修剪。我的證明指出，如果我們考慮圖中每個可能的週期，我們遲早會找到一個最佳週期。