グラフ理論最適化問題
グラフ理論の最適化のプログラミング解法について行き詰まっているので、どうかお力添え願いたいです。
説明が長く、わかりにくい表現もあるかもしれませんが、質問などしてくださればお答えしたいと思っています。
よろしくお願いします。
ちなみに言語はc++です。
問題定義
#####入力
ノードの数
エッジの数
コネクトの数
グループの数
エッジの両端点のノード番号
ここでコネクトとグループとは以下の通りとします
コネクト(繋げなければならないノード同士)
繋げたい出発地点のノード番号
繋げる目的地点のノード番号(複数あり)
グループ
複数のコネクト(複数あり)
#####問題
例として以下のようにグラフがあり、コネクト、グループがあるとします。
※補足 グラフは有向グラフです。双方向につながるわけではありません。向きも考慮しなければなりません。
それぞれグループごとにコネクト通りに、つまり出発地点からどこかの経路を通って到着地点のノードに繋げなければなりません。
なおかつ、同じ辺を使うのを避け、辺の重複度を最小化したいという問題です。
例えば、グループID.0をルーティングするとこのような感じになります。
上の図はコネクトID.0,1,2のように全て繋げることができる例の一つです。
これでグループID.0はルーティングできました。
※補足図1 不可な例です。
これではコネクトID.2を満たしていません。5から6に繋がっていないです。
エッジ1-5が双方向につながるわけではないからです。
次にグループID.1をルーティングすると以下のように二つ考えられると思います。
ここでどちらのパターンを選ぶかは、同じ辺を使うのを避けるとすると、グループID.0で使用されている5と6を結んでいる辺を使っていない前者のパターンを採用するべきです。
補足図2 以下もエッジ5-6が使われているのでそれより1番目の例の方が最適であると言えます。
次にグループID.2は同じように以下のようになります。
この場合は5と6の辺以外を通ると他の辺の重複度が増してしまうので5と6をつないでいる辺の重複度は増してしまうがこれが最適である。
以上のようにルーティングしたとすると各辺の重複度は以下のようになる。
そして、グループ内で通る経路の重複度の合計最大値を最小化することが目的である。
この例だと重複度合計はグループID.0は4,ID.1は3,ID.2は3,
よって最大値は4である。
困っていること
この問題は後の採用された経路がわからないとその前の経路が本当に重複度が最小かわからないことが最大のネックです。
なので単純にグループごとに経路を決めていっても、重複度は小さくならないと思います。
ネットで似たような解法が見当たらず質問に至りました。
例えば、先にルーティングしておくと比較的、後の経路が重複しなくなるようなグループの順番でルーティングする方法(どうすればいいか探す必要がありますが。。)や、数理計画法のようなアプローチができるかと考えましたが、他に良い方法がありませんでしょうか?
様々なアイデアをいただければありがたいのと、似たような解法が紹介されているサイトなどあれば教えていただきたいです。