2025年3月15日 星期六 甲辰(龙)年 月十四 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

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

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

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更大时的情况,需要进一步优化实现,或者甚至从根本上调整实现策略。

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