mengxz的个人博客分享 http://blog.sciencenet.cn/u/mengxz

博文

迷宫的数学建模

已有 32278 次阅读 2012-5-6 08:30 |系统分类:论文交流| 数学建模, 迷宫

迷宫的数学建模

山东省聊城第一中学高二14班 孟庆伦(高中学生,本博主之子)  指导教师 王树清

摘要:提出了迷宫问题的数学建模方法,得到了走迷宫的三步走法。这种方法可以走通任意迷宫。

关键词:迷宫;端点;无效边

迷宫是一种充满复杂通道的建筑物,由于很难找到从入口到出口的通道,因而成为很多人喜欢的有趣和益智游戏。下面以图1所示的简单迷宫为例建立数学模型,分析走迷宫的数学方法。

 

一、迷宫问题的数学建模

1、数学建模

在迷宫问题中,人们关心的是找出从入口到出口的通道,并不关心通道两侧的建筑物墙壁,这样迷宫问题的实质上就转化为选择从入口到出口通道的问题。通道在数学上可以用线段来描述,因此,从入口到出口的通道在数学上可以用从入口到出口的折线段描述。图2给出了上图中简单迷宫的数学模型。在数学模型中,找出从入口到出口的折线段就成了解决迷宫问题的关键

2、数学分析

第一步 查找端点,去除无效边

图中ABCDEFGHIJK等结点都只有一条边相连,是边的端点。与端点直接相连的边LALB无效通道,进入无效通道后只能沿原路返回。为了叙述方便,我们把与端点直接相连的边(如图2中LALB)称为无效边。可见,要成功走出迷宫首先要避免进入无效边,所以走迷宫第一步是查找端点,去除无效边,图3为去除无效边后的一次简化模型。

第二步 查找各级新生端点,去除各级新生无效边

2LMNOPQRSTUVW等结点有三条以上的边相连,其中有这样一些结点——有n条边相连,但其中有(n-1)条边是无效边。例如,结点L有三条边,但其中有两条边LALB是无效边,去除LALB两条无效边后,结点L就变成了新生的端点,为了叙述方便,我们把这种新生的端点简称为新生端点。与结点L连结的第三条边OL也就变成了新生的无效边,为了叙述方便,我们把OL这种新生的无效边简称为新生无效边。进入这种新生无效边后也只能沿原路返回。图2中新生端点除了L外,还有结点S

2中还有这样一些结点——有n条边相连,但无效边和新生无效边的总条数为(n-1)。例如,结点O有四条边,其中有两条边OCOD是无效边,另一条OL是新生无效边。去除OCODOL三条无效边后,结点O也变成了新生的端点,为了叙述方便,我们把这种新生的端点也简称为新生端点。与结点O连结的第四条边QO也是新生的无效边,为了叙述方便,我们把QO这种边也称为新生无效边。进入这种新生无效边后也只能沿原路返回。

可见,要成功走出迷宫不仅要避免进入无效边,也要避免进入各级新生无效边,所以成功走迷宫的第二步就是查找各级新生端点,去除上述各级新生无效边,图3为去除无效边和各级新生无效边后的最终简化模型。

第三步 剩余的边就是成功走迷宫的通道

逐步去除无效边和各级新生无效边后,最后就会只剩从入口到出口的有效通道,如图3所示。沿着剩余有效通道就可以成功走通迷宫。按这种迷宫的三步走法,任意复杂迷宫都可以快速走通。



https://wap.sciencenet.cn/blog-671857-567654.html

上一篇:让购买书籍和购买物质食粮一样平常——谈书籍价格与知识传播
下一篇:黄帝纪元与公元纪元
收藏 IP: 222.133.217.*| 热度|

7 刘建兴 刘鹰翔 唐常杰 张国庆 王一华 杨月琴 wormbreeder

该博文允许注册用户评论 请点击登录 评论 (15 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 03:33

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部