思考:路径遍历(一)有趣的童年难题

木槿   个人博客   生命的意义,是成为你自己  本文由博客端 https://www.hudk.top 主动推送

image.png
  这个问题是在我上小学时同学告诉我的,当时觉得好玩,就随便瞎画着玩儿,不过从小学到大学,没有一次画成功过。这个问题起初同学告诉我的时候,图不是这样画的,我只是为了好表达,将问题抽象成网格了,原问题是说有 25 个小球,如下图:
image.png
用一笔画,将所有蓝色小球串起来,要求画出的线不允许超过矩阵之外,不允许斜,且每个小球只被经过一次。
两种对问题描述的本质是一样的。
  答案是我的大学同学用数学方法找到的,本质上这确实是一个数学问题,他给出的结论是:不可能存在一条满足要求的路线,证明过程如下:
image.png
  将小球相间着涂成不同颜色,这样,就出现黑球相邻的周围是白球,白球相邻的周围是黑球(忽略橙色球)。换句话说,假如要连线的话,被这条线连起来的小球形成的顺序串儿,一定是黑白小球相间的,不可能出现同色小球相邻。另外,数一数黑色和白色小球的个数,你会发现,黑球有 13 个,白球有 11 个,这就存在一个矛盾:要求把所有黑色和白色球都串起来的话,就会出现,13 个黑球和 11 个白球异色相间地出现在一个序列里。而这中情况不可能出现,因为异色相间的有限序列,两色个数相差不可能超过 1,即出现矛盾。到这里,确实感觉我的同学的方法很巧妙,甚是佩服。
  虽然知道此题的结果,但作为一个程序员还是手痒,心生要写一个可视化寻路算法。请参考文章链接《 算法:路径遍历(二)图上的路径遍历》和《实践:路径遍历(三) 迷宫探秘》,附程序预览 路径遍历迷宫探秘

赞助商 我要投放

回帖
请输入回帖内容 ...