摘要:本文先考慮深度優(yōu)先搜索。深度優(yōu)先搜索算法流程如下最后,將初始化為,初始化,和分別初始化為適當(dāng)?shù)娜銛?shù)組,然后調(diào)用到最終退出后所得到的即為所求結(jié)果。
目錄
????????本題是要找最長(zhǎng)路徑,應(yīng)該廣度優(yōu)先搜索和深度優(yōu)先搜索都可以。本文先考慮深度優(yōu)先搜索。
????????本題與以前的類似的題目的區(qū)別在于約束條件的不同,比如說(shuō)之前有類似的題目的約束條件是不能重復(fù)通過(guò)一條邊,或者路線不能交叉,等等。本題的約束條件是在同一條直線上不能移動(dòng)兩次。因此在深度優(yōu)先搜索過(guò)程中需要記錄當(dāng)前搜索路徑中每條直線上已經(jīng)移動(dòng)過(guò)的次數(shù),并結(jié)合邊界條件下來(lái)確定從當(dāng)前位置出發(fā)的下一步可能的移動(dòng)方向。
????????移動(dòng)網(wǎng)格如上圖所示,以n和m分別表示縱向?qū)挾群蜋M向長(zhǎng)度,出發(fā)點(diǎn)坐標(biāo)為(0,0),目標(biāo)點(diǎn)坐標(biāo)為(n,m)。橫向和縱向分別有(n+1)條直線和(m+1) 條直線,分別用H和V表示(n+1)條橫線和(m+1)條縱線已經(jīng)移動(dòng)過(guò)的次數(shù)。
????????深度優(yōu)先搜索算法流程如下:
? ? ? ?最后,將curpos初始化為(0,0),steps初始化0,H和V分別初始化為適當(dāng)size的全零數(shù)組,然后調(diào)用dfs()到最終退出后所得到的maxsteps即為所求結(jié)果。在以下代碼實(shí)現(xiàn)中,maxsteps指定為全局變量,這樣避免了參數(shù)傳遞的麻煩。
以上流程中,“還原H和V” 比較容易忘記,這個(gè)相當(dāng)于函數(shù)遞歸調(diào)用退回時(shí)的退棧處理。只不過(guò)遞歸調(diào)用的退棧處理是編譯器進(jìn)行了自動(dòng)管理。但是如果像steps那樣的傳遞的話,由于沒(méi)有更新當(dāng)前遞歸層次的值,所以就不需要還原處理。
??
# -*- 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))
????????運(yùn)行結(jié)果:n=5, m=6, maxsteps=25, tCost = ?1.682(sec)
? ? ? ? 運(yùn)行速度有點(diǎn)差強(qiáng)人意。
? ? ? ? 接下來(lái)看看用廣度優(yōu)先搜索策略是不是能夠更快一些。
? ? ? ? 上一篇:Q48: 翻轉(zhuǎn)得到交錯(cuò)排列
? ? ? ? 下一篇:Q50: 完美洗牌
????????本系列總目錄參見(jiàn):程序員的算法趣題:詳細(xì)分析和Python全解
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/122172.html
摘要:且聽(tīng)下回分解基于動(dòng)態(tài)規(guī)劃策略的優(yōu)化解法參見(jiàn)程序員的算法趣題偷懶的算盤(pán)上一篇程序員的算法趣題同數(shù)包夾程序員的算法趣題同數(shù)包夾本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問(wèn)題描述 2. 解題分析 3. 代碼及測(cè)試 4. 后記 1. 問(wèn)題描述 ??...
摘要:假設(shè)有幾個(gè)小朋友以相同間隔圍成圓周,要結(jié)對(duì)用紙杯電話相互通話。如果繩子交叉,很有可能會(huì)纏繞起來(lái),所以結(jié)對(duì)的原則是不能讓繩子交叉。如下所示運(yùn)行結(jié)果上一篇異或楊輝三角形下一篇禁止右轉(zhuǎn)本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問(wèn)題描述 2. 解題分析 3. 代碼及測(cè)試 1. 問(wèn)...
摘要:可以在遍歷所有矩陣時(shí),對(duì)各種出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù),最后計(jì)數(shù)值為的個(gè)數(shù)即為所求結(jié)果。上一篇排序交換次數(shù)的最少化排序交換次數(shù)的最少化本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問(wèn)題描述 2. 解題分析 3. 代碼及測(cè)試 4. 后記 1. 問(wèn)題描述 ...
摘要:能以最少交換次數(shù)到達(dá)升序有序排列記為的數(shù)列記為就等價(jià)于從代表的節(jié)點(diǎn)在這張圖中到達(dá)對(duì)應(yīng)的節(jié)點(diǎn)的最短路徑長(zhǎng)度。上一篇質(zhì)數(shù)矩陣質(zhì)數(shù)矩陣下一篇唯一的序列本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問(wèn)題描述 2. 解題分析 3. 代碼及測(cè)試 4. 后記 ...
閱讀 3526·2023-04-25 17:35
閱讀 2599·2021-11-24 09:39
閱讀 2537·2021-10-18 13:32
閱讀 3424·2021-10-11 10:58
閱讀 1641·2021-09-26 09:55
閱讀 6175·2021-09-22 15:47
閱讀 972·2021-08-26 14:15
閱讀 3476·2019-08-30 15:55