-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)

--------------- 更多细节（或重写鞋面） ---------------

我有一个类，它读取我的输入文件并存储我需要的所有信息，例如图形的成本矩阵、边、边和节点的数量。

接下来我有一个 DijkstrasShortestPath 算法，它计算我的图表（costMatrix）中从给定起始节点到给定结束节点的最短路径。

我还有一个方法可以检查图形（costMatrix）并将所有奇数度节点存储在一个列表中。

所以我一直在寻找的是一些关于如何以最便宜的方式（最短路径）配对所有奇数度节点的提示。当我知道如何组合列表中的所有节点时，使用我拥有的数据很容易。

我不需要解决方案，这不是家庭作业。

我只需要一个提示即可知道，当您有一个包含整数的列表时，如何将所有整数成对组合。

希望这个解释更好......：D

4

2 回答 2

0

（如果没有关于成本的更多细节，我将假设cost(1,5) = 1-5，并且您希望总和尽可能接近 0。）

您正在描述偶数分区问题，即NP-Complete。

问题是：给定一个列表L，找到两个列表A,B，满足sum(A) = sum(B)#elements(A) = #elements(B)，其中 L 中的每个元素都必须在 A 或 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 回答