延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第第5 5章章 搜索求解策略搜索求解策略延边大学工学院计算机科学与技术学科延边大学工学院计算机科学与技术学科李永珍李永珍E_mail:E_mail:人工智能基础人工智能基础延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第5章 搜索求解策略5.1 5.1 搜索的概念搜索的概念5.2 5.2 状态空间的搜索策略状态空间的搜索策略5.3 5.3 盲目的图搜索策略盲目的图搜索策略5.4 5.4 启发式图搜索策略启发式图搜索策略5.5 5.5 与与/ /或图搜索策略或图搜索策略延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第第5 5章章 搜索求解策略搜索求解策略5.1 5.1 搜索的概念搜索的概念5.2 5.2 状态空间知识表示方法状态空间知识表示方法5.3 5.3 盲目的图搜索策略盲目的图搜索策略5.4 5.4 启发式图搜索策略启发式图搜索策略5.5 5.5 与与/ /或图搜索策略或图搜索策略延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.1 5.1 搜索的概念搜索的概念 n问题求解：问题的表示。 选择一种相对合适的求解方法。n问题求解的基本方法：搜索法、归约法、归结法、推理法及产生式等。延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.1 5.1 搜索的概念搜索的概念5.1.1 5.1.1 搜索的基本问题与主要过程搜索的基本问题与主要过程5.1.2 5.1.2 搜索策略搜索策略延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.1.1 5.1.1 搜索的基本问题与主要过程搜索的基本问题与主要过程 n搜索中需要解决的基本问题搜索中需要解决的基本问题：（1）是否一定能找到一个解。（2）是否终止运行或是否会陷入一个死循环。（3）找到的解是否是最佳解。（4）时间与空间复杂性如何。延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.1.1 5.1.1 搜索的基本问题与主要过程搜索的基本问题与主要过程n搜索的主要过程搜索的主要过程：(1) 从初始或目的状态出发，并将它作为当前状态。(2) 扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针 。(3) 检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索。 延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.1.2 5.1.2 搜索策略搜索策略1. 搜索方向搜索方向：(1) 数据驱动数据驱动：从初始状态出发的正向搜索。正向搜索正向搜索从问题给出的条件（一个用于状态转换的操作算子集合）出发。 (2) 目的驱动目的驱动：从目的状态出发的逆向搜索。逆向搜索逆向搜索：先从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。(3) 双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.1.2 5.1.2 搜索策略搜索策略2. 2. 盲目搜索与启发式搜索盲目搜索与启发式搜索: :（1 1）盲盲目目搜搜索索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。 （2 2）启启发发式式搜搜索索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第第5 5章章 搜索求解策略搜索求解策略5.1 5.1 搜索的概念搜索的概念5.2 5.2 状态空间知识表示方法状态空间知识表示方法5.3 5.3 盲目的图搜索策略盲目的图搜索策略5.4 5.4 启发式图搜索策略启发式图搜索策略5.5 5.5 与与/ /或图搜索策略或图搜索策略延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.2 5.2 状态空间知识表示方法状态空间知识表示方法5.2.1 5.2.1 状态空间表示法状态空间表示法5.2.2 5.2.2 状态空间的图描述状态空间的图描述延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.2.1 5.2.1 状态空间表示法状态空间表示法n状态状态：表示系统状态、事实等叙述型知识的一组变量或数组：n操作操作：表示引起状态变化的过程型知识的一组关 系或函数：T延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.2.1 5.2.1 状态空间表示法状态空间表示法n状态空间状态空间：利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组： ：状态集合。 ：操作算子的集合。 ：包含问题的初始状态是 的非空子集。 ：若干具体状态或满足某些性质的路径信息描述。延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.2.1 5.2.1 状态空间表示法状态空间表示法n求解路径求解路径：从 结点到 结点的路径。 n状态空间的一个解状态空间的一个解：一个有限的操作算子序列。 ：状态空间的一个解。延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程n例例1 八数码问题的状态空间八数码问题的状态空间。 状态集 ：所有摆法操作算子：将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right5.2.1 5.2.1 状态空间表示法状态空间表示法延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.2.2 5.2.2 状态空间的图描述状态空间的图描述（状态）（操作算子）状态空间的有向图描述状态空间的有向图描述延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.2.2 5.2.2 状态空间的图描述状态空间的图描述八数码状态空间图八数码状态空间图 延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.2.2 5.2.2 状态空间的图描述状态空间的图描述 例例2 旅旅行行商商问问题题（traveling salesman problem, TSP）或邮递员路径问题。）或邮递员路径问题。 （家）（单位：km）可能路径：费用为375的路径（A，B，C，D，E，A） 延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.2.2 5.2.2 状态空间的图描述状态空间的图描述 旅行推销员状态空间图（部分） ABCDEA 375 A A A A B B C C C C D D D D A E E E E E E E D 路径: 路径: 路径: 路径: ABCEDA ABDCE ABDECA 费用: 费用 : 费用: 费用: 425 525 475 525 475 375 325 400 400 300 275 275 250 225 150 100 75 125 175 225 250 100 175 225 425 . . . . . . . 延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第第5 5章章 搜索求解策略搜索求解策略5.1 5.1 搜索的概念搜索的概念5.2 5.2 状态空间知识表示方法状态空间知识表示方法5.3 5.3 盲目的图搜索策略盲目的图搜索策略5.4 5.4 启发式图搜索策略启发式图搜索策略5.5 5.5 与与/ /或图搜索策略或图搜索策略延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.3 5.3 盲目的图搜索策略盲目的图搜索策略5.3.1 5.3.1 回溯策略回溯策略5.3.2 5.3.2 宽度优先搜索策略宽度优先搜索策略5.3.3 5.3.3 深度优先搜索策略深度优先搜索策略延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程5.3.1 5.3.1 回溯策略回溯策略n 带回溯策略的搜索带回溯策略的搜索：从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或“不可解结点”，即“死胡同”为止。若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。延边大学工学院计算机科学与技术系病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程n递归过程递归过程：Step Track (DataList)：Data：= First(DataList);if Member(Data, Tail(DataList) then return FAIL; *回老路退回if Goal(Data) then return NIL; *达到目的地成功返回if DeadEnd(Data) then return FAIL; *达到不合理状态，退出if Length(DataList) Bound then return FAIL; *已到深度限制，退回Rules：= AppRules(Data); *得出可应用的规则集Loop：if Null(Rules) then return FAIL; *进入死胡同，退回R：= First(Rules); *取出第一条可用规则Rules：= Tail(Rules); Newdata：= Gen(R,Data); *运用规则，生成新状态NewDataList：= Cons(Newdata, DataList);Path：= Back Track(NewDataList); *递归If Path：= FAIL then go loop else return Cons(R, Pa