獲取列表的最低值<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; 
    } 

而且我想用最低的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) 
      { 

      } 
     } 

如果我猜我會說這要麼是非常困難或複雜得多，比我」讓它聽起來很不錯，或者非常容易，我只是感到困惑。

我的確在考慮滾動列表並將每個項目與其對應項目進行比較，但考慮到我們所處的年齡，這似乎不合理，似乎會有一種更簡單的方法。我不關心列表的順序，因爲我正在爲每個項目分配一個索引，我可以從中調用它。

在此先感謝！

Answer 1

沒有一種LINQ擴展方法可以返回具有最小值的對象，但您可以自己編寫一個。下面的類，你想要做的任何非空枚舉什麼：

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）。

Answer 2

要獲得Tile具有最低distanceLeft，試試這個：

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

編輯：

這樣做會返回一個IEnumerable<Tile>將在升序進行排序 - openList本身不會改性。

Answer 3

或者，如果由於某種原因，你不能使用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]; 

Answer 4

其他的答案解釋如何使用LINQ做到這一點 - 不過，他們都是O(n)或更慢。使用其中的一種方法將顯着減慢您的尋路算法。

取而代之，你的應該使用正確的數據結構。而不是列表，您應該將您的節點存儲在優先級隊列中，以獲得（併除去）中的最小值O(log n)。

請參閱this question瞭解.Net中的優先級隊列列表。