基于八方向跟踪算法的迷宫问题新解  

A NEW SOLUTION FOR MAZE PROBLEM BASED ON EIGHT-DIRECTION TRACKING ALGORITHM

作　　者：孙秋冬[1] 

机构地区：[1]上海第二工业大学电子电气工程学院,上海201209

出　　处：《计算机应用与软件》2005年第8期103-105,共3页Computer Applications and Software

摘　　要：本文提出了一个基于八方向跟踪算法的破解迷宫问题的新方法,避免了用深探法或广探法求解迷宫问题的诸多问题,它不仅为计算机的解题提供了一个快捷的算法,而且也为人工或机器人破解提供了一个无需记忆的简便方法。另外,本文还给出了迷宫次佳通路和最佳通路(即捷径)的求解算法;岔道剔除算法和最佳八连通选择算法。本文的所有方法尽管是针对求解单通路迷宫提出来的,但算法对多通路和有环的迷宫也同样有效。Because there are some defects in the classical maze solving methods： DFS （Depth First Search） and BFS （Breadth First Search） , this article produces a new method for solving the maze problem based on eight-direction tracking algorithm, which not only provides a simple quick algorithm for computers but also gives a convenient un-memorial method for human being or robot. In addition,the article also gives the algorithms （Turnoff Eliminating Algorithm and Best Eight Connectivity Selection Algorithm） to solve the maze＇s hypo-best path and best path. Although the all algorithms given here are presented for the single path maze ,they are efficient too for the multi-path maze and the looped path maze.

关 键 词：计算机图形学 八方向跟踪算法 迷宫问题 图论 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] O157.5[自动化与计算机技术—计算机科学与技术]