图论算法基础 之 浅谈骑士巡逻问题（神经网络算法）与哈密顿路径

lee1892

在开放式竞赛区有这样一道题：[开_72]一道益智题，试试大家的编程技巧

其题目的要求可以描述为：
在一个4x4个格子的棋盘中，去掉左上角和右上角两个格子，取一棋子在棋盘上走日字格（如国际象棋中的马），该棋子由某一格开始经过所有格子且只经过一次并回到出发格子所形成的路径称为“答案路径”，要求找出所有可能的“答案路径”。

在该贴中，所有人都采用一个2维数组来模拟棋盘，并通过穷举的方式遍历所有可能的走法，但没有人揭示这道题目背后所隐藏的数学含义。

实际上，这道题是在寻找图论中一个非常有名的路径，其被称之为哈密顿回路（Hamiltonian Cycle）。有关图论的一些基础知识，可参考我之前的主题贴：图论算法基础 之 计算两点间最短路径（三种算法的介绍）。

哈密顿路径（Hamiltonian Path）：通过边（Edge）访问所有顶点（Vertex）一次且仅一次的路径。
哈密顿回路（Hamiltonian Cycle）：能够回到出发顶点的哈密顿路径。

按上述题目的描述，可以把棋盘格子作为图中的顶点，则该棋盘可视作如下的一个图：

按照题意，连接顶点之间的边实际上是日字格的对角线而不是上面图中表现得，为此可以通过下述代码进行转换得到所需要的图的结构：
[code=vb]Private Type PADDLE_INFO
    Name    As String
    X       As Integer
    Y       As Integer
    Links   As Collection
End Type

Private aPads(13) As PADDLE_INFO
Private Sub GenerateGraph()
    Dim i%, j%, k%, nCnt%, sCon$
    nCnt = -1
    For i = 0 To 3
        For j = 0 To 3
            If Not (i = 0 And j = 3) And Not (i = 3 And j = 3) Then
                nCnt = nCnt + 1
                With aPads(nCnt)
                    .Name = i & "_" & j
                    .X = i: .Y = j
                    Set .Links = New Collection
                End With
            End If
        Next
    Next
    For i = 0 To nCnt
        sCon = ""
        For j = 0 To nCnt
            If i <> j Then
                If Abs(aPads(i).X - aPads(j).X) * Abs(aPads(i).Y - aPads(j).Y) = 2 Then
                    aPads(i).Links.Add j
                    sCon = sCon & ", " & aPads(j).Name
                End If
            End If
        Next
        sCon = Right(sCon, Len(sCon) - 2)
    Next
End Sub[/code]


那么上面这个图中一个哈密顿回路（或曰答案路径）可以是如下形式，红点为起始顶点：




补充内容 (2013-10-18 15:27):
到第12楼

lee1892

现在我们得到了用于计算的一个简单的图的数据结构，顶点是aPads数组中的元素，边则通过顶点的Links集合来表达。显然这是一个无向的简单图。

可以采用深度优先遍历来找到“答案路径”，其伪代码如下：
[code=vb]Sub 寻找路径(ByVal 当前顶点)
For Each 下一个顶点 In 当前顶点.连通的顶点集合
    If 未经过(下一个顶点) Then
        If 下一个顶点 = 起始点 And 已通过顶点数量 = 总数量 - 1 Then
            找到答案路径，记录该路径
        ElseIf 下一个顶点 <> 起始点 And 已通过顶点数量 < 总数量 - 1 Then
            添加下一个顶点至已通过顶点集合
            Call 寻找路径(下一个顶点)
            自已通过顶点集合中移除下一个顶点
        End If
    End If
Next
End Sub[/code]

为此，我们需要设置几个全局变量，实际的实现代码如下：
[code=vb]Private dicPathed As Object         ' 查找路径时，已经通过的顶点编号作为字典的Key
Private nPadStart As Integer        ' 起始顶点元素编号
Private nSolveCnt As Long           ' 找到的答案路径的计数
Private aSolve() As String          ' 答案路径结果数组
Private Sub FindHamiltonianCycle(ByVal nPadNow%)
    Dim nNext, aPathed, i%
    '// nNext   当前顶点所连通的下一个顶点
    '// aPathed 临时数组，记录答案路径用
    For Each nNext In aPads(nPadNow).Links
        If Not dicPathed.exists(nNext) Then
        ' 如果下一个顶点未通过则继续判断，否则跳过
            If nNext = nPadStart And dicPathed.Count = 13 Then
            ' 如果下一个顶点是起始顶点，并且已经通过了13个顶点
            ' （共14个顶点，起始顶点不在已经通过的顶点字典中）
            ' 记录该路径至结果数组
                aPathed = dicPathed.keys
                nSolveCnt = nSolveCnt + 1
                aSolve(nSolveCnt, 0) = aPads(nPadStart).Name
                For i = 0 To dicPathed.Count - 1
                    aSolve(nSolveCnt, i + 1) = aPads(aPathed(i)).Name
                Next
            ElseIf nNext <> nPadStart And dicPathed.Count <= 13 Then
            ' 如果下一个顶点不是起始顶点，并且已经通过的顶点数量不大于13
                dicPathed(nNext) = True     ' 添加下一个顶点至字典
                FindHamiltonianCycle nNext  ' 递归寻找下一个顶点为当前点
                dicPathed.Remove nNext      ' 该下一个顶点查找完成，由字典中删除
            End If
        End If
    Next
End Sub[/code]

有了上述代码后，对每个顶点循环调用即可获得全部答案路径，比如：
[code=vb]For nPadStart = 0 To 13
    FindHamiltonianCycle nPadStart
Next[/code]

我们注意到，这个图是左右对称的，可想而知仅需要对左侧的7个点作为起始点查找，而后镜像，就可获得右侧的结果。于是有了如下代码作为查找全部路径的主过程：
[code=vb]Public Sub FindPath()
    Dim t#, tt#, s$, dicMirror As Object, nMirror%, i&, j&
    Sheet1.Columns("A:N").ClearContents
    t = Timer: tt = t
    GenerateGraph
    s = vbCrLf & vbCrLf & "Generate graph used: " & Format(Timer - t, "0.000s")
    t = Timer
   
    Set dicPathed = CreateObject("Scripting.Dictionary")
    ReDim aSolve(200, 13)
    nSolveCnt = -1
    s = s & vbCrLf & "Claim memory used: " & Format(Timer - t, "0.000s")
    t = Timer
   
    Set dicMirror = CreateObject("Scripting.Dictionary")
    For nPadStart = 0 To 6
        FindHamiltonianCycle nPadStart
        nMirror = IIf(nPadStart < 3, nPadStart + 11, nPadStart + 4)
        dicMirror(aPads(nPadStart).Name) = aPads(nMirror).Name
        dicMirror(aPads(nMirror).Name) = aPads(nPadStart).Name
    Next
    For i = 0 To nSolveCnt
        For j = 0 To 13
            aSolve(i + nSolveCnt + 1, j) = dicMirror(aSolve(i, j))
        Next
    Next
    nSolveCnt = nSolveCnt * 2 + 1
    s = s & vbCrLf & "Searching path used: " & Format(Timer - t, "0.000s")
    t = Timer
   
    Set dicPathed = Nothing: Set dicMirror = Nothing
    Sheet1.Cells(1, 1).Resize(nSolveCnt + 1, 13 + 1) = aSolve
    s = s & vbCrLf & "Output to Excel used: " & Format(Timer - t, "0.000s")
    s = s & vbCrLf & vbCrLf & "Totally used: " & Format(Timer - tt, "0.000s")
   
    MsgBox s
End Sub[/code]

完整代码见附件： [开_72]一道益智题 Lee1892.rar (27.14 KB, 下载次数: 165)

2013-10-10 13:05 上传

点击文件名下载附件

该附件中还能显示如下动画效果：

lee1892

运行前贴中的附件，我们可以找到共计112个“答案路径”。

但需要注意到，既然是一个闭合的路径，那么也就意味着在一条路径上由不同的点开始会对应至不同的“答案路径”。如果我们称一个封闭的回路为“答案回路”，而不考虑起始点，那么可知：“答案回路” * 顶点数量 = “答案路径”。换言之，只需要寻找由一个顶点开始的“答案路径”，就可以找到全部的“答案路径”。

由此，可将上述代码中寻找路径部分的代码更换为如下形式：
[code=vb]    nPadStart = 0
    FindHamiltonianCycle 0
    For nPadStart = 1 To 13
        sName = aPads(nPadStart).Name
        For i = 0 To nSolveCnt
            For k = 0 To 13
                If aSolve(i, k) = sName Then Exit For
            Next
            For j = 0 To 13
                aSolve(i + (nSolveCnt + 1) * nPadStart, j) = aSolve(i, (j + k) Mod (13 + 1))
            Next
        Next
    Next
    nSolveCnt = (nSolveCnt + 1) * (13 + 1) - 1[/code]
替换下述部分：
[code=vb]    Set dicMirror = CreateObject("Scripting.Dictionary")
'......
    nSolveCnt = nSolveCnt * 2 + 1[/code]
如此，则查找速度大幅提高，在我的机器上由原先的0.063s变成了0.012s。

再进一步的考量，对于由一个顶点开始的回路而言，其必然是由该顶点的一个边出发而由另一个边返回，如果将该回路反向行走的话就会得到另一个前述的“答案回路”，或可称之为“有向回路”和“无向回路”。显然，“有向回路” = “无向回路” * 2。于是可以进一步改进查找过程的代码，对于起始顶点，只向下搜索其一半的邻接顶点即可，这里就不再展开了。

lee1892

如果你注意到这个帖子的标题中的骑士巡逻问题，并且去查询了相关信息，你一定就会知道这个益智题的由来是一个非常古老的被称为骑士巡逻问题（Knight's Tour），该问题的提出可以追溯到9世纪的印度。

在一个8x8的国际象棋棋盘上，棋子骑士（马）走过（日字格走法）所有格子一次且仅一次。如果终点不是起始格则称为开放路径（Open Tour），如果回到起始格则称为封闭路径（Close Tour）。

开放路径示意：


封闭路径示意：


按此前的讨论，我们将其转化成数据结构中的图，并标记各节点的邻接点数量，则可以得到如下的样子：


已经被计算出共有 26,534,728,821,064 个“答案路径”，开放路径的数量则未知......

对于更为普遍的 m X n （m不大于n）格的棋盘而言，已经被证明其总是存在封闭路径，除非满足下述三个条件有一个或多个：
1）m 和 n 都是奇数
2）m = 1、2 或 4
3）m = 3 且 n = 4、6 或 8

而对于任意一个矩形棋盘，只要 m 不小于 5，则必定存在巡逻路径（可能是开放的）。

lee1892

骑士巡逻问题的计算（通常指找到一个路径，而非穷举所有可能）：

1）暴力计算
采用前面所描述的深度优先搜索的办法，可以保证只要存在就能找到，但由于随着行列数的增加，可能的路径选择数量增长太快，所以对稍大点的棋盘其耗时就无法忍受了。

2）分治的算法
可以将一个较大的棋盘拆分成数个较小的棋盘，而后将每个棋盘的开放路径连接起来，就可以找到路径。采用这种方法可以有效降低寻找时间。

3）神经网络算法
按前面的图数据结构，棋盘中的格子称为顶点，两个顶点间的连通称为边，则可将所有的边设为神经元。神经元有状态（U）和结果（V）两个属性，状态的初始值为随机的激活（1）或未激活（0），结果的初始值均为未激活（0）。
神经网络运行时，各神经元按照下述规则改变其状态和结果两个属性：
对神经元 N(i, j)，其 U(t+1) = U(t) + 2 - SUM(V(t)(N))，SUM(V(t)(N)) 表示该神经元同行同列的各神经元的 V(t) 值之和
如果 U(t+1) > 3，则 V(t+1) = 1
如果 U(t+1) < 0，则 V(t+1) = 0
否则 V(t+1) = V(t)
其中 t 表示网络运行的次数
当网络运行到前后两次的结果值全部相同时，则称网络是收敛的，并停止运行。按一些人的测试，这样的一个网络通常运行不超过1000次就会收敛。
收敛时得到的V值或则是一个闭合回路，或则是数个。
由于初始值的随机性，多尝试几次后，就有很大的可能获得巡逻回路。

用VBA实现的神经网络算法计算 8x8，尝试30次，耗时11秒多找到4个解：


由神经网络计算找到的14x14的巡逻回路（用暴力算法基本不可能呀）


强悍的20x20：


疯狂的26x26：


4）启发式计算
Warnsdorff's Rule：可以在线形时间内找到（如果存在）巡逻路经（通常开放）。按前面的图数据结构的示意图，每个格子都标注了其连通的格子的数量，当棋子进入一个格子时，将其所连通的各格子内的数字都减 1，该棋子的下一步是走到标注数量最少的那个格子。

附件包含了1、3、4的代码： 骑士巡逻问题 Lee1892.rar (51.62 KB, 下载次数: 205)

2013-10-14 14:41 上传

点击文件名下载附件

lee1892

骑士巡逻问题差不多就这些内容可聊了，或许还可一提的是所谓最长无交叉巡逻路径，如下：

n=7时，最长无交叉封闭路径=24：


n=8时，最长无交叉开放路径=35：


关于这个问题貌似没啥人研究，有兴趣的可以去看看：http://euler.free.fr/knight/index.htm

另外，前面提到的那个神经网络算法，貌似对付这种节点互相限制的问题很有效，感觉拉丁方阵、数独之类的都可以应用，有时间学习学习~

lee1892

结束之前

关于哈密顿路径：

其定义之前已经提到，对于普遍意义上而言的图，寻找哈密顿路径或是回路是一个NP完全（NP-Complete）问题，无论是有向图还是无向图。

有一些定理可以帮助判断其是否是存在哈密顿路径，比如：

Dirac： 一个简单图，其顶点（Vertex）数量 n >=3，如果每个顶点的度（Degree，图论名词，不同于边 Edge）>= n/2，则存在哈密顿路径。

Ore：一个图，其顶点数量 n >=3，如果对于每一对邻接点对，其度之和 >= n，则存在哈密顿路径。

值得一提的是，旅行商问题的路径是一个特殊的哈密顿路径，参见会跑法师的帖子：http://club.excelhome.net/thread-688274-1-1.html

另外，与之相对应的欧拉路径（Eulerian Path），由著名的七桥问题衍生而来，即不重复的经过所有边的路径。

关于神经网络算法：

我也是初次接触这个，照着描述勉强作出来的。感觉：

1、收敛与否以及收敛速度与初始的随机值有很大关系，包括随机值的范围（0、1 貌似不是好的选择）和概率。

2、怀疑一次网络运行的结果，无论其是否收敛，能否作为下次运行时初始值的参考，以加速网络的收敛。如果确实有参考价值的话，那么就有点遗传的意思了。

3、这种算法应该很适合应用在节点间互相限制的问题，如拉丁方阵、数独等等，其效率如何有待测试。

以上。

lee1892

另外，对神经网络算法加了些功能，方便学习，有兴趣的同学可以下载附件： 骑士巡逻问题 神经网络算法 Lee1892.rar (71.27 KB, 下载次数: 212)

2013-10-16 15:59 上传

点击文件名下载附件

参考动画：




补充内容 (2013-12-2 08:51):
附件中尝试次数标签和文本框在原位置有重复的两个，需要将上方的那个删除。

yuanhongly

好贴  ，前排占位。

antlia

属于数据结构中比较深奥的部分了，图论啊，对数学知识要求不是一般高。
感谢lee1892 老师，Mark 慢慢学，现在基本上一点看不懂。

zjyriqing

先标记，再学习

lipton

做个记号，感谢分享。