質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

最適化

最適化とはメソッドやデザインの最適な処理方法を選択することです。パフォーマンスの向上を目指す為に行われます。プログラミングにおける最適化は、アルゴリズムのスピードアップや、要求されるリソースを減らすことなどを指します。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

1回答

1962閲覧

グラフ理論最適化問題 辺の重複度最小化 解法のアルゴリズムがわかりません。。

AtsuyaShono

総合スコア11

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

最適化

最適化とはメソッドやデザインの最適な処理方法を選択することです。パフォーマンスの向上を目指す為に行われます。プログラミングにおける最適化は、アルゴリズムのスピードアップや、要求されるリソースを減らすことなどを指します。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2019/06/05 18:11

編集2022/01/12 10:55

グラフ理論最適化問題

グラフ理論の最適化のプログラミング解法について行き詰まっているので、どうかお力添え願いたいです。
説明が長く、わかりにくい表現もあるかもしれませんが、質問などしてくださればお答えしたいと思っています。
よろしくお願いします。

ちなみに言語は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である。

困っていること

この問題は後の採用された経路がわからないとその前の経路が本当に重複度が最小かわからないことが最大のネックです。
なので単純にグループごとに経路を決めていっても、重複度は小さくならないと思います。

ネットで似たような解法が見当たらず質問に至りました。

例えば、先にルーティングしておくと比較的、後の経路が重複しなくなるようなグループの順番でルーティングする方法(どうすればいいか探す必要がありますが。。)や、数理計画法のようなアプローチができるかと考えましたが、他に良い方法がありませんでしょうか?

様々なアイデアをいただければありがたいのと、似たような解法が紹介されているサイトなどあれば教えていただきたいです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2019/06/06 01:47 編集

ルールが良くわからないです. * グループ0がエッジ5-6を使わずにエッジ1-6を使えば重複度が下がるように見えるのですが. * グループ1の繋ぎ方は「二つ考えられる」とされているが,0-4を使わない方法もあるように見える.
AtsuyaShono

2019/06/06 06:34

ご質問ありがとうございます 説明不足申し訳ありません 補足としてこの問題は有向グラフです。 図も矢印を付けて訂正しておきます。 もし無向グラフであれば、グループ0はエッジ5-6ではなくエッジ1-6を使う経路もありでした。 しかし有向グラフなので、fanaさんのグループ0の経路だと補足図1のようにコネクトID3の元の5から繋げる先の6につながっていないことになります。 2つ目は補足図2のような方法でしょうか? もしそうならば、エッジ5-6を使ってしまうのでもっと重複度を下げる経路があると言えます。 ”2つ”というのはあくまでいろんなパターンがある中で例として2つあげさせていただきました。他にも経路はたくさんあります。その中で重複するのをなるべく下げたい次第です。
fana

2019/06/06 08:26

お手数をおかけしてしまい申し訳ありません. > 有効グラフ 「元」と「先」という記述から把握して然るべきでした.(恥ずかしい) > fanaさんのグループ0の経路だと補足図1のようにコネクトID3の元の5から繋げる先の6につながっていないことになります。 この場合,5から6への経路を確保するために,5->1を追加してエッジ1-5を両方向で使うとしたら,このグループの重複度は6に増えてしまうという認識で合っていますでしょうか.
AtsuyaShono

2019/06/06 09:25

はい、その通りです。
guest

回答1

0

(頭が足りない人の馬鹿な戯言である可能性が高いと思うので,そうである場合には遠慮なく低評価の連打をお願いします!)

最終的な結果の重複度の値が低い側から「できるかできないか」を調べていく……なら,「できた」時点でそれが最小(なパターンのうちの1つ)だということが確定するんじゃないでしょうか.

例えば,
各グループが自分しかいない世界で最適なルーティングを行った場合の重複度を求めて,その最大値から「できるかできないか」を調べていけばよい.(それより低い重複度では絶対にできないから)
仮にグループaの重複度がS_aで最大なのだとしたら,重複度S_aでできるパターンがあるか否かを調べるには,
【グループaのそのルーティングパターンに用いたエッジを取り除いた世界において,aを除いた残りのグループ群を「重複度S_a以下でルーティングできるか」問題】に取り組めば良いように思う.(再帰的に小さい問題になっていく…かな?)

上記【】が「できない」とわかったら,グループaの次に重複度が小さいパターンに関して同様に調べていく… 的な……

投稿2019/06/06 10:40

編集2019/06/06 10:41
fana

総合スコア11634

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

AtsuyaShono

2019/06/06 16:52

なるほど! 自分では考えつかなかったロジックです。 参考にして考察させていただきます。 ありがとうございます!
fana

2019/06/26 01:20 編集

この回答に関して,「回答への高評価(+)が取り消されました」というアクションがあった模様. それ自体は構わないのですが(元から低評価来いや!という勢いですし),この考え方だと良くない(うまくいかない?)みたいな話であれば純粋に興味があるので, 可能であれば指摘(?)のコメント頂けると嬉しいです.
AtsuyaShono

2019/06/26 15:42

すみませんおそらく誤操作です、、 この回答を参考にしてプログラムを組もうと思っています 他にもいくつか実験してこれが正しいか検証していくつもりです あまり時間がなくてこの課題をあまり進められていないのでまだまだ先になりそうです
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問