-1

ノード数が偶数のリストがあります（常に偶数）。私の仕事は、最もコストのかからない方法ですべてのノードを「一致させる」ことです。

これはlistDegree(1,4,5,6)、グラフ内のすべての奇数次数ノードを表します。listDegreeのノードをペアにして、最もコストの低い組み合わせを変数に保存するにはどうすればよいでしょうかint totalCost。

totalCostこのようなもので、私は最小限の金額を返します。

totalCost = (1,4) + (5,6)
totalCost = (1,5) + (4,6)
totalCost = (1,6) + (4,5)

--------------- 詳細（またはアッパーの書き直し） ---------------

入力ファイルを読み取り、必要なすべての情報 (グラフの costMatrix、エッジ、エッジ、ノードの数など) を格納するクラスがあります。

次に、特定の開始ノードから特定の終了ノードまでのグラフ (costMatrix) 内の最短パスを計算する DijkstrasShortestPath アルゴリズムがあります。

また、グラフ (costMatrix) を調べて、すべての奇数次数ノードをリストに格納するメソッドもあります。

そこで私が探していたのは、すべての奇数次ノードを最小コストの方法 (最短パス) でペアリングする方法のヒントでした。リスト内のすべてのノードを組み合わせる方法を知っていれば、私が持っているデータを使用するのは簡単です。

解決策は必要ありません。これは宿題ではありません。

整数と言うリストがある場合、すべての整数をペアで組み合わせる方法を知るためのヒントが必要です。

この説明がより良いものであることを願っています... :D

4

2 に答える 2

0

(コストの詳細は省きますが、 を仮定cost(1,5) = 1-5します。合計をできるだけ 0 に近づけたいと考えています。)

NP-Completeである偶数パーティションの問題について説明しています。

問題は次のように述べています: list が与えられた場合、L の各要素が A または B になければならない (両方であってはなりません) で、かつ #elements(A) = #elements(B) であるようなL2 つのリストを見つけます。A,Bsum(A) = sum(B)

あなたの問題への還元は簡単です.ペアの左の各要素はAに行き、各ペアの右の各要素はBに行きます.

したがって、問題に対する既知の多項式解はありませんが、指数関数的網羅的検索アプローチを試してみることをお勧めします (考えられるすべてのペアを検索しますChoose(2n,n) = (2n!)/(n!*n!)。それらのペアがあります)。

代替手段は、疑似多項式 DP ベースのソリューションです (小さな整数で実行可能)。

于 2012-12-13T11:37:37.577 に答える
0

多分：

List<int> totalCosts = listDegree
            .Select((num,index) => new{num,index})
            .GroupBy(x => x.index / 2)
            .Select(g => g.Sum(x => x.num))
            .ToList();

デモ

編集：

質問を編集した後、要件を理解しました。リスト内のすべての要素のすべての（ペアごとの）組み合わせの総和が必要です。非常に効率的で有益なこの組み合わせプロジェクトを使用します。

var listDegree = new[] { 1, 4, 5, 6 };
int lowerIndex = 2;
var combinations = new Facet.Combinatorics.Combinations<int>(
    listDegree,
    lowerIndex,
    Facet.Combinatorics.GenerateOption.WithoutRepetition
);

 // get total costs overall
 int totalCosts = combinations.Sum(c => c.Sum());

 // get a List<List<int>> of all combination (the inner list count is 2=lowerIndex since you want pairs)
 List<List<int>> allLists = combinations.Select(c => c.ToList()).ToList();

 // output the result for demo purposes
 foreach (IList<int> combis in combinations)
 {
     Console.WriteLine(String.Join(" ", combis));
 }
于 2012-12-13T11:40:15.063 に答える