摘要
提出了基于蚁群算法求解迷宫最优路径的算法。设定两组蚂蚁分别分布在迷宫中距离入口、出口路径长度为k的前沿位置,根据移动规则,相向爬行。迷宫中各位置记忆蚂蚁信息素量和至迷宫入口、出口的路径长度。蚂蚁爬行至一新位置后,根据当前位置的信息而修改周边位置至入口或出口的路径长度,从而形成一条宽度为3的路径信息带。蚁群在迷宫中爬行使得迷宫中记忆了大量的路径信息,从而容易实现两段路径的拼接,提高了蚂蚁寻找到达目的地最优路径的效率。不同规模迷宫的试验结果显示,该算法是一种求解迷宫最优路径问题的有效解法。
An algorithm based on ant colony algorithm was proposed to solve the maze problem. The ant colony is divided into two sub-colonies. Starting at a distance of k away from the entrance and the exit, the colonies crawl forward oppositely according to the given rules. Each ant moves on the maze and updates the distance information between the neighbor points and the entrance or exit by referring to the information of the current position. Thus an information way with three band widths is formed. In this algorithm, with the crawling of the colonies, plenty routing information was established, and new optimal paths can be formed by crossing two exsitent ones, and thus enhance the algorithm optimization performance. The results of experiments to the different scale mazes demonstrate that this algorithm is an effective solution to solve maze problem.
出处
《青岛大学学报（自然科学版）》
CAS
2008年第1期61-65,共5页
Journal of Qingdao University(Natural Science Edition)
关键词
蚁群算法
迷宫问题
最优路径
ant colony algorithm
maze problem
optimal path
