回溯算法的形式模型

FORMAL MODEL OF BACKTRACKING ALGORITHMS

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

In this paper the formal model of a backtracking algorithm is discussed, and the mathematical concepts for describing backtracking are presented. The concept of state space is given to describe implicit searching, and the corresponding state spaces of directed graph represented by adjacency table and contiguous list respectively are given to get the result that explicit searching are special cases of implicit searching. The concept of expansive space is presented to depict different data structures corresponding to different objects of problem solving. Several general backtracking algorithms are given and their applications in various algorithm design problems such as N queens problem, stable marriage problem, node coloring problem, subset-with-given-sum problem, knight's tour problem, longest path problem, and strong-connected component problem, are all discussed. The results help to promote the application of backtracking algorithms with reliability and efficiency.