座標系の2点間の最短経路

Question

2点AとBがあります。AからBまでの最短経路を探したいが、N（最大200）の矩形があり、それらの矩形。パスと長方形は、矩形の頂点と矩形の辺でのみ交差することができます。最短経路の長さはどのくらいですか？四角形は交差できません。彼らはポイントまたは側を共有することができます。だから二人が二人であれば、それらの間を渡すことができます。

Answer 1

通常、この種の問題の最良のアルゴリズムは、Manhattan Distanceのような単純なヒューリスティックを使用してA*です。しかしまず、あなたは違法な点を見つけなければなりません。違法な点は、この問題では入力できない点です。矩形内にある点は違法です（矩形の辺にある点は、通過できるので合法です）。これらの点を見つけたら、A *アルゴリズムを実装して、AとBの間の最短経路を見つけてください。

この問題ではエッジ重みがないため、BFSを実行して最短パスを見つけることはできますが、A *ほど速くはないことに注意してください。

検索スペースが非常に大きく、A *を使用してメモリが不足している場合は、メモリを消費する代わりにノードを複数回探索するIDA*の使用を検討する必要があります。