种豆资源网

当前位置:首页 > 百科 > 百科综合 / 正文

摸墙算法

(2019-12-29 00:43:59) 百科综合
摸墙算法

摸墙算法

摸墙算法称绕墙走算法,是一种用运用左手/右手法则进行迷宫搜寻的初级算法。

基本介绍

  • 中文名:摸墙算法
  • 外文名:wall-following algorithm
  • 拼音:Mo Qiang Suan Fa
  • 别称:绕墙走算法
  • 法则:左手/右手法则

概述

(wall-following algorithm)
又称绕墙走算法,是一种用运用左手/右手法则进行迷宫搜寻的初级算法。

简介

如果迷宫是简单连通的,即迷宫的墙总是相互相连的或与迷宫的外轮廓相连,那幺迷宫的搜寻者从起点开始将一只手扶在墙面前行,总能保证不会迷失并且找到迷宫中存在的出口(若忽略出口将回到迷宫起点)。这种策略在刚进入迷宫时即执行的效果是最佳的。
另外可以从拓扑学的角度来看待这种搜寻策略。如果墙是互相连线的,那幺它们可以被转换成一个迴路或者说圆环。那幺摸墙走就可以被看作是从一个圆环的起点行进至其到终点。
当迷宫不是简单连通的,比如迷宫的起始或终止点在迷宫结构的内部并且其外部有迴路包围,那幺这种策略就不能保证出口一定会被找到。
摸墙算法还可以被套用到三维或更高维度的情况下,只要迷宫多出的维度可以用一种确定的方式投影到二维平面。比如在三维迷宫中,“上”这个方向可以被映射为二维平面中的“西北”,而“下”则可以被映射为“东南”。然后摸墙算法就可以被套用到这个被转换后的模型中。然而不像二维平面,这种模型需要得知当前搜寻者的具体朝向,以便确定哪个方向才是第一个左手或右手方向。
左手摸墙算法流程图:
摸墙算法

标 签

搜索
随机推荐

Powered By 种豆资源网||