-1

いくつかのメンバーstructを含む があり、リストから最も低い値を取得しようとしています (実際には、A* 検索ベースのパス ファインダーを作成しています)。intbool

基本的に、私のオブジェクトは次のようになります。

    public struct Tile
    {
        public int id;
        public int x;
        public int y;
        public int cost;
        public bool walkable;
        public int distanceLeft;
        public int parentid;
    }

そして、distanceLeft が最も小さいアイテムを取得したいと考えています。リストは次のように宣言されます。

        List<Structs.Tile> openList = new List<Structs.Tile>();

値は次のように割り当てられます。

        while (pathFound == null)
        {
            foreach (Structs.Tile tile in map)
            {
                foreach (Structs.Tile tile1 in getSurroundingTiles(Current))
                {
                    if (tile1.x == tile.x && tile1.y == tile.y)
                    {
                        Structs.Tile curTile = tile1;
                        curTile.parentid = Current.id;
                        curTile.distanceLeft = (Math.Abs(tile.x - goalx) + Math.Abs(tile.y - goaly));
                        if (curTile.distanceLeft == 0)
                        {
                            pathFound = true;
                        }
                        openList.Add(curTile);
                    }
                }
            }
            foreach (Structs.Tile tile in openList)
            {

            }
        }

推測する必要があるとすれば、これは非常に難しいか、私が思っているよりもはるかに複雑であるか、信じられないほど簡単で混乱していると言えます。

リストをスクロールして、各アイテムを下位のアイテムと比較することを考えましたが、私たちの時代を考えるとそれは不合理に思えます。もっと簡単な方法があるようです. リストの順序は気にしません。各アイテムに、それを呼び出すことができるインデックスを割り当てているからです。

前もって感謝します！

4

4 に答える 4

5

他の回答は、LINQでこれを行う方法を説明していますが、すべてO(n)または遅いです。これらの方法のいずれかを使用すると、パスファインディングアルゴリズムの速度が大幅に低下します。

代わりに、適切なデータ構造を使用する必要があります。リストではなく、ノードを優先キューに格納して、の最小値を取得（および削除）O(log n)する必要があります。

.Netの優先キューのリストについては、この質問を参照してください。

于 2013-02-19T21:40:52.987 に答える
2

最小値でオブジェクトを返すLINQ拡張メソッドは1つではありませんが、自分で作成することはできます。次のクラスは、空でない列挙可能なものに対して必要なことを実行します。

public static class MyExtensions
{
    public static TSource MinOf<TSource>(
        this IEnumerable<TSource> source,
        Func<TSource, int> selector)
    {
        // Get the enumerator.
        var enumerator = source.GetEnumerator();
        if (!enumerator.MoveNext())
            throw new InvalidOperationException("The source sequence is empty.");

        // Take the first value as a minimum.
        int minimum = selector(enumerator.Current);
        TSource current = enumerator.Current;

        // Go through all other values...
        while (enumerator.MoveNext())
        {
            int value = selector(enumerator.Current);
            if (value < minimum)
            {
                // A new minimum was found. Store it.
                minimum = value;
                current = enumerator.Current;
            }
        }

        // Return the minimum value.
        return current;
    }
}

プロジェクト内のファイルに入れて、次のように呼び出します。

openList.MinOf(tile => tile.distanceLeft);

OrderByこれは、シーケンス全体を並べ替えて（を使用して）、最初の値を取得する（を使用して）よりも効率的ですFirst。

于 2013-02-19T21:22:26.360 に答える
1

または、何らかの理由でLINQを使用できない場合：

int lowest = 0;
for (int i = 1; i < openList.Count; ++i)
{
    if (openList[i].distanceLeft < openList[lowest].distanceLeft)
    {
        lowest = i;
    }
}
// lowest contains the index of the item with the lowest 'distanceLeft' value.
// You can return the item itself by indexing into the list.
var lowestItem = openList[lowest];
于 2013-02-19T21:40:14.883 に答える
1

Tile最も低い値を取得するには、次のことdistanceLeftを試してください。

Tile tile = openList.OrderByAscending(t => t.distanceLeft).First();

編集：

IEnumerable<Tile>これを行うと、昇順でソートされるが返されます-openListそれ自体は変更されません。

于 2013-02-19T21:33:17.230 に答える