与えられた頂点間を結ぶネットワークで,エッジの長さの総和(≒敷設コスト)の制約を満たし,頂点間の最短路距離の総和が最小(≒輸送効率が最大)になるものを出力します. 頂点数が \( n \) のとき,探索対象のネットワークは \( 2^{\frac{n(n-1)}{2}} \) 個あり,天文学的な数字(\( n = 10 \) で \( 35184372088832 \))になりますが, Dionne-Florianのアルゴリズムを使って効率的に探索します.
SOFTWARE
与えられた頂点間を結ぶネットワークで,エッジの長さの総和(≒敷設コスト)の制約を満たし,頂点間の最短路距離の総和が最小(≒輸送効率が最大)になるものを出力します. 頂点数が \( n \) のとき,探索対象のネットワークは \( 2^{\frac{n(n-1)}{2}} \) 個あり,天文学的な数字(\( n = 10 \) で \( 35184372088832 \))になりますが, Dionne-Florianのアルゴリズムを使って効率的に探索します.
田端祥太
e-mail:tbtgoat.contact[at]gmail.com