0

私はPythonでA *パ​​ス検索アルゴリズムに取り組んでおり、このdtypeを使用してデータを2D NumPy配列にうまく詰め込んでいます:

numpy.dtype([
  ('open', bool),
  ('closed', bool),
  ('parent', object),
  ('g', int),
  ('f', int)
])

ウィキペディアの「A* 検索アルゴリズム」エントリの疑似コードに従って、これを解釈する必要があります。

current := the node in openset having the lowest f_score[] value

このビットは、最小の 'f' 値のインデックスを示します (作業配列は pathArray として定義されます)。

numpy.unravel_index(numpy.argmin(pathArray['f']), pathArray['f'].shape)

...そして、このビットは、'open' が True であるすべてのインデックスを見つけます。

numpy.where(pathArray['open'])

これらの条件を一緒に使用して、「open」が True である最小の「f」値を見つけるにはどうすればよいですか?

4

2 に答える 2

1

onを使用する代わりに、np.argminonpathArray['f']を使用することもできますpathArray[pathArray['open']]['f']。もちろん、結果を適応させて、それを使用できるようにする必要がありますpathArray['f']...

別の方法としては、フィールドにpathArray沿ってソートし、最初にTrue であるエントリを見つけます。'f'pathArray_sorted['open']

于 2012-10-04T07:59:19.410 に答える
0

私はあまり詳しくありnumpyませんが、組み込み関数を使用してこれを行うことはできないと「考えています」。しかし、私はまだ説明しようとします。Wikipediaつまり、priority queueこれを行うには、のようなものが必要です。

current := the node in openset having the lowest f_score[] value

これを非常に高速に実行する必要があります。私が提案するのは、バイナリヒープを構築し、それを優先キューとして使用することです。これはPythonで簡単に行うことができます。これは、 Pythonでの実装とその実装heapsを説明する非常に優れた記事です。 幸運をpriority queues

于 2012-10-04T05:04:07.340 に答える