圖論：具有矢量權重的最短路徑

我有一個強連通的有向圖加權的有向圖，其中每個矢量只有非負項。我想找到一個循環，使權重之和與對角矢量之間的角度（[1,1,1，... 1]）最小化。這種事情有沒有算法？圖論：具有矢量權重的最短路徑

我相當有信心，一個貝爾曼 - 福特型算法會給我一個相當不錯的解決方案，但我不認爲這將是-best -...

2014-03-31 DomJack

「向量與[1,1，...，1]之間的角度被最小化」肯定是指定最優性準則的奇怪方式。在一些代數之後，這相當於「sum（x_i）^ 2/sum（x_i^2）被最大化」，這看起來更可能導致算法。（儘管對於通常的圖搜索算法來說，它似乎還不是一個合適的選擇，因爲添加一個邊可以使分母膨脹超過分子...） –

好點。我一直在使用這種形式，但沒有這樣想。經過進一步的考慮，我總是可以旋轉我的參考座標系，這樣我們就可以最小化投影到任何矢量 - 比如說[1,0,0,0，...，0]。你付出的代價是現在的矢量條目可能是負數。因此，我們將xi^2/sum（xi^2）最小化。保存一個總和，我想。 – DomJack

我覺得現在可能是時候濫用一些「不夠好的」近似的不平等。 Cauchy-Swarz將2-範數計算降至1範數，將三角不等式與1-範數的總和相關... – DomJack

由於弧可以多次使用，因此可以將此問題制定爲quadratic program。如果實例不大，那麼嘗試使用維基百科鏈接的解算器可能是值得的。

讓我們採取循環x的可行解，即簡單循環的正線性組合。設A是表示從弧到矢量的線性映射的矩陣。有一個技巧，用一個小代數證明：不是將Ax相對於全1矢量的角度最小化，而是將Ax的長度最小化，受限於Ax和全1矢量的點積爲1的限制。

現在我們可以寫下二次程序。

minimize y1^2 + ... + yn^2 (positive semidefinite objective) 
subject to 
Ax - y = 0 
x is a circulation

最後一個約束分解爲線性約束x >= 0，併爲每個頂點，即x值在進入頂點弧總和等於x值的上弧留下的總和。

來源

2014-04-08 21:10:27

啊，好的舊的二次編程。我是怎麼做數學學位的，從來沒有遇到過這個問題？謝謝，最有幫助。雖然我相信這會起作用，但對於那些閱讀，我認爲我會稍微有點不同。如果我們讓M = [A | -d]，其中d是[1,1，...，1]^T且y = [x^T，k]^T，則完美對齊的解將滿足M * y = 0。唉，y> = 0表示這並不總是有一個解決方案，所以相反，我們可以最小化rr，服從M * y = r且y> = 0。 – DomJack

@DomJack它是純粹的數學程度嗎？與應用類型不同，它們傾向於在緊湊集合上看到連續的功能，並稱它爲一天。 –

負數，應用。我聽到像'圖論'和'分析'這樣的術語，但更多的是建模重點。仍然非常有用，不要誤解我的意思 - 我實際上可以掌握大部分我正在閱讀的維基百科頁面的基本概念 - 只要我不知道要搜索什麼術語;） – DomJack

據我瞭解Bellman-Ford Algo似乎是Dijkstra Shortest Path Algo所做的一樣。但它的貪婪行爲更快。

編輯：Dijkstra只適用於非負項目。但是，這將適合你的問題

來源

2014-03-31 07:39:23 DaTebe

不，它不會。即使矢量的所有條目都是正數，它們之和的角度可以隨着另一個的增加而減小。考慮[1,0]和[0,1]向量的情況。（[0,1]和[1,1]]之間的夾角=π/ 4 注意：（（[[0,1] + [1,0]）和[上面的例子顯然是2D的，但我想能夠推廣到ND。 – DomJack

考慮共享一個公共頂點的兩個週期。完全有可能有正整數p和q，所以p次是第一次循環的矢量加到q次第二次循環的矢量上，恰好等於（1,1，...，1）的倍數。因此，除非你限制爲簡單的週期，否則我不認爲你有一個快速算法可以證明是最優的。即使你只限於簡單的週期，你也可以讓週期的一部分等於一個向量x，剩下的週期等於一個向量c（1,1，...，1） - x，可能無法知道這一點，除非你列舉了所有的週期，只是檢查它們。因此，我認爲如果您想要最佳解決方案，強力枚舉週期可能是解決您的問題的唯一可行方法。

來源

2014-03-31 18:08:48 user2566092

感謝您的回覆。我嘗試了一種強力方法，但甚至不知道如何處理結果。我可以在圖中找到所有簡單的循環，並將所涉及的邊緣向量相加（因爲我可以在這些循環周圍採取任意數量的行程，所以循環之間的行程可以忽略不計）。任務然後變爲：對於每個循環向量xi，在N中找到ai，使得sum（ai * xi）= k * d，其中d = [1,1,1,1]^T 另一種觀察方式它將找到[X，-d] [ak]^T的零空間，其中X = [x0，x1，x2，x3，...]和a = [a0，a1，a2，... ]^T。 – DomJack

這本身是相當平凡的（至少在文獻中有很好的論述），但它仍然給我帶來了大量的零空間向量（我的特殊問題有長度爲16的約2.5m週期向量，導致2.5m - 16/approx 2.5米零空間向量）。不幸的是，這些零空間向量中的每一個都至少有一個負值，這意味着我需要找到導致所有正值的向量的線性組合（任何分數理性值都很好，因爲我們可以稍後調整解）。 – DomJack

總是有簡單的蠻力方法 - 嘗試所有向量的所有組合 - 但這是非常昂貴的 - 我最好猜測它是週期數的階乘，它本身就是頂點數量的指數。我不喜歡我完成O（（^^）！）〜O（e ^（N^2））算法的機會...所以我想我會看到什麼stackoverflow必須說:)。 – DomJack

圖論：具有矢量權重的最短路徑

回答

相關問題