0

我正在实现 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

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

我知道在 bash 中有类似的东西：

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

有了这个，我就会有关于节点是否在开放集中的信息。

我怎样才能在 C# 中做到这一点？

EDIT openList_是一个列表（我必须对其进行排序），所以它不能是一个HashSet.

4

2 回答 2

0

您可以HashSet<T>为此使用 C# 中的对象。HashSet 将很快能够告诉您一个对象是否是 Set 的成员。

HashSet有Add和Contains方法。

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

请参阅这个有用的答案。

于 2012-12-30T15:43:19.167 回答
0

我认为 A* 需要的是一个也支持 fast 的优先级队列Contains。SortedSet<T>是这堂课。据我了解，它是一棵红黑树。

警告：不要使用SortedList<T>BCL 中的类。它是基于可怕O(n^2)算法的遗留物。

于 2012-12-30T16:27:29.620 回答