补充资料：启发式搜索

启发式搜索
heuristic search

q一fQ sh一sousuo启发式搜索《heuristic search)一种利用与待求解问题有关的信息，即所谓启发信息，对搜索路径的走向给予一定约束或选择的搜索方法。 搜索方法的目标是要在与间题有关的状态空间或图表示中，根据已知的初始状态(起始节点)、目标状态(满足目标状态描述的节点)以及从一种状态(节点)转换到另一种状态(节点)所允许的操作或算符，寻找一条从初始状态达到目标状态的途径。绝大多数问题求解技术最终都归结为状态空间或图的搜索问题。 一般说来，不同的问题求解类型需要不同的搜索策略。根据问题求解的任务和问题本身所存在的解的情况，问题求解可分为三种类型。一是问题只有唯一解或有多个解，但它们均处于同等地位，不涉及寻找最优解。这类问题要求搜索方法尽可能地减少搜索次数并保证完全性，即问题存在解的话，搜索一定能成功并找到问题的解。定理证明所面临的就是这类问题。二是问题有多个解，问题求解的目的是寻求其最优解。在问题的规模不太大，复杂性不甚高的情况下，这是可以做到的，但对大多数这类问题来说，需利用某些启发信息以提高搜索效率。A‘和献)’等启发式搜索算法所要解决的就是这一类问题。第三类与第二类相似，但间题是NP难解的(参见Np完全性理论)。在现实的存储资源和时间条件下很难或根本得不到最优解。同时，对于诸如推销员旅行问题等具体应用，令人满意的解也并非一定要最优解。因而在求解这类问题时可以放弃最优解而研究各种更加实用有效的启发式搜索方法。 50年代末期，A.N~11，J.C.Sllaw和H.A.Sin五〕n开始研究启发式搜索。60年代中期以后，随着计算机，尤其是人工智能应用领域的不断扩大，NP难解性问题又长期得不到解决，因而启发式搜索的研究越来越引起人们的重视与兴趣，并且取得了一批引人瞩目的成果。如J.D〕ran和D.Michie以及N.J.Nill以)n的利用搜索估价函数引导搜索的方法，P.E.Hart，Nillsoll和B.Raphad的A‘算法，与或图上的启发式搜索AO‘算法以及各种博弈树搜索等。 启发式搜索的最大特点就是在搜索过程中使用与问题有关的启发信息来缩减搜索量，其一般过程如下: 步骤1建立只含有初始节点S的搜索图G，把S放人名为()PEN的未扩展节点表中; 步骤2建立扩展节点表口丈EEI)，C以)SED初始为空表; 步骤3若01〕EN为空表，则搜索失败并退出; 步骤4把OPEN表上的第一个节点n〔xle移人CL(〕SEI〕表; 步骤5若n浏e为目标节点，则搜索成功并退出。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。