修改後的Dijkstra找到了給定額外屬性的最優化最短路徑

Question

這是我在here處詢問的問題的後續問題。該問題被映射到邊上具有非負權重的圖表（如果它可以被定向或不定向，則沒有偏好）。然而，除了實際距離的重量外，我們還有另一個屬性，它是邊緣的數據覆蓋率，這可能是重要因素，選擇路線的重要因素我的手機需要多麼嚴格（例如，實時遊戲需要良好的帶寬）。總的來說，我們想要在路徑長度和網絡帶寬之間找到一個折衷方案來解決尋找兩個城市之間最優化和最短路徑的問題。但是，一個重要的特徵是該算法應該是動態的。一旦我們到達節點，根據我們目前的需求狀態，我們可能會改變預定的路徑。

好的。爲了簡單起見，我們假設每條邊都與兩個屬性相關聯：A）距離或旅行時間或其他，作爲常規權重，以及B）網絡帶寬作爲顯示網絡良好性的次要屬性。

約束和目標函數，說，我們要儘量減少總距離（或行駛時間），但根據我們目前的狀態，我們也想盡量減少總斷開時間或最大化total sum of path bandwidths 。可選地，假設我們不能容忍總持續斷開時間超過閾值T。所以這可能是對問題的限制。最簡單的這種目標函數可以是f()=total time of travel + a*time of disconnection。係數決定了每次連接對我們來說有多重要。

爲了解決邊緣可能部分斷開的事實，經過一番思考，我進入了一個解決方案，讓我們在其中插入節點。這使問題更容易解決。所以基本上每個路由都有斷開連接，或者連接帶寬爲特定值。

是走進了我的腦子裏，每當我們計算的路徑來積累的總連續斷開時間，所以它無法超越的門檻T第一個版本的解決方案。每當我們到達有連接的路由時（無論帶寬是否更簡單），我們都會重置累加。考慮到帶寬，因爲我們也有連接帶寬的價值，所以我們可以從總累積斷開時間中扣除連接帶寬的值（是否工作？！）

一個重要的事情是考慮以下示例數字。不超過總斷開閾值不應該導致通過一條非常遠的路線，從而增加總旅行時間！爲此，我考慮了這種一般方法：解決斷開閾值T1, T2, ...Tk的問題，計算最佳路徑（或一組最佳路徑可能？！），並計算每個路徑的相應總行程時間。然後應用我們上面的目標函數，看看什麼是最優解。我們可以進一步在兩個樣本之間尋找解決方案，以使用類似二進制搜索的方法找到更優化的解決方案。

請，有人可以幫我解決這個問題？顯然，我的解決方案是不正確的，如果是這樣，甚至不可能在多項式時間。也許近似算法？！任何有助於找到解決方案，高度讚賞。隨意添加更多細節或假設，或修改問題。問題比我想象的要困難。

Answer 1

首先爲整個網絡找到這個問題的完美答案在計算上是不可行的。請參閱http://phys.org/news/2015-05-maths-congestionsprings-traffic.html以獲得一篇文章，概述您將遇到的一些實際複雜性和數值不穩定性。以及增加道路的示範可能會使整個網絡變得更糟。

但是，我們可以在實踐中很好地解決它，確切地說，您正在查看的IP網絡問題。谷歌搜索給了我https://www.cs.princeton.edu/~jrex/papers/opthand04.pdf作爲從哪裏開始學習文學的建議。