資訊專欄INFORMATION COLUMN
摘要：本文先考慮深度優先搜索。深度優先搜索算法流程如下最后，將初始化為，初始化，和分別初始化為適當的全零數組，然后調用到最終退出后所得到的即為所求結果。
目錄
????????本題是要找最長路徑，應該廣度優先搜索和深度優先搜索都可以。本文先考慮深度優先搜索。
????????本題與以前的類似的題目的區別在于約束條件的不同，比如說之前有類似的題目的約束條件是不能重復通過一條邊，或者路線不能交叉，等等。本題的約束條件是在同一條直線上不能移動兩次。因此在深度優先搜索過程中需要記錄當前搜索路徑中每條直線上已經移動過的次數，并結合邊界條件下來確定從當前位置出發的下一步可能的移動方向。
????????移動網格如上圖所示，以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那樣的傳遞的話，由于沒有更新當前遞歸層次的值，所以就不需要還原處理。
??
# -*- 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)
? ? ? ? 運行速度有點差強人意。
? ? ? ? 接下來看看用廣度優先搜索策略是不是能夠更快一些。
? ? ? ? 上一篇：Q48: 翻轉得到交錯排列
? ? ? ? 下一篇：Q50: 完美洗牌
????????本系列總目錄參見：程序員的算法趣題：詳細分析和Python全解
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/122172.html
摘要：且聽下回分解基于動態規劃策略的優化解法參見程序員的算法趣題偷懶的算盤上一篇程序員的算法趣題同數包夾程序員的算法趣題同數包夾本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 ??...
摘要：假設有幾個小朋友以相同間隔圍成圓周，要結對用紙杯電話相互通話。如果繩子交叉，很有可能會纏繞起來，所以結對的原則是不能讓繩子交叉。如下所示運行結果上一篇異或楊輝三角形下一篇禁止右轉本系列總目錄參見程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問...
摘要：可以在遍歷所有矩陣時，對各種出現的次數進行計數，最后計數值為的個數即為所求結果。上一篇排序交換次數的最少化排序交換次數的最少化本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 ...
摘要：能以最少交換次數到達升序有序排列記為的數列記為就等價于從代表的節點在這張圖中到達對應的節點的最短路徑長度。上一篇質數矩陣質數矩陣下一篇唯一的序列本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 ...
閱讀 3518·2023-04-25 17:35
閱讀 2594·2021-11-24 09:39
閱讀 2530·2021-10-18 13:32
閱讀 3416·2021-10-11 10:58
閱讀 1637·2021-09-26 09:55
閱讀 6152·2021-09-22 15:47
閱讀 967·2021-08-26 14:15
閱讀 3472·2019-08-30 15:55
