获取List <Struct.int>的最小值

Question

我有一个struct包含一些int和bool成员的,我希望从列表中获得最低值(实际上是基于A*搜索的路径查找器).

基本上,我的对象看起来像这样:

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

我想得到距离最低的物品.列表声明如下:

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

            }
        }

如果我不得不猜测我会说这要么是非常困难,要么比我听起来要复杂得多,或者非常简单,我只是感到困惑.

我确实考虑过滚动列表并将每个项目与其较低的对应项进行比较,但考虑到我们所处的年龄,这似乎是不合理的,它似乎只是一种更简单的方式.我不关心列表的顺序,因为我正在为每个项目分配一个索引,我可以从中调用它.

提前致谢!

Answer 1

其他答案解释了如何使用LINQ执行此操作 - 但是,它们全部O(n)或更慢.使用这些方法之一将显着减慢您的寻路算法.

相反,您应该使用适当的数据结构.您应该将节点存储在优先级队列中以获取(并删除)最小值,而不是列表O(log n).

有关.Net中优先级队列的列表,请参阅此问题.