这个问题更多的是关于算法而不是实际代码，但示例代码将不胜感激。
假设我有一个二维数组，如下所示：
A B C D E
--------------
1 | 0 2 3 4 5
2 | 1 2 4 5 6
3 | 1 3 4 5 6
4 | 2 3 4 5 6
5 | 1 2 3 4 5
我正在尝试找到包含每行值的最短列表。目前，我逐行逐列，将每个值添加到SortedSet，然后根据迄今为止找到的最短集合检查集合的长度。例如：
添加单元格{1A, 2A, 3A, 4A, 5A}将添加值{0, 1, 1, 2, 1}这将导致排序集{0, 1, 2}。{1B, 2A, 3A, 4A, 5A}将{2, 1, 1, 2, 1}值相加，这将得到一个排序集{1, 2}，它比前一个集合短。
显然，添加{1D, 2C, 3C, 4C, 5D}或{1E, 2D, 3D, 4D, 5E}将是最短的集合，每个集合只有一个项目，我可以使用任何一个。
我不必在数组中包含每个数字。我只需要找到最短的集合，同时从每行中至少包含一个数字。
请记住，这只是一个示例数组，我使用的数组要大得多。最小的是 495x28。蛮力将需要很长时间(28^495 次传递)。有没有人知道的捷径，可以在最少的传递次数中找到它？我有 C# 代码，但它有点长。
编辑：
根据请求发布当前代码：
// Set an array of counters, Add enough to create largest initial array
int ListsCount = MatrixResults.Count();
int[] Counters = new int[ListsCount];
SortedSet<long> CurrentSet = new SortedSet<long>();
for (long X = 0; X < ListsCount; X++)
{
Counters[X] = 0;
CurrentSet.Add(X);
}
while (true)
{
// Compile sequence list from MatrixResults[]
SortedSet<long> ThisSet = new SortedSet<long>();
for (int X = 0; X < Count4; X ++)
{
ThisSet.Add(MatrixResults[X][Counters[X]]);
}
// if Sequence Length less than current low, set ThisSet as Current
if (ThisSet.Count() < CurrentSet.Count())
{
CurrentSet.Clear();
long[] TSI = ThisSet.ToArray();
for (int Y = 0; Y < ThisSet.Count(); Y ++)
{
CurrentSet.Add(TSI[Y]);
}
}
// Increment Counters
int Index = 0;
bool EndReached = false;
while (true)
{
Counters[Index]++;
if (Counters[Index] < MatrixResults[Index].Count()) break;
Counters[Index] = 0;
Index++;
if (Index >= ListsCount)
{
EndReached = true;
break;
}
Counters[Index]++;
}
// If all counters are fully incremented, then break
if (EndReached) break;
}
在所有计算中，总有一个权衡，有几个因素在起作用，比如你会因为让它完美而获得报酬(在这种情况下对我来说，没有)。这是最好的人是善良的敌人的情况。我们可以花多长时间来解决问题，是否足以足够接近用例(imo)，以及何时我们可以在不以UHD分辨率手绘像素的情况下解决问题以获得密钥的想法，让我们！
所以，我的选择是一种方法，它将得到一个小的覆盖集，嗯......有时将是最小的:)从本质上讲，由于比较的顺序在不同策略之间是迭代的，比较不同策略的集合长度 - 为了这个晚上的乐趣，我选择给出一个策略，即我发现可防御的接近或等于最小集合。
因此，此策略是将多维数组视为具有不同值集的列表序列。然后，如果迭代地减少余数中最小的列表的总数，在每次迭代中减少总集时清除该最小列表中任何未使用的值，我们将得到一条足够接近理想的路径，因为它在毫秒内完成这种方法。
对这种方法的批评是，你传递最小列表的方向实际上必须迭代变化才能选择最佳，从左到右，从右到左，在位置序列 X，Y，Z，...因为电位减少量不相等。因此，为了接近序列的理想迭代，也必须为每次迭代进行，直到覆盖所有组合，选择最简化的序列。右 - 但我只选择了从左到右！
现在我选择不对你的代码运行比较执行，因为你实例化 MatrixResults 的方式是一个 int 数组数组，而不是实例化为多维数组，你的绘图就是这样，所以我去了你的绘图，然后无法与您的代码共享数据源。无论如何，如果您愿意，您可以进行该转换，以生成示例数据：
private int[,] CreateSampleArray(int xDimension, int yDimensions, Random rnd)
{
Debug.WriteLine($"Created sample array of dimensions ({xDimension}, {yDimensions})");
var array = new int[xDimension, yDimensions];
for (int x = 0; x < array.GetLength(0); x++)
{
for(int y = 0; y < array.GetLength(1); y++)
{
array[x, y] = rnd.Next(0, 4000);
}
}
return array;
}
带有一些日志记录的整体结构，我正在使用 xUnit 运行代码
[Fact]
public void SetCoverExperimentTest()
{
var rnd = new Random((int)DateTime.Now.Ticks);
var sw = Stopwatch.StartNew();
int[,] matrixResults = CreateSampleArray(rnd.Next(100, 500), rnd.Next(100, 500), rnd);
//So first requirement is that you must have one element per row, so lets get our unique rows
var listOfAll = new List<List<int>>();
List<int> listOfRow;
for (int y = 0; y < matrixResults.GetLength(1); y++)
{
listOfRow = new List<int>();
for (int x = 0; x < matrixResults.GetLength(0); x++)
{
listOfRow.Add(matrixResults[x, y]);
}
listOfAll.Add(listOfRow.Distinct().ToList());
}
var setFound = new HashSet<int>();
List<List<int>> allUniquelyRequired = GetDistinctSmallestList(listOfAll, setFound);
// This set now has all rows that are either distinctly different
// Or have a reordering of distinct values of that length value lists
// our HashSet has the unique value range
//Meaning any combination of sets with those values,
//grabbing any one for each set, prefering already chosen ones should give a covering total set
var leastSet = new LeastSetData
{
LeastSet = setFound,
MatrixResults = matrixResults,
};
List<Coordinate>? minSet = leastSet.GenerateResultsSet();
sw.Stop();
Debug.WriteLine($"Completed in {sw.Elapsed.TotalMilliseconds:0.00} ms");
Assert.NotNull(minSet);
//There is one for each row
Assert.False(minSet.Select(s => s.y).Distinct().Count() < minSet.Count());
//We took less than 25 milliseconds
var timespan = new TimeSpan(0, 0, 0, 0, 25);
Assert.True(sw.Elapsed < timespan);
//Outputting to debugger for the fun of it
var sb = new StringBuilder();
foreach (var coordinate in minSet)
{
sb.Append($"({coordinate.x}, {coordinate.y}) {matrixResults[coordinate.x, coordinate.y]},");
}
var debugLine = sb.ToString();
debugLine = debugLine.Substring(0, debugLine.Length - 1);
Debug.WriteLine("Resulting set: " + debugLine);
}
现在更丰富的迭代位
private List<List<int>> GetDistinctSmallestList(List<List<int>> listOfAll, HashSet<int> setFound)
{
// Our smallest set must be a subset the distinct sum of all our smallest lists for value range,
// plus unknown
var listOfShortest = new List<List<int>>();
int shortest = int.MaxValue;
foreach (var list in listOfAll)
{
if (list.Count < shortest)
{
listOfShortest.Clear();
shortest = list.Count;
listOfShortest.Add(list);
}
else if (list.Count == shortest)
{
if (listOfShortest.Contains(list))
continue;
listOfShortest.Add(list);
}
}
var setFoundAddition = new HashSet<int>(setFound);
foreach (var list in listOfShortest)
{
foreach (var item in list)
{
if (setFound.Contains(item))
continue;
if (setFoundAddition.Contains(item))
continue;
setFoundAddition.Add(item);
}
}
//Now we can remove all rows with those found, we'll add the smallest later
var listOfAllRemainder = new List<List<int>>();
bool foundInList;
List<int> consumedWhenReducing = new List<int>();
foreach (var list in listOfAll)
{
foundInList = false;
foreach (int item in list)
{
if (setFound.Contains(item))
{
//Covered by data from last iteration(s)
foundInList = true;
break;
}
else if (setFoundAddition.Contains(item))
{
consumedWhenReducing.Add(item);
foundInList = true;
break;
}
}
if (!foundInList)
{
listOfAllRemainder.Add(list); //adding what lists did not have elements found
}
}
//Remove any from these smallestset lists that did not get consumed in the favour used pass before
if (consumedWhenReducing.Count == 0)
{
throw new Exception($"Shouldn't be possible to remove the row itself without using one of its values, please investigate");
}
var removeArray = setFoundAddition.Where(a => !consumedWhenReducing.Contains(a)).ToArray();
setFoundAddition.RemoveWhere(x => removeArray.Contains(x));
foreach (var value in setFoundAddition)
{
setFound.Add(value);
}
if (listOfAllRemainder.Count != 0)
{
//Do the whole thing again until there in no list left
listOfShortest.AddRange(GetDistinctSmallestList(listOfAllRemainder, setFound));
}
return listOfShortest; //Here we will ultimately have the sum of shortest lists per iteration
}
总结：我希望能启发你，至少我玩得很开心，想出一个最好的近似值，如果你想完成代码，非常欢迎你抓住你喜欢的东西。
显然，我们真的应该跟踪我们经历最短列表的顺序，毕竟如果我们从在位置 0 或 0+N 按元素减少总不同列表以及之后减少哪个列表开始，这很重要。我的意思是我们必须有一个这些值，但每次消耗每个值都删除了总列表的大部分，它真正产生的只是一个值范围，范围消耗序列对以后的迭代很重要 - 因为我们之前没有达到的位置没有其他人留下，例如可以删除可能超过一些被覆盖的位置。我敢肯定，你明白了。
这只是一种策略，即使在同一个框架内，人们也可以选择最大的不同列表，如果您没有迭代涵盖足够的策略，则只剩下蛮力。
无论如何，你都希望人工智能采取行动。就像人类一样，以前不考虑宇宙的存在，毕竟只要我们能这么快，我们就可以经常用硅大脑重新考虑。
至少对于任何移动物体，我宁愿每秒 90% 的目标校正，同时需要 14 毫秒才能到达那里，而不是花费 2 秒达到 99% 或虚幻的 100% =>这意味着我们应该在混凝土柱子或婴儿车之前停止车辆，或者相反地在时机购买股权， 没有弄清楚我们应该停下来，当我们在障碍物的另一边准备好时，或者我们应该在 5 秒前买入，但那时现货价格已经再次上涨......
因此，辩护基于这样一种观念，即如果这个解决方案足够好或充其量是不完整的，那么它就是固执己见:D
我意识到这是非常随机的，但只是说虽然这个草图不是完全无可争议的正确，但它很容易阅读和维护，无论如何这个问题是错误的 B-]我们很少需要绝对最小集合，当我们这样做时，答案会更长:D
。呜，忘记了支持类
public struct Coordinate
{
public int x;
public int y;
public override string ToString()
{
return $"({x},{y})";
}
}
public struct CoordinateValue
{
public int Value { get; set; }
public Coordinate Coordinate { get; set; }
public override string ToString()
{
return string.Concat(Coordinate.ToString(), " ", Value.ToString());
}
}
public class LeastSetData
{
public HashSet<int> LeastSet { get; set; }
public int[,] MatrixResults { get; set; }
public List<Coordinate> GenerateResultsSet()
{
HashSet<int> chosenValueRange = new HashSet<int>();
var chosenSet = new List<Coordinate>();
for (int y = 0; y < MatrixResults.GetLength(1); y++)
{
var candidates = new List<CoordinateValue>();
for (int x = 0; x < MatrixResults.GetLength(0); x++)
{
if (LeastSet.Contains(MatrixResults[x, y]))
{
candidates.Add(new CoordinateValue
{
Value = MatrixResults[x, y],
Coordinate = new Coordinate { x = x, y = y }
}
);
continue;
}
}
if (candidates.Count == 0)
throw new Exception($"OMG Something's wrong! (this row did not have any of derived range [y: {y}])");
var done = false;
foreach (var c in candidates)
{
if (chosenValueRange.Contains(c.Value))
{
chosenSet.Add(c.Coordinate);
done = true;
break;
}
}
if (!done)
{
var firstCandidate = candidates.First();
chosenSet.Add(firstCandidate.Coordinate);
chosenValueRange.Add(firstCandidate.Value);
}
}
return chosenSet;
}
}
这个问题很难。
为了证明这一点，我们必须采用一个已知的NP难题，并将其简化为这个问题。 让我们用设置封面问题来做到这一点。
我们从一个U事物的宇宙开始，以及一个覆盖宇宙的集合S集合。 为每件事分配一行，每件事设置一个数字。 这将填充每行的不同列数。 通过添加新数字来填充矩形。
现在解决您的问题。
对于解决方案中不是来自原始问题中的集合的每个新数字，我们可以将其替换为同一行中来自集合的另一个数字。
现在我们将数字重新转换为集合，我们有了解决集合覆盖问题的方法。
从设置覆盖到问题并再次返回的转换都是O(number_of_elements * number_of_sets)输入中的多项式。因此，您的问题很难解决。
相反，如果将矩阵中的每个数字替换为所涵盖的行集，则问题将变为集合覆盖问题。 使用任何现有的求解器作为集合覆盖也可以为您的问题提供合理的方法。
代码不是特别整洁或优化，但说明了我认为@btilly在他的答案(E&OE)中建议的方法，使用一些递归(我追求的是直观而不是理想的扩展，所以你可能不得不使用迭代等效物)。
从具有其值的行中，生成"具有它们出现的行的值"对应项。现在选择一个值，消除它出现的所有行，然后再次求解减少的行集。 递归重复，只保留最短的解决方案。
我知道这不是非常可读(或解释得很好)，并且可能会在早上回来整理，所以让我知道它是否符合您的要求(值得我花更多的时间;-)。
// Setup
var rowValues = new Dictionary<int, HashSet<int>>
{
[0] = new() { 0, 2, 3, 4, 5 },
[1] = new() { 1, 2, 4, 5, 6 },
[2] = new() { 1, 3, 4, 5, 6 },
[3] = new() { 2, 3, 4, 5, 6 },
[4] = new() { 1, 2, 3, 4, 5 }
};
Dictionary<int, HashSet<int>> ValueRows(Dictionary<int, HashSet<int>> rv)
{
var vr = new Dictionary<int, HashSet<int>>();
foreach (var row in rv.Keys)
{
foreach (var value in rv[row])
{
if (vr.ContainsKey(value))
{
if (!vr[value].Contains(row))
vr[value].Add(row);
}
else
{
vr.Add(value, new HashSet<int> { row });
}
}
}
return vr;
}
List<int> FindSolution(Dictionary<int, HashSet<int>> rAndV)
{
if (rAndV.Count == 0) return new List<int>();
var bestSolutionSoFar = new List<int>();
var vAndR = ValueRows(rAndV);
foreach (var v in vAndR.Keys)
{
var copyRemove = new Dictionary<int, HashSet<int>>(rAndV);
foreach (var r in vAndR[v])
copyRemove.Remove(r);
var solution = new List<int>{ v };
solution.AddRange(FindSolution(copyRemove));
if (bestSolutionSoFar.Count == 0 || solution.Count > 0 && solution.Count < bestSolutionSoFar.Count)
bestSolutionSoFar = solution;
}
return bestSolutionSoFar;
}
var solution = FindSolution(rowValues);
Console.WriteLine($"Optimal solution has values {{ {string.Join(',', solution)} }}");
输出Optimal solution has values { 4 }