文献类型：期刊文章

作　　者：王岩冰[1] 郑明春[2] 刘弘[2]

机构地区：[1]山东科技大学电子工程系,济南250031 [2]山东师范大学计算机科学系,济南250014

出　　处：《计算机研究与发展》

基　　金：国家自然科学资金资助 ( 6 9975 0 10 )

年　　份：2001

卷　　号：38

期　　号：9

起止页码：1066-1079

语　　种：中文

收录情况：AJ、BDHX、BDHX2000、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：讨论了回溯算法的形式模型 ,提出了刻画回溯的一些数学概念 ,以隐式搜索为背景提出了状态空间概念 ,给出了分别以邻接方阵和邻接表形式表示的有向图所对应的状态空间 ,从而说明显式搜索是隐式搜索的特例 ,通过展开空间概念揭示了问题求解的不同要求所对应的不同数据结构 ,提出了通用回溯算法 ,并以 N皇后问题、稳定婚姻问题、点着色问题、子集和数问题、跳马问题、最长路径问题和强连通分支问题等多种算法设计问题为例讨论了通用回溯算法的应用 .该文结果有助于扩大回溯算法的使用范围 ,提高回溯算法实现的正确性和效率 .

关 键 词：状态空间  回溯算法  形式模型  人工智能

分 类 号：TP18]