成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

程序員的算法趣題Q49: 欲速則不達(dá)

BlackMass / 3423人閱讀

摘要:本文先考慮深度優(yōu)先搜索。深度優(yōu)先搜索算法流程如下最后,將初始化為,初始化,和分別初始化為適當(dāng)?shù)娜銛?shù)組,然后調(diào)用到最終退出后所得到的即為所求結(jié)果。

目錄

1. 問(wèn)題描述

2. 解題分析

3. 代碼及測(cè)試

4. 后記


1. 問(wèn)題描述

2. 解題分析

????????本題是要找最長(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)前遞歸層次的值,所以就不需要還原處理。

??

3. 代碼及測(cè)試

# -*- 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)

4. 后記

? ? ? ? 運(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

相關(guān)文章

  • 序員算法趣題Q54: 偷懶算盤(pán)

    摘要:且聽(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)題描述 ??...

    wangzy2019 評(píng)論0 收藏0
  • 序員算法趣題Q22: 不纏繞紙杯電話

    摘要:假設(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)...

    MoAir 評(píng)論0 收藏0
  • 序員算法趣題Q46: 唯一OX序列

    摘要:可以在遍歷所有矩陣時(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)題描述 ...

    y1chuan 評(píng)論0 收藏0
  • 序員算法趣題Q45: 排序交換次數(shù)最少化

    摘要:能以最少交換次數(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. 后記 ...

    flybywind 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<