人工智能 搜索问题

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

第 1 章1. 2. 3. 4. 5. 6. 7. 8.

搜索问题

什么是状态空间？ 回溯策略。 图搜索策略 无信息的图搜索策略 启发式图搜索策略 A*算法。 A*算法的性质。 搜索算法的讨论。

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

状态空间 1. 计算机对传统的问题求解方法带来了根本性的 改变。 传统方法， 由专家给出公式， 使用者 的任务是理解公式， 应用公式。 有些问题用传统方法描述很困难, 例如本节的 几个例子 公式的推导需要很高的水平， 与实际 问题相差较远，对应用者要求很高。 2. 计算机利用自己强大的计算能力和存储能力, 采用”猜”的方式, 试探法. 能解决问题的领 域更广, 更结合实际.

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

例 智力游戏问题：传教士与野人渡河问题 传教士与野人渡河问题：有 3 个传教士带 3 个野 人渡河，河的岸边有一条船， 每次最多可载 2 人， 要求无论在河的哪一边，野人的数目不能超过传教 士的数目，问为安全起见， 应如何安排传教士与 野人渡河？ 一种较为简单的表示方式3 元向量(x, y, z) x: 河此岸的传教士数， y: 河此岸的野人数。 x,y 取值范围{0,1,2,3} z: 船在此岸，z取值范围{0,1}

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

初始状态： (3,3,1) 目标状态： (0,0,0)例 设有 8 数码难题如下:在 3×3 的框架中有 8 个标有 数字的硬纸片， 这些硬纸片上标的数字分别是 1, 2, …, 8, 每个纸片都可以移进相邻的空格， 8 数码难 题的初始状态和目标状态分别列出如下，问如何把这个问 题由初始状态移向目标状态？ 2 8 3 1 6 4 5 7 初始状态Initial 1 2 3 4 8 7 6 5 目标状态 Goal

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

对于8 数码难题， 我们选用直接的矩阵描述，解题过程 中的任何一个中间情况都对应一个 3*3的矩阵， 用0,1, 2,…, 8这9个数的一个排列依次去充填这个矩阵的各个单 元,就是求解问题的一个可能的情况, 共有 9!种。

8 数码难题(8-puzzle)的矩阵描述 2 8 3 1 6 4 5 7 Initial Goal 1 2 3 4 8 7 6 5

教师讲得人工智能课件,觉得课件很好

人工智能7

吉林大学珠海学院计算机科学与技术系1 4 3 6

5 8 2

1

3

1 4 3 7 6 5 8 2

1 2 3 7 8 6 5 2

1 2 3 7 6 5 8 2

7 4 6 5 8 2

1 3 7 4 6 5 8 2

1 3 7 4 6 5 8 2

1 4 3 1 7 6 5 8 2

1 4 3 5 7 6 8 2

1 4 3 7 8 6 5 2

1 4 3 7 8 6 5 2

1 4 3 7 6 3 5 8 2

1 4 3 7 6 2 5 8

教师讲得人工智能课件,觉得课件很好

人工智能 例 旅行推销员问题 75 125 100 125 50 D

吉林大学珠海学院计算机科学与技术系

A 100 B 125 125 75 50 100 C

E

问题表示, 形式为(A****)的字符串和(A****A)的字符串。 其中****为B,C, D, E 的排列. 问题的节，形式为(A****A)的

字符串, 其中****为B,C, D, E 的排列.

教师讲得人工智能课件,觉得课件很好

人工智能旅行推销员问题的搜索空间

吉林大学珠海学院计算机科学与技术系

A 100 B 150 C 175 D 225 125 C 100 D 75

E

250 275 D E C 300 325 D E E 375 425 A A A E

教师讲得人工智能课件,觉得课件很好

人工智能 1.1 回溯策略

吉林大学珠海学院计算机科学与技术系

回溯策略的主要思想: 只保留从初始状态到当前状态的 一条解路径, 给变换状态的规则给出一个排序方法, 对当前状 态使用规则产生新的状态, 不断地向前延伸解路径. 当没有规 则可用, 或向前延伸的状态都是无解状态(称为死点,deadend) 时, 沿解路径后退到前一个状态(回溯), 重新开始搜索, 直至找 到解或宣布失败. 回溯策略是一种穷尽的搜索方法.

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

2.1 回溯算法Backtracking Strategies 递归过程A simple recursive procedure 输入: 问题的初始状态. . The input: the initial state. 输出:一个规则表. 应用这个规则表可以把初始状态变为 目标状态. 否则回答FAIL. The output of the procedure, a list of rules, using it we can get the goal from the initial state. If the procedure can not find the solution, it return FAIL. Recursive procedure BACKTRCK(DATA) 1 if TERM(DATA), return NIL; 2 if DEADEND(DATA), return FAIL; 3 RULES ← APPRULES(DATA);

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

4 LOOP: if NULL(RULES), return FAIL; 5 R ← FIRST(RULES); 6 RULES ← TAIL(RULES); 7 RDATA ← R(DATA); 8 PATH ←BACKTRACK( RDATA); 9 if PATH = FAIL , go LOOP; 10 return CONS( R, PATH)

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

In step 3, after get the list of rules using the function APPRULES, we need to order the rules in the lists. The ordering is very important. If the “better” rule is put in the front of the list, it can be used firstly, the efficiency of the system is high. If the “worse” rule is put in the front, the system needs to try more rules, the efficiency of the system is poor. The Example of Backtracking procedure. The 4 queen problem

* * *

在利用APPRUKES 得到规则表之 后, 需要对表中的规则排序, 把好 的规则放在表的前面优先使用, 这 个排序对算法的效率有很大影响.

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

The problem representation the global database: 4*4 array the rule: Rij If i= 1 : there are no queen in the array 1 < i<= 4: There is a queen in the row i-1 then put a queen in the row i, column j We order the rules according to the column. 我们用Rij表示在棋盘的第 i 行第 j 列放一个王后. 按行的增 加顺序依次放皇后, 在规则的排序上依列的上升次序排序. Termination condition: there are 4 queens in the chess board, they can not kill each other. 终止条件: 4 皇后都放到棋盘上, 且不能互相杀死.

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学

与技术系

Order of rules: R11, R12, R13, R14(R12,R24,R31,R43) R21, R22, R23,R24 (R24,R31,R43)

deadend deadend deadend deadend (R31,R43)

deadend

deadend

deadend

deadend

(R43)

deadend deadend There many backtrack NIL ()

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

We can use more informed rule ordering using function diag(i,j) 我们可以采用含有较多信息的函数diag(i,j) . Diag(i,j) = the length of the longest diagonal passing through cell(i,j) diag(i,j) 是通过单元(i, j)的最长对角线的长度, 我们按diag(i,j)排序, we order Rmn before Rij, if diag(m,n) < diag(i,j) Rin before Rij, If diag(i,n) = diag(i,j) and n<j Homework: Solve the 4 queens problem by using backtracking procedure and function diag BACKTRACK1: to avoid cycle 1. The argument of the procedure is changed, from a single state to a list of state. 2. Use MEMBER function to check cycle. 3. Add depth bound

教师讲得人工智能课件,觉得课件很好

人工智能2.1

吉林大学珠海学院计算机科学与技术系

Backtracking Strategies A simple recursive procedure The input of the procedure, DATA : the initial state. The output of the procedure, a list of rules, using it we can get the goal from the initial state. If the procedure can not find the solution, it return FAIL.

Recursive procedure BACKTRCK(DATALIST) 1 DATA ← FIRST(DATALIST); 2 if MEMBER(DATA, TAIL(DATALIST)), return FAIL; 3 if TERM(DATA), return NIL; 4 if DEADEND(DATA), return FAIL; 5 if LENGTH(DATALIST) > BOUND, return FAIL; 6 RULES ← APPRULES(DATA);

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

7 LOOP: if NULL(RULES), return FAIL; 8 R ← FIRST(RULES); 9 RULES ← TAIL(RULES); 10 RDATA ← R(DATA); 11 RDATALIST ←CONS( RDATA, DATALIST); 12 PATH ←BACKTRACK( RDATALIST); 13 if PATH = FAIL , go LOOP; 14 return CONS( R, PATH)

教师讲得人工智能课件,觉得课件很好

人工智能 1.2

吉林大学珠海学院计算机科学与技术系

图搜索策略graph-search strategies graphgraph

回溯算法只包含一条探索路径, 如果发现 deadend节点或无规则可用时要退回来, 因此可能产 生把探索过的节点擦掉后又重新产生的现象. 在图搜索算法中.将所有搜索过的状态用一个图(搜 索图)记录下来, 图的弧反映状态之间的关系.在图 中选择节点加以扩展, 直至把搜索图扩展到充分大, 包含解路径在内.

教师讲得人工智能课件,觉得课件很好

人工智能

吉林大学珠海学院计算机科学与技术系

The main idea of graph searchIn the backtracking procedure, we preserve only a path from the initial state to the current state, so sometimes we need to product some states again after the states were removed. However, in graph search method, We preserve a graph in the memory, the graph include all the states we passed through and the relation of their sequences. When we find some node(state) in the graph is suited to expand for search, we expand it, continue our searching, until a solution is finded.

本文来源：https://www.bwwdw.com/article/8uji.html