感觉非常没有头绪。先做一些实例计算分析。
考虑图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}的两个鬼脚图解。但是这里存在几个问题:
试图总结以上鬼脚图绘制贪心策略如下(CSDN上不能很好地支持WORD复制过来的自动缩进所以只好贴图):
以上可以看作是一个基于贪心策略的深度优先搜索问题。虽然前进了一步,但是依然没有解决前面提及的两个问题:如何证明最优性或非最优性?如何编程?甚至,以上规则难以显而易见地判断是正确的。。。不过作为一种思路记录下来总归是有价值的
[2021-11-05] 非常惭愧,这道题目从最开始看到过去了两个星期。但是一直没有找到明确的头绪,所以暂时先把到目前为止的思路列上。欢迎小伙伴们讨论指点。不过我还没有放弃(还没有想去偷看原书答案),还是希望自己能够找到一个属于自己的(哪怕笨拙)解决方案^-^毕竟现实生活中的问题并不总是有答案可以参考的。
[2021-11-08] 本问题的第2个思路参见:程序员的算法趣题Q56: 鬼脚图中的横线(思路2)