0

私がやろうとしているのは、NP 完全問題へのヒューリスティックなアプローチを実装することです。オブジェクト (一致) のリストがあり、それぞれに 2 つのスコアがあります。スコアの説明で並べ替えられたリストの最初の要素を取得し、リストから削除します。次に、最初の要素にバインドされたすべての要素が削除されます。要素がなくなるまで、リストを反復処理します。

この問題を効率的に解決できるデータ構造が必要なので、基本的には 次のプロパティを備えている必要があり ます
。

今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

ヒープとセットの 2 つのデータ構造を使用する必要があると思います。並べ替えられたアイテムを保持するためのヒープと、削除されたアイテムを保持するためのセットです。ヒープをアイテムで埋め、一番上のものを削除し、それとそのすべての従属をセットに追加します。2 番目のものを削除します。既にセットにある場合は無視して 3 番目に移動します。そうでない場合は、それとその従属をセットに追加します。

セットにアイテムを追加するたびに、そのアイテムで計画していることは何でも実行してください。

ここでの複雑さは 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 に答える