Abstract: Due to the large number of products in large supermarkets and the complex space environment, customers often spend a lot of time shopping to find the purchase of goods. In response to this problem, the genetic & modified A* algorithm is proposed to help customers find a shortest path to the desired purchase. First, the matrix is used to model the spatial layout of the supermarket. Then, the shortest path between any two commodities can be found by using the modified A* algorithm. Next, according to the customer’s shopping list a shortest path can be optimized by genetic algorithm, which includes the supermarket entrance, the shopping list, and the supermarket exit. Finally, the simulation results show that in a large supermarket with multiple floors, the more different commodities the customer purchases, the better optimization ability the genetic & modified A* algorithm has, the better quality of solution is, the shorter running time is required, which can efficiently solve the shortest path planning problem.

Key words: supermarket shopping guide, environmental modeling, genetic &, modified A* algorithm

摘要： 大型超市内商品数目繁多，空间环境复杂，顾客在购物的过程中往往需要耗费大量的时间来寻找所需购买的商品。针对这一问题，提出了遗传-改进A*算法来帮助顾客找到一条通往所需购买商品的最短路径。首先利用矩阵对超市的空间环境进行建模，然后通过改进A*算法找到任意两个商品之间的最短路径，再根据顾客的购物列表利用遗传算法优化生成一条包含超市入口，购物列表上的商品以及超市出口的最短路径。最后仿真实验表明，在多楼层的大型超市里，顾客购买多个不同商品时，遗传-改进A*算法寻优能力更强，求解质量更优，并且运行时间更短，能够高效地解决最短路径规划问题。

关键词: 超市导购, 环境建模, 遗传-改进A*算法