最小全域木について

質問

現在、最小全域木の問題はグラフ理論や遺伝的アルゴリズムの文献など様々な分野で解説されていますが、この「最小全域木」について気になることがあります。

最小全域木とは辺に対して一つの重みがあるものですが、この重みが多重化すること、つまり一つの辺に対して二つ以上の重みが存在する最小全域木とは存在しないのでしょうか？？

つまりは「二重の重みを持つグラフ」を対象とした研究とは世の中では行われていないのでしょうか？？

厳密な解を求めるのが不可能など、様々な問題が生じてくるから不可能なのかなと思ったりしたのですが、、、違うのでしょうか？？

もし、この分野に詳しい方がいらっしゃったら返事をお願いしたいです。

回答No.2

noocyte · ベストアンサー

そもそも最適化に使用できる重みは１組だけだと思いますので，
複数の重みを最適化でどのように使うのかが理解できません．
(つまり，どの重みに対して最小化すればいいの？ということです．)

事前に設定された複数の重みを演算して１つの重みを求めることが，
最適化の途中結果に依存するということなのでしょうか？
(例えば，最適化の途中結果に応じて，複数の重みから１つを選ぶとか．)

回答No.1

driverII

研究されているかたはいらっしゃるようですが・・・

参考URL：

http://www.is.oit.ac.jp/material/sotsuken-2006.html#ichimori