如果条件相似，检查并赋值

Question

我正在实现A*算法，我被下面的伪代码卡住了:

 if neighbor not in openset or tentative_g_score <= g_score[neighbor] 
     came_from[neighbor] := current
     g_score[neighbor] := tentative_g_score
     f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
     if neighbor not in openset
         add neighbor to openset

我想优化openset检查，这样我就不会检查一个节点是否在一个算法通过中被openset两次。

我知道在bash中有这样的东西:

if(( false == openedList_.ContainsNodeXY(n.X, n.Y)) && 
     InOpenSet = false ){ .... }

有了这个，我将有关于节点在或不在开放集中的信息。

如何在c#中做到这一点?

编辑openList_是一个列表(我必须有它排序)，所以它不能是一个HashSet。

Answer 1

你可以使用c#中的HashSet<T>对象。HashSet将能够快速地告诉你一个对象是否是集合的成员。

HashSet有Add和Contains方法。

---

根据你的评论，你可能想要SortedList。它不会更快，HashSet在大多数情况下是O(1)。SortedList在插入时将是O(n)。SortedList也有Contains(因为它们都实现了字典)。

Answer 2

我认为A*需要的是一个也支持快速Contains的优先级队列。SortedSet<T>就是这个班。据我所知，这是一棵红黑树。

警告:不要使用BCL中的SortedList<T>类。这是一种基于可怕的O(n^2)算法的遗留东西。