基于Prim算法的迷宫生成问题及路径规划算法的对比研究

打开文本图片集

中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2025）23-0069-08

Abstract： This paper focuses on the performance comparison of maze generation and path planing algorithms based on Prim's algorithm.By constructing maze environments of different scales，the path finding effciency of BFS，DFS， A* ，Dijkstra andRandom Walkalgorithmsissystematicallyanalyzed.Theexperimentquantitativelyevaluates thefourdimensionsoftime out of the maze， success rate， path steps and exploration effciency. It is found that A* and Dijkstra are stable in path optimality， and A* greatlyimproves thesearch effciency with the helpofheuristic function.BFS strictly guarantes the shortest path but consumesalotofspace.DFSperforms thefastest，butthepathlengthislonger than theoptimalsolution.Random Walk'ssuccess rate in large-scale mazes is less than 20% ，and is onlyapplicable to benchmarkcontrols.The adaptabilityof thealgorithm is further verified by memory and generalization experiments.The results show that A* has the best generalization ability in unfamiliarenvironments，andDijkstrais ireplaceableintheglobaloptimalsolutionscenario.Thisstudyprovidesabasis for algorithmselectioninthefeldsofrobotnavigation，gameAI，andotherfelds.Andproposesanotimizationdirectionforthe integrationof taditionalalgorithmsanddeepreinforcementlearning，whichhastheoreticalandengineering practicalvalue for path planning in resource-constrained environments.

Keywords： Artificial Intelligence; algorithm; maze generation; path planning; performance comparison

0 引言

在我国，迷宫生成与路径规划算法的研究领域已展现出显著的研究优势。（剩余9020字）