搜索的概念：从初始结点出发沿着与之相连的边试探地前进，寻找目标结点的过程。搜索过程中所经过的结点和边所形成的连接关系，便形成一个树型有向图，称为搜索树。搜索算法很多有爬山法(Hill Climbing),回溯法(backtracking),宽度（广度）优先法(Breadth-First),深度优先法（Depth-first），分支界限法（Branch and Bound），大英博物馆法（British Museum）,最佳图搜索法（A*），启发式搜索法（Heuristic）等，可参阅有关资料。

1.回溯搜索（Backtracking search） 无向导的搜索，从初始结点出发，沿连接边逐一考察各个结点,看是否为目标结点，如不是则对当前结点进行扩展，但当不能再扩展时，则退回一个结点，然后再扩展另一条边。这样，要么最终找到目标结点，搜索成功，要么一直回溯到初试结点也未找到目标结点，则搜索失败。搜索算法（Search Algorithm）建立两个表open表，closed表

Node-id parent_no open表：记录待考察的结点 Node_no Node_id parent_no closed表：记录考察过的结点

算法的自然语言描述（只与closed表有关）：(1)将初始结点S0放入closed表中；(2)令Node_id=S0;(3)若Node_id=Sg，则搜索成功，结束；(4)若Node_id不可扩展，则移出closed表中末端结点Node_id_end，若Node_id_end=S0，则搜索失败，exit。否则令Node_id=Node_id_end,转步骤(4)；(5)扩展Node_id，选取其一个没在closed表中出现过的子结点Node_id_1放入closed表中，令Node_id=Node_id_1，转步骤3。利用回溯搜索解决4皇后问题：

.

(初始结点)步骤1：(0,0)→放置成功

.

步骤3：[2][0]→放置失败；（同列中已有1个皇后）[2][1]→放置失败；（右上角已有1个皇后）[2][2]→放置失败；（同列中已有1个皇后）[2][3]→放置失败；（左上角已有1个皇后）

.

步骤6：[2][0]→放置失败；（同列中已有1个皇后）[2][1]→放置成功

.

结点NODE[2][1][2][2],[2][3]均不能放置,所以在该层只扩展成一个结点!步骤7：[3][0]→放置失败；（同列或右上角中已有1个皇后）[3][1]→放置失败；（同列中已有1个皇后）[3][2]→放置失败；（左上角已有1个皇后）[3][3]→放置失败；（同列中已有1个皇后）

.

扩展失败!从closed表中移出结点NODE[1][3](即删除)步骤10：第三行无法放置任何皇后，所以回到上一层[1][3]位置往下讨论,但若[1][3]不放置皇后的话,则该层放置失败,所以再回溯到上一层[0][0]即其始位置开始讨论。

.

步骤12：[1][0]→放置失败（右上角已经有皇后）[1][1]→放置失败（同列已经有皇后）[1][2]→放置失败（左上角已经有皇后）[1][3]→放置成功

.

步骤13：[2][0]→放置成功[2][1]→放置失败[2][2]→放置失败[2][3]→放置失败

.