迷宮-右手法則改善
ラビリンス-右手の法則の改善(スタック)
前に定めた右手の法則で迷路を探すのは避けられないアルゴリズムだ.
stackを使用すると最短経路は得られないが,袋小路からの戻りを防ぐ経路を見つけることができる.
stack<Pos> s;
for(int i=0;i<_path.size()-1;i++)
{
if (s.empty() == false && s.top() == _path[i + 1])
s.pop();
else
s.push(_path[i]);
}
// 목적지 도착
if (_path.empty() == false)
s.push(_path.back());
vector<Pos> path;
while (s.empty() == false)
{
path.push_back(s.top());
s.pop();
}
std::reverse(path.begin(), path.end());
_path = path;
現在位置をiと呼ぶとスタックに格納されている(i-1)ルートと(i+1)ルートを比較し、それらが等しい場合は戻る道であるため、最終ルートから削除する.
異なる場合は、スタックに現在位置のiルートが格納されます.
すべてのルーティングが終了すると、スタック内のルーティングが最終ルーティングに格納されます.stackは、一番後ろの要素から取り出し、一時変数に保存し、最終ルートディレクトリに逆方向に保存します.
この方法を用いると,既存の右手定則により求めた根から戻った根を除去することができる.
しかし、これは最短経路を求めるアルゴリズムではなく、絶路に直面して戻る道を減らしただけだ.
結果
既存の右手の法則を通じて道を見つけるよりもずっと速いことがわかります.
Reference
この問題について(迷宮-右手法則改善), 我々は、より多くの情報をここで見つけました https://velog.io/@sansam41/미로-오른손법칙-개선テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol