【記錄】批處理實現dfs,bfs,雙向bfs,A*尋路

2019-11-10 17:57:31

字體：大中小

來源：轉載

供稿：網友

演示程序鏈接：http://pan.baidu.com/s/1hrMy7Qk 密碼：3hhy

:: dfs By blackkitty:: 算法描述：深搜set xx_0=0 && set yy_0=-1set xx_1=1 && set yy_1=0set xx_2=0 && set yy_2=1set xx_3=-1 && set yy_3=0set x=%current_x% && set y=%current_y%set flag=0call:dfs %x% %y% 0goto:eof:dfs:: <x> <y>if "%1_%2" EQU "%end_x%_%end_y%" (set flag=1 && goto:eof)set dic_%3=0:dfs_loop1set tmp=!dic_%3!set/a dfs=%3+1set/a nx=%1+!xx_%tmp%!set/a ny=%2+!yy_%tmp%!if !vis_%nx%_%ny%! EQU 0 ( if !%map%_%nx%_%ny%! EQU 1 ( call go %nx% %ny% call:dfs %nx% %ny% %dfs% ))if %flag% EQU 1 (goto:eof)set/a dic_%3+=1if !dic_%3! LSS 4 (goto dfs_loop1)goto:eof:: dbfs By blackkitty:: 算法描述：逆向廣搜set xx_0=0&&set yy_0=-1set xx_1=1&&set yy_1=0set xx_2=0&&set yy_2=1set xx_3=-1&&set yy_3=0set l=0set r=1set x0=%end_x%set y0=%end_y%set nxt_%end_x%_%end_y%=0:rbfsset x=!x%l%!set y=!y%l%!:: 在地圖上顯示標記（x,y），演示搜索過程:: call:mark %x% %y% .set/a l+=1if "%x%_%y%" EQU "%start_x%_%start_y%" (goto rush)for /l %%i in (0,1,3) do ( set/a nx=x+!xx_%%i! set/a ny=y+!yy_%%i! set/a val=%map%_!nx!_!ny! if "!val!" EQU "1" ( if not defined nxt_!nx!_!ny! ( set nxt_!nx!_!ny!=!x!_!y! set x!r!=!nx! set y!r!=!ny! set/a r+=1 ) ))goto rbfs:rushset vv=!nxt_%start_x%_%start_y%!:rush_loopif "%vv%" EQU "0" (goto:eof)call go %vv:_= %set vv=!nxt_%vv%!goto rush_loop:mark:: <x> <y> 在地圖上顯示標記（x,y），用來演示搜索過程set/a _x=%1*2+%maze_x% && set/a _y=%2+%maze_y%cc %_x% %_y% && echo.%~3goto:eof

BFS

:: dbfs By blackkitty:: 算法描述：雙向廣搜set xx_0=0&&set yy_0=-1set xx_1=1&&set yy_1=0set xx_2=0&&set yy_2=1set xx_3=-1&&set yy_3=0set l=0set r=2set x0=%start_x%set y0=%start_y%set v%start_x%_%start_y%=PReset pre_%start_x%_%start_y%=0set x1=%end_x%set y1=%end_y%set v%end_x%_%end_y%=nxtset nxt_%end_x%_%end_y%=0:dbfsset x=!x%l%!set y=!y%l%!:: 在地圖上顯示標記（x,y），演示搜索過程:: call:mark %x% %y% .set v=!v%x%_%y%!set/a l+=1set/a i=0:loopset/a nx=%x%+!xx_%i%!set/a ny=%y%+!yy_%i%!if "!%map%_%nx%_%ny%!" EQU "1" (:: 若臨塊為路 if "!v%nx%_%ny%!" NEQ "%v%" ( :: 若臨塊的標記與本塊不同 if defined v%nx%_%ny% ( ::找到通路 if "%v%" EQU "pre" ( call:rush %x% %y% %nx% %ny% ) else ( call:rush %nx% %ny% %x% %y% ) goto:eof ) :: 若臨塊的標記與本塊不同，且臨塊無標記 set %v%_%nx%_%ny%=%x%_%y% set x%r%=%nx%&&set y%r%=%ny%&&set v%nx%_%ny%=%v% set/a r+=1 ))set/a i+=1&&if "!i!" NEQ "4" (goto loop)goto dbfs:rushset vv=%1_%2:rvs_loopif "!pre_%vv%!" EQU "0" (goto rvs_lopp_end)set nxt_!pre_%vv%!=%vv%set vv=!pre_%vv%!goto rvs_loop:rvs_lopp_endset nxt_%1_%2=%3_%4set vv=!nxt_%start_x%_%start_y%!:rush_loopif "%vv%" EQU "0" (goto:eof)call go %vv:_= %set vv=!nxt_%vv%!goto rush_loop:mark:: <x> <y> 在地圖上顯示標記（x,y），用來演示搜索過程set/a _x=%1*2+%maze_x% && set/a _y=%2+%maze_y%cc %_x% %_y% && echo.%~3goto:eof

DBFS

:: astar By blackkitty:: 算法描述：逆向啟發式A*set xx_0=0&&set yy_0=-1set xx_1=1&&set yy_1=0set xx_2=0&&set yy_2=1set xx_3=-1&&set yy_3=0set new=1set x0=%end_x%set y0=%end_y%set nxt_%end_x%_%end_y%=0set gn0=0set fn0=0set list=n0set/a maxfn=!%map%_width!*!%map%_height!:astarset vv=_set minfn=%maxfn%:: 從列表選取fn最小的位置for %%k in (%list%) do ( if !f%%k! LSS !minfn! ( set minfn=!f%%k! set vv=%%k )):: 從列表中刪除這個位置set list=!list:%vv%=!set vv=%vv:~1%set x=!x%vv%!set y=!y%vv%!:: 在地圖上顯示標記（x,y），演示搜索過程call:mark %x% %y% .if "%x%_%y%" EQU "%start_x%_%start_y%" (goto rush)for /l %%i in (0,1,3) do ( set/a nx=x+!xx_%%i! set/a ny=y+!yy_%%i! set/a val=%map%_!nx!_!ny! if "!val!" EQU "1" ( if not defined nxt_!nx!_!ny! ( set nxt_!nx!_!ny!=!x!_!y! :: 加入列表 set list=!list! n!new! :: 計算gn set/a gn!new!=!gn%vv%!+1 :: 計算fn保存至fn!new! call:fn !nx! !ny! gn!new! fn!new! set x!new!=!nx! set y!new!=!ny! set/a new+=1 ) ))goto astar:rushpause>nulset vv=!nxt_%start_x%_%start_y%!:rush_loopif "%vv%" EQU "0" (goto:eof)call go %vv:_= %set vv=!nxt_%vv%!goto rush_loop:fn:: <x> <y> [gn] [ret] 起點到x，y的估計代價（fn = gn + hn）:: gn 終點到(x,y)的實際代價:: hn 起點到(x,y)的估計代價，估值為起點到(x,y)的曼哈頓距離set/a tmp=%1-%start_x%if %tmp% LSS 0 (set/a tmp=-tmp)set %4=%tmp%set/a tmp=%2-%start_y%if %tmp% LSS 0 (set/a tmp=-tmp)set/a %4=!%4!+%tmp%+!%3!goto:eof:mark:: <x> <y> 在地圖上顯示標記（x,y），用來演示搜索過程set/a _x=%1*2+%maze_x% && set/a _y=%2+%maze_y%cc %_x% %_y% && echo.%~3goto:eof

astar