在jgraph中創建成本函數

Question

jgrapht支持在兩個節點之間的邊緣/頂點上放置wehight（成本）的想法。這可以使用DefaultWeightedEdge類來實現。

在我的圖中，我確實有要求找不到最短的路徑，但最便宜的。最便宜的路徑可能會更長/有更多的跳躍節點可以在最短路徑上行進。因此，可以使用DijkstraShortestPath算法來實現這一點。

但是，我的用例有點複雜：它還需要評估到達節點時需要執行的操作的成本。假設你有一個像國際象棋棋盤（8×8字段，每個字段都是一個節點）的圖形。所有的邊都有1的權重。要從一個汽車從左下角移動到對角線（右上角），有許多路徑，成本爲16.您可以採用zic zac風格的對角路徑，或者您可以首先將所有節點向右移動，然後向上移動所有節點。 區別在於：在拍攝zic zac時，您需要按照移動的方向旋轉自己。你旋轉16次。 當首先向右移動然後向上時，您只需旋轉一次（也許兩次，取決於您的開始方向）。 所以zic zac路徑從Djikstra的角度來看是完美的。從邏輯的角度來看，這是最糟糕的。

長話短說：我如何在節點或邊緣上放置一些費用，具體取決於該路徑中以前的邊緣/節點？我沒有在jgrapht的源代碼中找到任何相關的東西。 還是有更好的算法使用？

Answer 1

這不是一個JGraphT問題，而是一個圖算法問題。您需要考慮如何對此問題進行編碼並將其更形式化，更詳細地說

1. 合併頂點上的權重通常很容易。假設每個頂點都代表訪問一個客戶，這需要花費時間。這可以通過將a_i/2添加到節點i中每個輸入弧的成本以及每個輸出弧的成本的a_i/2來編碼在圖中。

2. 一個成本函數，其中從j到k依賴者在您用來前往j的弧（i，j）上移動的成本更爲複雜。

方法a：使用動態規劃（標記）算法。這也許是最簡單的。您可以將您的成本函數定義爲遞歸函數，其中遍歷圓弧的成本取決於之前圓弧的成本。方法b .:使用一些技巧，您可以通過向圖中添加額外的節點來對圖中的成本進行編碼。下面是一個例子：

給定一個具有頂點{a，b，c，d，e}，帶有圓弧的圖：（a，e），（e，b），（c，e），（e，d ）。該圖表示頂點e位於中間的交叉路口。從a→e→b（直線）出發是免費的，但是從a→e→d轉彎需要更多時間。類似於c-> e-> d（直線）是免費的，並且c-> e-> b（轉彎）應該受到懲罰。 在4個新頂點中去耦頂點e：e1，e2，e3，e4。 （e1，e3），（e1，e4），（e1，e4），（e4， e2，e4）。 （e1，e4）和（e2，e3）可以具有正的權重來懲罰車削。