0

我要做的是对 NP 完全问题实施启发式方法：我有一个对象列表（匹配项），每个对象都有一个双倍分数。我正在获取按分数 desc 排序的列表中的第一个元素，然后将其从列表中删除。然后将删除绑定到第一个元素的所有元素。我遍历列表，直到没有更多元素。

我需要一个可以有效解决这个问题的数据结构，所以基本上它应该具有以下属性：
1. 通用
2. 总是排序
3. 具有快速键访问

现在SortedSet<T>看起来是最合适的。

问题是：就我而言，它是最佳选择吗？

List result = new List();
while (sortedItems.Any())
{
var first = sortedItems.First();
result.Add(first);
sortedItems.Remove(first);
foreach (var dependentFirst in first.DependentElements)
{
sortedItems.Remove(dependentFirst);
}
}

我需要的是排序哈希表之类的东西。

4

3 回答 3

2

我假设您不仅想清除列表，而且还想在删除每个项目时对其进行处理。

var toDelete = new HashSet<T>();
foreach (var item in sortedItems)
{
    if (!toDelete.Contains(item))
    {
        toDelete.Add(item);
        // do something with item here
    }
    foreach (var dependentFirst in item.DependentElements)
    {
        if (!toDelete.Contains(item))
        {
            toDelete.Add(dependentFirst);
            // do something with item here
        }
    }
}
sortedItems.RemoveAll(i => toDelete.Contains(i));
于 2012-05-04T11:36:24.067 回答
1

我认为您应该使用两种数据结构 - 一个堆和一个集合 - 堆用于保存已排序的项目，设置用于保存已删除的项目。用项目填充堆，然后删除顶部的项目，并将其及其所有依赖项添加到集合中。删除第二个 - 如果它已经在集合中，则忽略它并移至第三个，否则将其及其依赖项添加到集合中。

每次您将一个项目添加到集合中时，也要执行您计划对这些项目执行的任何操作。

这里的复杂性是 O(NlogN)，你不会得到比这更好的，因为无论如何你都必须对项目列表进行排序。如果您想获得更好的性能，您可以为每个项目添加一个“已删除”布尔值，并将其设置为 true，而不是使用集合来跟踪已删除的项目。我不知道这是否适用于你。

于 2012-05-04T11:21:45.793 回答
0

如果我没记错的话，你想要这样的东西

            var dictionary = new Dictionary<string, int>();
            dictionary.Add("car", 2);
            dictionary.Add("apple", 1);
            dictionary.Add("zebra", 0);
            dictionary.Add("mouse", 5);
            dictionary.Add("year", 3);
            dictionary = dictionary.OrderBy(o => o.Key).ToDictionary(o => o.Key, o => o.Value);
于 2012-05-04T10:17:39.533 回答