重み付けされたエッジが定義されたノード AG、Z のセットがあります。ここで、AG はじょうご内のさまざまなノードであり、Z が一番下にあります。
さまざまなエッジを持つじょうご (V 字型) を視覚化しますが、最終的には最終ノードである Z を指し、水が単一の点 Z に流れ落ちるようにします。じょうご内のすべてのノードをカバーする Z への最も安い経路を見つけたいと考えています。
制約は次のとおりです。
- 孤立したノードはありません (すべてのノードが接続されています/含まれています)。
- 重み付けされたエッジの合計を最小化したい
- 「エッジの共有」は、水が下に流れるときに合体するように、共有エッジの重みを 1 回だけカウントします (つまり、濡れたパスを自由に流れることができます)。
この問題に最適なエッジのセットを見つけるには、どのブースト グラフ アルゴリズムを使用すればよいですか?
- ABDEZは、多くのノードをカバーする安価なパスです
- GにはZへのパスが1つしかないため、CGZは少し強制されます
- FZ は安価に見えますが、CGZ が強制されているため、FGZ は実際には FZ よりも安価であることに気付きます (GZ セグメントを二重にカウントする必要がないため、FG の増分コストは 1 だけです)。
したがって、エッジのセットは (AB、BD、DE、EZ、CG、FG、GZ) である必要があります。
これは新しい問題ではないと確信しています。アルゴリズムを識別/命名するのに十分なグラフ理論を知らないだけです。
アップデート
問題をさらに調査しているときに、グラフが方向付けられていない場合、問題は最小スパニング ツリーに縮小されることがわかりました。言い換えれば、アプリオリに、Z がグラフの最低点であると (矢印を使用して) 指定しなかった場合、水は両方向に流れることが許可されていました (バルブがない限り、一般的に真です)。この 2 番目のモデルは問題なく動作します。
もちろん、古い GZ 有向エッジを強制的に使用する代わりに、新しい FZ 無向エッジを選択して重みを小さくすることができます。
これらの結果に照らして、本当にエッジを方向付ける必要がある場合、liori の答えは元の質問に対する最良の応答です (つまり、アルゴリズムをコーディングする必要があります)。
出力
D <--> E with weight of 1
F <--> G with weight of 1
A <--> B with weight of 2
E <--> Z with weight of 2
C <--> G with weight of 2
F <--> Z with weight of 2
B <--> D with weight of 3
Total Weight = 13
最小スパニング ツリーを使用した無向非巡回グラフのコード
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>
int
main()
{
using namespace boost;
typedef adjacency_list < vecS, vecS, undirectedS,
no_property, property < edge_weight_t, int > > Graph;
typedef graph_traits < Graph >::edge_descriptor Edge;
typedef graph_traits < Graph >::vertex_descriptor Vertex;
typedef std::pair<int, int> E;
char letter[] = "ABCDEFGZ";
const int num_nodes = 8;
E edge_array[] = {
E(0,1), E(1,2), E(1,3), E(3,6), E(3,5), E(3,4), E(2,5), E(2,6),
E(5,7), E(5,6), E(6,7), E(4,7)
};
int weights[] = { 2, 6, 3, 5, 3, 1, 4, 2, 2, 1, 3, 2 };
std::size_t num_edges = sizeof(edge_array) / sizeof(E);
Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
property_map < Graph, edge_weight_t >::type weight = get(edge_weight, g);
std::vector < Edge > spanning_tree;
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));
int total_weight = 0;
for (std::vector < Edge >::iterator ei = spanning_tree.begin();
ei != spanning_tree.end(); ++ei)
{
std::cout << letter[source(*ei, g)] << " <--> " << letter[target(*ei, g)]
<< " with weight of " << weight[*ei]
<< std::endl;
total_weight += weight[*ei];
}
std::cout << "Total Weight = " << total_weight << std::endl;
return EXIT_SUCCESS;
}