CAJ | 학술논문

讨论了回溯算法的形式模型,提出了刻画回溯的一些数学概念,以隐式搜索为背景提出了状态空间概念,给出了分别以邻接方阵和邻接表形式表示的有向图所对应的状态空间,从而说明显式搜索是隐式搜索的特例,通过展开空间概念揭示了问题求解的不同要求所对应的不同数据结构,提出了通用回溯算法,并以N皇后问题、稳定婚姻问题、点着色问题、子集和数问题、跳马问题、最长路径问题和强连通分支问题等多种算法设计问题为例讨论了通用回溯算法的应用.该文结果有助于扩大回溯算法的使用范围,提高回溯算法实现的正确性和效率.
토론료회소산법적형식모형,제출료각화회소적일사수학개념,이은식수색위배경제출료상태공간개념,급출료분별이린접방진화린접표형식표시적유향도소대응적상태공간,종이설명현식수색시은식수색적특례,통과전개공간개념게시료문제구해적불동요구소대응적불동수거결구,제출료통용회소산법,병이N황후문제、은정혼인문제、점착색문제、자집화수문제、도마문제、최장로경문제화강련통분지문제등다충산법설계문제위례토론료통용회소산법적응용.해문결과유조우확대회소산법적사용범위,제고회소산법실현적정학성화효솔.