A^(*)算法的代数表示  

An Algebraic Approach to A^(*) Algorithm

作　　者：延卫军 张利军[2] 毕冬瑶 YAN Weijun;ZHANG Lijun;BI Dongyao(School of Mathematic and Statistics,Yulin University Yulin 719000;School of Marine Science and Technology,Northwestern Polytechnical University,Xi'an 710072)

机构地区：[1]榆林学院数学与统计学院,榆林719000 [2]西北工业大学航海学院,西安710072

出　　处：《系统科学与数学》2022年第6期1478-1489,共12页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金项目(11801496);陕西省自然科学基础研究计划重点项目(2021JZ-12);榆林市科技局项目(2019-89-4)资助课题。

摘　　要：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.

关 键 词：A^(*)算法 代数表示 矩阵半张量积 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]