• •

### A*算法的代数表示

1. 1. 榆林学院数学与统计学院, 榆林 719000;
2. 西北工业大学航海学院, 西安 710072
• 收稿日期:2021-12-14 修回日期:2022-03-03 发布日期:2022-07-29
• 基金资助:
国家自然科学基金项目(11801496),陕西省自然科学基础研究计划重点项目(2021JZ-12),榆林市科技局项目(2019-89-4)资助课题

YAN Weijun, ZHANG Lijun, BI Dongyao. An Algebraic Approach to A* Algorithm[J]. Journal of Systems Science and Mathematical Sciences, 2022, 42(6): 1478-1489.

### An Algebraic Approach to A* Algorithm

YAN Weijun1, ZHANG Lijun2, BI Dongyao2

1. 1. School of Mathematic and Statistics, Yulin University Yulin 719000;
2. School of Marine Science and Technology, Northwestern Polytechnical University, Xi'an 710072
• Received:2021-12-14 Revised:2022-03-03 Published:2022-07-29
A*算法是一种基于图遍历的路径搜索算法,被广泛应用于人工智能的许多领域.文章基于矩阵半张量积理论研究了A*算法的矩阵表示.首先利用矩阵半张量积给出了一般搜索问题动态行为的代数表示.在新的表示方式下,得到了优化问题有解的充分必要条件.接着,给出了A*算法的代数表示.最后给出了一个数值例子来说明本文的理论结果.
The A* algorithm is a path search algorithm based on ergodic process of graph, and it is widely used in many fields of computer science. In this paper, the algebraic representation of the A* algorithm is studied based on the method of semitensor product of matrices. First, we give the algebraic representation of the dynamic behavior of the general search problem. By the new representation, the necessary and sufficient conditions for the search problem to be solvable are given. Next, the algebraic representation of the A* algorithm is proposed. Finally, a numerical example is presented to illustrate the theoretical results.

MR(2010)主题分类:

()
 [1] Hart P E, Nilsson N J, Raphael B.A formal basis for the heuristic determination of minimum cost paths.IEEE Trans.Syst.Sci.Cybernet, 1968, SSC-4(2):100-107.[2] Bell M.Hyperstar:A multi-path Astar algorithm for risk averse vehicle navigation.Transp.Res.B Methodol, 2009, 43:97-107.[3] Duchon F, Babinec A, Kajan M, et al.Path planning with modified A-Star algorithm for a mobile robot.Proced.Eng, 2014, 96:59-69.[4] Wang H F, Zhou J W, Zheng G F, et al.HAS:Hierarchical A-Star algorithm for big map navigation in special areas.5th International Conference on Digital Home, 2014, 222-225.[5] ElNimr A, Fagiar M, Mohamed Y.Two-way integration of 3D visualization and discrete event simulation for modeling mobile crane movement under dynamically changing site layout.Autom.Constr., 2016, 68:235-248.[6] Kesleman A, Ten S, Ghazali A, et al.Reinforcement learning with A* and a deep heuristic.https://arxiv.org/abs/1811.07745, 2018.[7] 程代展,齐洪胜.矩阵的半张量积-理论与应用.第二版.北京:科学出版社, 2011.(Cheng D Z, Qi H S.Semi-tensor Product of Matrices:Theory and Applications (2nd).Beijing:Science Press, 2011.)[8] Cheng D Z, Li C X, He F H.Observability of boolean networks via set controllability approach.Systems and Control Letters, 2018, 115:22-25.[9] Lu J Q, Li H T, Liu Y, et al.Survey on semi-tensor product method with its applications in logical networks and other finite-valued systems.IET Control Theory and Applications, 2017, 11(13):2040-2047.[10] Li H T, Liu Y N, Wang S L, et al.State feedback stabilization of large-scale logical control networks via network aggregation.IEEE Transactions on Automatic Control, 2021, 66(12):6033-6040.[11] Cheng D Z, Wu Y H, Zhao G D, et al.A comprehensive survey on STP approach to finite games.Journal of Systems Science and Complexity, 2021, 34(5):1666-1680.[12] Dechter R, Pearl J.Generalized best-first search strategies and the optimality of A*.Journal of the ACM, 1985, 32:505-536.[13] L^L.j YM.p:_n 7 y, 2012.(Dang J W.Artificial Intelligence.Beijing:Publishing House of Electronics Industry, 2012.)
 [1] 沈宇桐, 徐勇. 概率布尔网络的牵制鲁棒镇定[J]. 系统科学与数学, 2022, 42(6): 1454-1466. [2] 贾光钰，冯俊娥. 三种单节点摄动对混合值逻辑网络极限集的影响[J]. 系统科学与数学, 2016, 36(3): 426-436. [3] 程代展，刘挺，王元华. 博弈论中的矩阵方法[J]. 系统科学与数学, 2014, 34(11): 1291-1305. [4] 程代展，齐洪胜. 矩阵半张量积的基本原理与适用领域[J]. 系统科学与数学, 2012, 32(12): 1488-1496. [5] 程代展，赵寅，徐听听. 演化博弈与逻辑动态系统的优化控制[J]. 系统科学与数学, 2012, 32(10): 1226-1238.