基于回溯法的罗密欧与朱丽叶的迷宫问题的Matlab实现
发布时间：2021-07-19 12:26
以算法设计和Matlab编程为主题,对经典算法问题"罗密欧与朱丽叶的迷宫问题"提出了一种基于回溯法的有效解决策略,并使用Matlab编程语言实现了结果的可视化输出。
【文章来源】：电脑编程技巧与维护. 2019,(09)
【文章页数】：7 页
【部分图文】：
罗密欧与朱丽叶的迷宫问题的程序调用关系图
2019.09elseifA(j,k)==row*column-numberOfClose-dRoomstext(k-0.35,j,num2str(A(j,k))+"：朱丽叶",'FontSize',10);elseifA(j,k)==-1text(k-0.35,j,num2str(A(j,k))+"：封闭房间",'FontSize',10);elsetext(k,j,num2str(A(j,k)),'FontSize',18);endendendendend3.6程序调用关系根据程序模块的设计方案，各程序之间的调用关系如图3所示。4程序测试4.1测试数据输入以下测试数据：迷宫的行数和列数为3和4，迷宫中封闭房间的数量为2，封闭房间的位置为（1,2）和（3,4），罗密欧的初始位置为（1,1），朱丽叶的位置为（2,2）。输入的数据如图4所示，命令行输出的结果如图5所示，可视化输出的图片如图6所示。4.2测试结果分析根据测试数据的结果可知，当迷宫的行数和列数为3和4，迷宫中封闭房间的数量为2，封闭房间的位置为（1,2）和（3,4），罗密欧的初始位置为（1,1），朱丽叶的位置为（2,2）时，罗密欧通往朱丽叶房间的最少转弯次数为6，不同的最少转弯次数的路线数量为7，以二维矩阵的形式进行表示。所有的转弯次数最少的路线如下所示。（1）（2）图3罗密欧与朱丽叶的迷宫问题的程序调用关系图图4测试数据图5测试数据命令行窗口结果输出图6测试数据结果可视化输出main函数initialize函数searchPath函数PrintResult函数checkStep函数savePath函数resultVisualization函数(下转第167页)146
2019.091问题描述算法问题“罗密欧与朱丽叶的迷宫问题”的问题描述如下所示：罗密欧与朱丽叶身处一个m*n的迷宫中，如图1所示。每一个方格表示迷宫中的一个房间，迷宫中有一些房间是封闭的，不允许任何人进入，如黄色方格所示。在迷宫中任何位置均可沿8个方向（上、下、左、右、左上、左下、右上、右下）进入未封闭的房间。罗密欧位于迷宫的某一个房间中，他需要找出一条通向朱丽叶所在房间的路线，该路线必须满足以下条件：（1）在抵达朱丽叶的房间之前，罗密欧必须走遍所有未封闭的房间各一次。（2）该路线的转弯次数为最少，每改变一次前进方向算作一次转弯。试设计一个算法帮助罗密欧找出所有符合上述要求的通往朱丽叶房间的路线。2问题分析2.1解题目标根据问题描述可知，罗密欧与朱丽叶的迷宫问题的解题目标是：给定一个m*n的迷宫（假设以迷宫左上角为坐标原点建立直角坐标系）、迷宫中封闭房间的数量为k、封闭房间的位置为（pi,qj）（i,j=1,2,3,...)、罗密欧房间的起始位置（a,b）、朱丽叶房间的位置（c,d）、求满足走遍所有未封闭房间各一次且转弯次数最少的罗密欧通往朱丽叶房间的路线。假设迷宫中未封闭房间的数量为w，罗密欧通往朱丽叶的路线的每一步为Si（Si∈（0,1),i=1,2,3,...）（Si为0表示当前房间为封闭房间，为1表示当前房间未封闭），该路线的转弯次数为t，罗密欧最后一步到达的房间的位置为（x,y），朱丽叶房间的位置为（c,d），则罗密欧与朱丽叶的迷宫问题等价于满足以下条件的问题
【参考文献】：
期刊论文
[1]回溯法与分枝限界法的分析与比较[J]. 杨超,何书前,郑志群,石春. 电脑知识与技术. 2018(11)
[2]回溯法在计算机程序设计中的应用[J]. 裴南平,毕传林. 电脑知识与技术. 2017(31)
[3]回溯算法的形式模型[J]. 王岩冰,郑明春,刘弘. 计算机研究与发展. 2001(09)
本文编号：3290700
【文章来源】：电脑编程技巧与维护. 2019,(09)
【文章页数】：7 页
【部分图文】：
罗密欧与朱丽叶的迷宫问题的程序调用关系图
2019.09elseifA(j,k)==row*column-numberOfClose-dRoomstext(k-0.35,j,num2str(A(j,k))+"：朱丽叶",'FontSize',10);elseifA(j,k)==-1text(k-0.35,j,num2str(A(j,k))+"：封闭房间",'FontSize',10);elsetext(k,j,num2str(A(j,k)),'FontSize',18);endendendendend3.6程序调用关系根据程序模块的设计方案，各程序之间的调用关系如图3所示。4程序测试4.1测试数据输入以下测试数据：迷宫的行数和列数为3和4，迷宫中封闭房间的数量为2，封闭房间的位置为（1,2）和（3,4），罗密欧的初始位置为（1,1），朱丽叶的位置为（2,2）。输入的数据如图4所示，命令行输出的结果如图5所示，可视化输出的图片如图6所示。4.2测试结果分析根据测试数据的结果可知，当迷宫的行数和列数为3和4，迷宫中封闭房间的数量为2，封闭房间的位置为（1,2）和（3,4），罗密欧的初始位置为（1,1），朱丽叶的位置为（2,2）时，罗密欧通往朱丽叶房间的最少转弯次数为6，不同的最少转弯次数的路线数量为7，以二维矩阵的形式进行表示。所有的转弯次数最少的路线如下所示。（1）（2）图3罗密欧与朱丽叶的迷宫问题的程序调用关系图图4测试数据图5测试数据命令行窗口结果输出图6测试数据结果可视化输出main函数initialize函数searchPath函数PrintResult函数checkStep函数savePath函数resultVisualization函数(下转第167页)146
2019.091问题描述算法问题“罗密欧与朱丽叶的迷宫问题”的问题描述如下所示：罗密欧与朱丽叶身处一个m*n的迷宫中，如图1所示。每一个方格表示迷宫中的一个房间，迷宫中有一些房间是封闭的，不允许任何人进入，如黄色方格所示。在迷宫中任何位置均可沿8个方向（上、下、左、右、左上、左下、右上、右下）进入未封闭的房间。罗密欧位于迷宫的某一个房间中，他需要找出一条通向朱丽叶所在房间的路线，该路线必须满足以下条件：（1）在抵达朱丽叶的房间之前，罗密欧必须走遍所有未封闭的房间各一次。（2）该路线的转弯次数为最少，每改变一次前进方向算作一次转弯。试设计一个算法帮助罗密欧找出所有符合上述要求的通往朱丽叶房间的路线。2问题分析2.1解题目标根据问题描述可知，罗密欧与朱丽叶的迷宫问题的解题目标是：给定一个m*n的迷宫（假设以迷宫左上角为坐标原点建立直角坐标系）、迷宫中封闭房间的数量为k、封闭房间的位置为（pi,qj）（i,j=1,2,3,...)、罗密欧房间的起始位置（a,b）、朱丽叶房间的位置（c,d）、求满足走遍所有未封闭房间各一次且转弯次数最少的罗密欧通往朱丽叶房间的路线。假设迷宫中未封闭房间的数量为w，罗密欧通往朱丽叶的路线的每一步为Si（Si∈（0,1),i=1,2,3,...）（Si为0表示当前房间为封闭房间，为1表示当前房间未封闭），该路线的转弯次数为t，罗密欧最后一步到达的房间的位置为（x,y），朱丽叶房间的位置为（c,d），则罗密欧与朱丽叶的迷宫问题等价于满足以下条件的问题
【参考文献】：
期刊论文
[1]回溯法与分枝限界法的分析与比较[J]. 杨超,何书前,郑志群,石春. 电脑知识与技术. 2018(11)
[2]回溯法在计算机程序设计中的应用[J]. 裴南平,毕传林. 电脑知识与技术. 2017(31)
[3]回溯算法的形式模型[J]. 王岩冰,郑明春,刘弘. 计算机研究与发展. 2001(09)
本文编号：3290700
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3290700.html
