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

1回のアルゴリズムパスでノードが2回オープンセットされているかどうかをチェックしないように、オープンセットチェックを最適化したいと思います。

私はbashに次のようなものがあることを知っています：

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

これにより、ノードがオープンセットに含まれるかどうかに関する情報が得られます。

C＃でこれを行うにはどうすればよいですか？

EDIT openList_はリストです（ソートする必要があります）ので、にすることはできませんHashSet。

4

2 に答える 2

0

HashSet<T>これには、C＃のオブジェクトを使用できます。HashSetは、オブジェクトがセットのメンバーであるかどうかをすばやく通知できます。

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 に答える