程序员的算法趣题Q56: 鬼脚图中的横线（思路2）

1. 问题描述

问题描述以及关于本问题的第一个思路参见：程序员的算法趣题Q56: 鬼脚图中的横线(思路1)

2. 思路2

仍然考虑图1的{1234-->3421}的例子。

在之前的讨论中我们已经得到了{1234-->3421}的两个鬼脚图连线方式，如下图所示的(2.2.2)和(2.3.1)。

2.1从鬼脚图出发进行变形

考虑将横线缩为一个点进行变形（类似于拓扑学中的那种变形）会得到什么呢？如下图所示：

图1

进一步将线扯扯直，让每一对Uk—Dk的路径变成直线，我们会发现以上图(A)和图(B)会得到相同的图，如下图所示（先扯直U1-D1, U3-D3, U4-D4，得到(C)，然后再挪动以下位置将U2-D2也扯直得到(D)，以下我们称这种图为交叉图）：

图2

这个意味着什么呢？是不是意味着原问题可以转变为“上下两排之间对应数字之间连线，求最小的交叉点的个数”的问题呢？

下面我们来进一步探索。

2.2 反向变换

注意，从以上图(D)的交叉图出发遵照前述鬼脚图的规则是可以恢复出原鬼脚图的（恢复的方法参见以下说明）。下面我们从一个一个与图(D)略微不同的交叉图(E)（这种不同仅仅在于上下两排点的相对间距不同导致直线连接后的交叉点的位置不同而已）出发看看反向能恢复出什么来。

首先从U1（记得前面我们提过U表示Upper，D表示Down，Uk表示上边的k节点，Dk表示下边的k节点）出发，因为U1到D1经过(1)，(2)，(3)三个交叉点，我们知道每个交叉点对应一条横线，因此可以先画出三条横线，而且横2位置在横1之下，横3在横2之下。

接下来，考虑U2的路径。U2的路径先碰到交叉点(4)，对应鬼脚图上横4的线，但是横4是应该往左画还是往右画呢？首先横4必然是在横2上面（如果不是的话，U2出发后就应该先碰到交叉点(2)）；其次，如果往左画的话，要么在横1上面，要么在横1下面。在横1下面画不行，因为这样破坏了U1的路径。在横1上面画也不行，因为这样的话，U2在(4)之后就应该是碰到(1)而不是如左图中的(2)。所以，横4只能是往右画，而且必须在横1上面。然后，U2在(4)之后碰到(5)，这对应着在右图需要追加一条新的横5，显然它只能往右画（因为D2在右边）而且必然在横3下边（不然的话U2在(4)之后就会碰到(3)）。

接下来，考虑U3的路径。此时图上已经有了横1，2，3，4，5。很显然U3经过(4)和(1)可以到达D3，这个在作图和右图都成立。因此不需要追加新的横线。

接下来，考虑U4的路径。左图中U4先碰到(3)然后是(5)，右图上也已经存在这一条路径了。

图3

好了，大功告成，我们的确从一个新的交叉图恢复出了对应的鬼脚图。而且，surprisingly，这个鬼脚图与我们之前的讨论所得到(2.2.2)和(2.3.1)都不同，我们得到了一个新的鬼脚图！

2.3 进一步探索

如上所述，图(D)和图(E)的差异仅在于上下两排节点的间距稍微不同而已。进一步，显而易见的是，不管从图(D)出发还是从图(E)出发，总可以使得多个交叉出现重叠，这种情况意味着什么呢？还能不能恢复出对应的鬼脚图，重叠的交叉点算多个点还是算一个点？如果算一个点的话，是不是意味着出现了横线更少的鬼脚图呢？

图4

如上图所示，在图(G)中，经过调节上下两排点的相对间隔后，交叉点(1)（2）（4）重叠了。让我们看看基于这个图能恢复出什么来？

首先从U1出发，因为U1到D1经过(1-2-4)（代表上图中三条线公共交叉点）和(3)。我们知道每个交叉点对应一条横线，但是如果把(1-2-4)看作一条横线的话，那么在U1和D1之间只有两条横线，而在鬼脚图中U1和D1之间隔着3格，不可能只经过两条横线到达。由此我们知道多重交叉点必须看作是多个交叉点，不能看作是一个。因此我们仍然把(1-2-4)看作是(1)和(2)和(4)（编号是无所谓的），那么U1到D1的路径可以是(1)-(2)-(3)也可以是(1)-(4)-(3)，由于编号是无所谓的，不失一般性，我们就仍然考虑是(1)-(2)-(3)。这样的话我们仍然可以先画出三条横线，而且横2位置在横1之下，横3在横2之下。(这个与上一节相同)

接下来，考虑U2的路径。此时图中已经有了横1、横2和横3。由于是三个重叠的交叉点，U2的路径是算碰到(1)和(2)和(4)中的哪个呢？显然(2)可以排除，因为横2在横1下面，U2不可能在遇到横1之前先碰到横2。

考虑U2先碰到的是交叉点(4)，对应鬼脚图上横4。那么必然有横4在横1上面。但是横4是应该往左画还是往右画呢？首先横4必然是在横2上面（如果不是的话，U2出发后就应该先碰到交叉点(2)）；其次，如果往左画的画，要么在横1上面，要么在横1下面。在横1下面画不行，因为这样破坏了U1的路径（与上一个例子的道理相同）。在横1上面画呢也不行，因为这样U1就会先碰到横4因而破坏了U1的路径。结论是横4不能往左画，只能是往右画，而且必须在横1上面。然后，U2在(4)之后碰到(5)，这对应着在右图需要追加一条新的横5，显然它只能往右画（因为D2在右边）而且必然在横3下边（不然的话U2在(4)之后就会碰到(3)）。

接下来，考虑U3、U4的路径就和上一节的例子一样了。由此得到了图(H)，其实和图(F)是相同的。

本节的讨论得到的结论是，多重交叉点必须作为多个不同的交叉点来处理。这样我们仍然可以恢复出对应的合法的鬼脚图。

3. 小结

今天的讨论感觉前进了一大步，问题似乎转变成了一个更容易进行算法处理的问题。不过我仍然没有完全想清楚这种对应意味着什么，目前也没有能力给出稍微严谨一点的数学证明。隐隐约约觉得这个跟图论（或甚至拓扑学）中的东西有关联？暂且贴出来看看有没有高手能够指点一下^-^.

Also：

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

对应本文中思路的题解在2021-11-17日发布，参见：程序员的算法趣题Q56: 鬼脚图中的横线(思路2的Python题解)