jgraphtでコスト関数を作成する

Question

jgraphtは、2つのノード間のエッジ/頂点にウェイト（コスト）を入れるという考え方をサポートしています。これは、DefaultWeightedEdgeクラスを使用して実現できます。

私のグラフでは、最短経路は見つけられないが、最も安い経路は見つけられないという要件があります。最も安いパスはより長くなるかもしれません/最短パスをたどるためにホップノードが増えます。したがって、これを達成するためにDijkstraShortestPathアルゴリズムを使用することができる。

しかし、私のユースケースはちょっと複雑です。ノードに着くときに実行する必要があるアクションのコストも評価する必要があります。

たとえば、チェスボードのようなグラフがあります（8x8フィールド、各フィールドはノードです）。すべてのエッジのウェイトは1です。左下から対角線のコーナー（右上）に移動するには、コストは16です。すべてのノードを最初に右に、次にすべてのノードを上に移動できます。 違いは：ジクザクを取るときは、自分自身を移動する方向に回転させる必要があります。あなたは16回回転します。 最初にすべてを右に移動してから上に移動するときは、1回だけ回転させる必要があります（開始方向に応じて2回）。 ジクザクのパスは、Djikstraの観点からは完璧です。論理的な観点からは、最悪です。

ストーリーショート：そのパスの前のエッジ/ノードに応じて、ノードやエッジにコストをかけるにはどうすればよいですか？ jgraphtのソースコードに関連するものは見つかりませんでした。 使用する方が良いアルゴリズムはありますか？

Answer 1

これはJGraphTの問題ではなく、グラフアルゴリズムの問​​題です。この問題をコード化する方法を考えて、それをより詳細に公式化する必要があります。

1. 一般的に、頂点にウェイトを組み込むのは簡単です。すべての頂点がa_i時間かかる顧客を訪問しているとします。これは、ノードi内のすべての着信アークのコストにa_i/2を加え、すべての発信アークのコストに対してa_i/2を加算することによってグラフに符号化することができます。

2. jへの旅に費やされた円弧（i、j）上のjからkへの移動コストがより複雑なコスト関数は、より複雑です。

アプローチ：ダイナミックプログラミング（ラベリング）アルゴリズムを使用してください。これはおそらく最も簡単です。コスト関数を再帰関数として定義することができます。ここで、弧を横断するコストは、前の弧のコストに依存します。

アプローチ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つの新しい頂点e1、e2、e3、e4で頂点eをデカップリングします。 （a、e1）、（e3、b）、（c、e2）、（e4、d）、（e2、e3）、（e1、e3）、（e1、e4）、 e2、e4）。 （e1、e4）および（e2、e3）は、回転をペナルティするために正の重みを持つことができます。