JavaまたはLispまたはC#でのマルチスレッドA *検索
-
08-07-2019 - |
質問
マルチスレッドA *検索を行う良い方法はありますか? (たとえば)人工知能:現代のアプローチで示されているように、シングルスレッドはかなり簡単ですが、良いマルチスレッドバージョンに出くわしていません。
スレッドプールとワークブロック、そしてもちろんガベージコレクションがあるJavaやC#、Lispなどの健全な言語を想定します。
解決
このペーパーを読むことをお勧めします:
"対称マルチプロセッサでの並列双方向A *検索"
別の論文もあります。これもIEEEにあります。
"メッセージパッシングアーキテクチャの並列Astar検索"
どちらの論文も、かなりの高速化を実現する新しい方法を見つけています。
他のヒント
あなたの言っていることは聞きましたが、あなたが望むかどうかはわかりません。 A *検索では、最適なパスを取得し、同じパスに対して2回計算を行いたくありません。
事実を見てください:
- 選択する「最良の」正方形はすべて隣同士です
- 「最良の」選択以外の他の平方の計算は、早すぎる計算です。 A *のポイントは、選択が効率的であることです。
必要なアプリケーションをスレッド化した場合:
- a 「Waiter」は、スレッドが同じ正方形に触れないようにし、彼らに計算するための新しい正方形を与えるために。すべての「最良の」正方形が互いに隣接しているため、彼らは全員、パスリソースのために戦うほど緊密なニットエリアで働いているでしょう。
この問題は手続き的なものであり、個別の部分に分割する良い方法がないため、スレッド化には適していません。要するに、それは望ましいことではないので、誰もそれをやっていません。これがお役に立てば幸いです。
所属していません StackOverflow