程序员的算法趣题Q49: 欲速则不达

BlackMass 发布于2021-10-11 10:58 / 3407人阅读

摘要：本文先考虑深度优先搜索。深度优先搜索算法流程如下最后，将初始化为，初始化，和分别初始化为适当的全零数组，然后调用到最终退出后所得到的即为所求结果。

1. 问题描述

2. 解题分析

3. 代码及测试

4. 后记

1. 问题描述

2. 解题分析

本题是要找最长路径，应该广度优先搜索和深度优先搜索都可以。本文先考虑深度优先搜索。

本题与以前的类似的题目的区别在于约束条件的不同，比如说之前有类似的题目的约束条件是不能重复通过一条边，或者路线不能交叉，等等。本题的约束条件是在同一条直线上不能移动两次。因此在深度优先搜索过程中需要记录当前搜索路径中每条直线上已经移动过的次数，并结合边界条件下来确定从当前位置出发的下一步可能的移动方向。

移动网格如上图所示，以n和m分别表示纵向宽度和横向长度，出发点坐标为(0,0),目标点坐标为(n,m)。横向和纵向分别有(n+1)条直线和(m+1) 条直线，分别用H和V表示(n+1)条横线和(m+1)条纵线已经移动过的次数。

深度优先搜索算法流程如下：

最后，将curpos初始化为(0,0)，steps初始化0，H和V分别初始化为适当size的全零数组，然后调用dfs()到最终退出后所得到的maxsteps即为所求结果。在以下代码实现中，maxsteps指定为全局变量，这样避免了参数传递的麻烦。

以上流程中，“还原H和V” 比较容易忘记，这个相当于函数递归调用退回时的退栈处理。只不过递归调用的退栈处理是编译器进行了自动管理。但是如果像steps那样的传递的话，由于没有更新当前递归层次的值，所以就不需要还原处理。

3. 代码及测试

# -*- coding: utf-8 -*-"""Created on Sat Oct  9 07:12:37 2021@author: chenxy"""# import sysimport timefrom   collections import dequen = 5m = 6target = (n,m)maxsteps = 0H = (n+1)*[0]V = (m+1)*[0]def dfs(curpos, H, V, steps):    # print(curpos, H, V, steps)    global maxsteps    if curpos == target:        if maxsteps < steps:            maxsteps = steps    # Up trial    if curpos[0] > 0 and V[curpos[1]] < 2:        nxtpos = (curpos[0]-1, curpos[1])        V[curpos[1]] = V[curpos[1]] + 1        dfs(nxtpos, H, V, steps+1)        V[curpos[1]] = V[curpos[1]] - 1    # Down trial    if curpos[0] < n and V[curpos[1]] < 2:        nxtpos = (curpos[0]+1, curpos[1])        V[curpos[1]] = V[curpos[1]] + 1            dfs(nxtpos, H, V, steps+1)        V[curpos[1]] = V[curpos[1]] - 1        # Left trial    if curpos[1] > 0 and H[curpos[0]] < 2:        nxtpos = (curpos[0], curpos[1]-1)        H[curpos[0]] = H[curpos[0]] + 1            dfs(nxtpos, H, V, steps+1)        H[curpos[0]] = H[curpos[0]] - 1        # Right trial    if curpos[1] < m and H[curpos[0]] < 2:        nxtpos = (curpos[0], curpos[1]+1)        H[curpos[0]] = H[curpos[0]] + 1                dfs(nxtpos, H, V, steps+1)        H[curpos[0]] = H[curpos[0]] - 1        returntStart  = time.perf_counter()dfs((0,0),H,V,0)tCost  = time.perf_counter() - tStartprint("n={0}, m={1}, maxsteps={2}, tCost = {3:6.3f}(sec)".format(n,m,maxsteps,tCost))

运行结果：n=5, m=6, maxsteps=25, tCost = 1.682(sec)

4. 后记

运行速度有点差强人意。

接下来看看用广度优先搜索策略是不是能够更快一些。

上一篇：Q48: 翻转得到交错排列

下一篇：Q50: 完美洗牌

本系列总目录参见：程序员的算法趣题：详细分析和Python全解

GPU云服务器云服务器最短路算法的程序最复杂的程序算法最厉害的算法想法程序 php程序员玩转算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/122172.html

程序员的算法趣题Q54: 偷懒的算盘

摘要：且听下回分解基于动态规划策略的优化解法参见程序员的算法趣题偷懒的算盘上一篇程序员的算法趣题同数包夹程序员的算法趣题同数包夹本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...

wangzy2019 2021-10-14 09:43 评论0 收藏0
程序员的算法趣题Q22: 不缠绕的纸杯电话

摘要：假设有几个小朋友以相同间隔围成圆周，要结对用纸杯电话相互通话。如果绳子交叉，很有可能会缠绕起来，所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问...

MoAir 2021-09-09 09:33 评论0 收藏0
程序员的算法趣题Q46: 唯一的OX序列

摘要：可以在遍历所有矩阵时，对各种出现的次数进行计数，最后计数值为的个数即为所求结果。上一篇排序交换次数的最少化排序交换次数的最少化本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...

y1chuan 2021-09-30 09:47 评论0 收藏0
程序员的算法趣题Q45: 排序交换次数的最少化

摘要：能以最少交换次数到达升序有序排列记为的数列记为就等价于从代表的节点在这张图中到达对应的节点的最短路径长度。上一篇质数矩阵质数矩阵下一篇唯一的序列本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 ...

flybywind 2021-09-29 09:35 评论0 收藏0