程序员的算法趣题Q31: 计算最短路径

1. 问题描述

本题来自《程序员的算法趣题》中的第31题。

假设有正方形被划分为若干个边长为1cm的正方形方格。请思考沿着正方形方格的边从左下角到右上角再回到左下角（*1）往返的情况。这里往返程不能经过同一条边（但是允许往返路径有交叉点）。

求大的正方形的不同边长N（cm）时，总共有多少种最短路径？

*1 与原题略有不同—但是没有本质区别，只是作者习惯了迎合平面坐标系第一象限来思考

N=1时，很显然有两条路径；N=2时，有10条路径。如下图所示。

2. 解题思路

2.1 BFS or DFS

第一感应该能够想到这是一个跟图遍历搜索相关的问题。“最短路径”容易让人联想到BFS(广度优先搜索)，然而本题并不是BFS的菜。本题的重点在于要找出所有的最短路径（而最短路径的长度本身其实是确定性的，只要保证去程只向上或向右，回程只向下或向左，就能保证是最短路径），所以这道题可以用深度优先搜索算法来解决。

2.2 节点的表示

既然要作为图搜索问题来解决，那第一个问题就是这个隐含的图（implicit graph）的节点表示什么？题目要求往返程的边是不能重复的，但是交叉点是可以重复的，所以这里考虑用正方形方格的边来对应“图的节点”。每条边以嵌套的tuple--((x0,y0), (x1,y1), direction)来表示。(x0,y0)和(x1,y1)分别表示通过这条边时的起点和终点，这是一个有向表示。direction用于指示通过当前这条边时是去程还是在回程—不是必须的，根据(x0,y0)和(x1,y1)也可以判断出这条边的通过方向。

2.3 如何避免往返程通过相同的边

上面说了“边”是以有向的方式表示的，但是题目的要求是往返程不能通过相同的边，不论方向。所以在通过对比以确定一条边是否被访问过时需要去除掉方向信息，只要两个端点相同即为相同的边。在以下代码中的实现方式是在将“边”加入visited时，是成对地加入，以存储的代价换取查询visited的便利。

但是visited的管理与通常的递归式深度优先搜索中的处理又有所不同。在以下代码实现中，visited是作为参数传入dfs()，并且在每次退出时将进入dfs()函数是添加的节点又弹出去了--To be frankly, 初始代码在这里掉坑里了。。。等彻底想清楚如何解释再来追加解释。

3. 代码与测试

# -*- coding: utf-8 -*-
"""
Created on Sun Aug 22 08:23:28 2021

@author: chenxy
"""

import sys
import time
import random
# from math import gcd, sqrt, ceil
# from   typing import List
# from   queue import Queue

class Solution:

    def shortestRoundTrip(self, N:int)->int:
        """
        :N:    The size of the square grid network
        :    
        :ret:  The number of the solutions
        """

        leftBotm  = (0,0)        
        rightTop  = (N,N)        
        
        def dfs(edge, pathCnt, visited):
            # print('dfs: edge = ',edge)
            if edge[1] == leftBotm: # Complete one round-trip
                # print('dfs: Complete one round-trip!')
                return pathCnt + 1                
            
            visited.append(edge)
            visited.append((edge[1],edge[0],1-edge[2]))
            
            # Decide the candidates for the next edge. Care for not crossing the boundary
            x = edge[1][0]
            y = edge[1][1]            
            if edge[2] == 0: # Forward path
                if x == N and y == N: #edge[1] == rightTop: 
                    nxtedge1 = (edge[1],(x-1,y),1)  # Move left
                    nxtedge2 = (edge[1],(x,y-1),1)  # Move down                  
                elif x == N:
                    nxtedge1 = ()
                    nxtedge2 = (edge[1],(x,y+1),0)  # Move up
                elif y == N:
                    nxtedge2 = ()
                    nxtedge1 = (edge[1],(x+1,y),0)  # Move right
                else:
                    nxtedge1 = (edge[1],(x+1,y),0)  # Move right
                    nxtedge2 = (edge[1],(x,y+1),0)  # Move up                    
            else:
                if x == 0:
                    nxtedge1 = ()
                    nxtedge2 = (edge[1],(x,y-1),1)  # Move down                                      
                elif y == 0:
                    nxtedge2 = ()
                    nxtedge1 = (edge[1],(x-1,y),1)  # Move left
                else:
                    nxtedge1 = (edge[1],(x-1,y),1)  # Move left
                    nxtedge2 = (edge[1],(x,y-1),1)  # Move down                                      
                    
            pathCnt1,pathCnt2 = 0,0
            if (nxtedge1 not in visited) and (nxtedge1 != ()):
                pathCnt1 = dfs(nxtedge1,pathCnt,visited)
            if (nxtedge2 not in visited) and (nxtedge2 != ()):
                pathCnt2 = dfs(nxtedge2,pathCnt,visited)
            
            visited.pop()
            visited.pop()
            
            return pathCnt1 + pathCnt2
             
        # Start from the following two call, and finally return pathCnt
        return dfs(((0,0),(0,1),0),0,[]) + dfs(((0,0),(1,0),0),0,[])

测试代码如下：

if __name__ == '__main__':        
    
    sln = Solution()

    for N in range(2,8):
        tStart = time.time()
        num = sln.shortestRoundTrip(N)
        tCost = time.time() - tStart
        print('N = {0}, numSlns = {1}, tCost = {2}(sec)'.format(N,num,tCost))    

运行结果如下：

N = 2, numSlns = 10, tCost = 0.0(sec)

N = 3, numSlns = 80, tCost = 0.0(sec)

N = 4, numSlns = 786, tCost = 0.007980823516845703(sec)

N = 5, numSlns = 8592, tCost = 0.10571455955505371(sec)

N = 6, numSlns = 100360, tCost = 1.3892908096313477(sec)

N = 7, numSlns = 1227200, tCost = 19.797149658203125(sec)

大概N增加1，运行时间增加15倍的样子。要想搜索N更大时的情况，需要进一步优化实现，或者甚至从根本上调整实现策略。