JavaまたはLispまたはC＃でのマルチスレッドA *検索

Question

マルチスレッドA *検索を行う良い方法はありますか？ （たとえば）人工知能：現代のアプローチで示されているように、シングルスレッドはかなり簡単ですが、良いマルチスレッドバージョンに出くわしていません。

スレッドプールとワークブロック、そしてもちろんガベージコレクションがあるJavaやC＃、Lispなどの健全な言語を想定します。

Answer 1

このペーパーを読むことをお勧めします：

＆quot;対称マルチプロセッサでの並列双方向A *検索＆quot;

別の論文もあります。これもIEEEにあります。

＆quot;メッセージパッシングアーキテクチャの並列Astar検索＆quot;

どちらの論文も、かなりの高速化を実現する新しい方法を見つけています。

Answer 2

あなたの言っていることは聞きましたが、あなたが望むかどうかはわかりません。 A *検索では、最適なパスを取得し、同じパスに対して2回計算を行いたくありません。

事実を見てください：

• 選択する「最良の」正方形はすべて隣同士です
• 「最良の」選択以外の他の平方の計算は、早すぎる計算です。 A *のポイントは、選択が効率的であることです。

必要なアプリケーションをスレッド化した場合：

• a 「Waiter」は、スレッドが同じ正方形に触れないようにし、彼らに計算するための新しい正方形を与えるために。すべての「最良の」正方形が互いに隣接しているため、彼らは全員、パスリソースのために戦うほど緊密なニットエリアで働いているでしょう。

この問題は手続き的なものであり、個別の部分に分割する良い方法がないため、スレッド化には適していません。要するに、それは望ましいことではないので、誰もそれをやっていません。これがお役に立てば幸いです。