注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

亿能部落格---观察思维比思维本身更重要

我是回来地球补课的!

 
 
 

日志

 
 
关于我

光行者的存在不在于他们真的能唤醒人类或者改变人类,而在于人类世界走向几近崩溃的时候能够站出来建立一套持久永恒的生活模式。

网易考拉推荐

迷宫的数学建模  

2016-05-12 00:11:09|  分类: 数学眼光 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

迷宫的数学建模

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

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

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


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

迷宫的数学建模 - 亿能 - 亿能部落格---观察思维比思维本身更重要

 

一、迷宫问题的数学建模

1、数学建模

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

迷宫的数学建模 - 亿能 - 亿能部落格---观察思维比思维本身更重要

2、数学分析

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

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

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

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

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

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

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

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

迷宫的数学建模 - 亿能 - 亿能部落格---观察思维比思维本身更重要


本文引用地址:http://blog.sciencenet.cn/blog-671857-567654.html  此文来自科学网孟现柱博客,转载请注明出处。
  评论这张
 
阅读(265)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017