您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q56: 鬼脚图中的横线(思路1)

时间:12-31来源:作者:点击数:

1. 问题描述

2. 解题分析

感觉非常没有头绪。先做一些实例计算分析。

2.1 贪心策略

考虑图1的{1234--3421}的例子。为了说明方便,以U*表示上边的数字,D*表示下边的数字。以“纵1”表示第一根纵线,余类推。以”横*”表示所添加的横线,横线上的数字(图中8边形中的数字)表示横线添加的序号。

假定按照类似于贪心算法的方式来绘制鬼脚图。

比如说U1要到达D1,必须横跨中间两根纵线,因此可以画出对应的横线如下图所示:

接下来考虑U2àD2. U2往下走时先碰到横1横跨到纵1,然后肯定必须再加一根横线回到纵2。但是这根横线添加的(相对于其它已经添加的横2、3的)纵向相对位置是与后续动作相关的,所以必须分情况考虑。显然这里有三种可能的情况,如下所示:

上图中的(2.1)由于横4的加入导致原来的U1到D1的路径发生了变化,所以予以排除(注1:暂时按照这种规则进行)。

图(2.2)中U2经过横1、横4后回到纵2,然后需要再添加一条横线到达D2,同样有相对于横3的上下相对位置的两种选择。但是如果添加到横3上面(横4与横3之间)的话,会导致原U1到D1的路径发生变化所以排除(2.2.1)。因此只有一种选择,如下图所示(2.2.2):

接下来继续考虑(2.2.2),我们会发现在(2.2.2)中U3和U4已经可以借助既有横线到达目的点了:U3-横2-横4;U4-横3-横5。因此我们得到{1234--3421}的第一个鬼脚图解。

接下来再回头考虑(2.3)的继续。U2要到到达D2还要追加一条线,由于横4已经比横3低了,所以追加横5只有一种可能。如下图所示:

然后我们同样发现,在(2.3.1)中U3和U4已经可以借助既有横线到达目的点了:U3-横2-横4-D3;U4-横3-横5-D4。因此我们得到{1234--3421}的第二个鬼脚图解。

以上我们基于类似于贪心算法的思路得到了{1234--3421}的两个鬼脚图解。但是这里存在几个问题:

  1. 如何确保,或者说如何证明,以上贪心算法总能得到最优解?
  2. 以上鬼脚图绘制规则由人手动来做的话似乎是一目了然的,但是如何让计算机按照这个规则来搜索呢,或者说如何编程呢?

试图总结以上鬼脚图绘制贪心策略如下(CSDN上不能很好地支持WORD复制过来的自动缩进所以只好贴图):

以上可以看作是一个基于贪心策略的深度优先搜索问题。虽然前进了一步,但是依然没有解决前面提及的两个问题:如何证明最优性或非最优性?如何编程?甚至,以上规则难以显而易见地判断是正确的。。。不过作为一种思路记录下来总归是有价值的

3. 代码及测试

4. 后记

[2021-11-05] 非常惭愧,这道题目从最开始看到过去了两个星期。但是一直没有找到明确的头绪,所以暂时先把到目前为止的思路列上。欢迎小伙伴们讨论指点。不过我还没有放弃(还没有想去偷看原书答案),还是希望自己能够找到一个属于自己的(哪怕笨拙)解决方案^-^毕竟现实生活中的问题并不总是有答案可以参考的。

[2021-11-08] 本问题的第2个思路参见:程序员的算法趣题Q56: 鬼脚图中的横线(思路2)

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门