计算机仿真
計算機倣真
계산궤방진
COMPUTER SIMULATION
2007年
8期
171-173,208
,共4页
注水法%迷宫问题%最优路径
註水法%迷宮問題%最優路徑
주수법%미궁문제%최우로경
根据灌溉系统的工作原理,提出注水法算法应用于求解迷宫最优路径问题.设定迷宫为一个灌溉系统,水从迷宫的入口注入,通过迷宫的通路水从迷宫的出口流出.从入口注入的水沿通路流向各个方向,在通路的各个位置记忆水流到达的时间.当迷宫出口有水流到达时,从出口到入口根据记录在通路上的时间逐步减小的原则逆向寻找入口就可找到迷宫的所有最优路径.该算法的空间复杂度和时间复杂度同迷宫的规模成线性关系.实验结果显示该算法是一种求解迷宫问题的有效算法.
根據灌溉繫統的工作原理,提齣註水法算法應用于求解迷宮最優路徑問題.設定迷宮為一箇灌溉繫統,水從迷宮的入口註入,通過迷宮的通路水從迷宮的齣口流齣.從入口註入的水沿通路流嚮各箇方嚮,在通路的各箇位置記憶水流到達的時間.噹迷宮齣口有水流到達時,從齣口到入口根據記錄在通路上的時間逐步減小的原則逆嚮尋找入口就可找到迷宮的所有最優路徑.該算法的空間複雜度和時間複雜度同迷宮的規模成線性關繫.實驗結果顯示該算法是一種求解迷宮問題的有效算法.
근거관개계통적공작원리,제출주수법산법응용우구해미궁최우로경문제.설정미궁위일개관개계통,수종미궁적입구주입,통과미궁적통로수종미궁적출구류출.종입구주입적수연통로류향각개방향,재통로적각개위치기억수류도체적시간.당미궁출구유수류도체시,종출구도입구근거기록재통로상적시간축보감소적원칙역향심조입구취가조도미궁적소유최우로경.해산법적공간복잡도화시간복잡도동미궁적규모성선성관계.실험결과현시해산법시일충구해미궁문제적유효산법.