AI-问题求解

《AI-问题求解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、AI:问题求解基本理论与方法内容提要搜索的定义具体问题的形式化盲信息搜索有信息搜索/启发式搜索优化问题的搜索算法联机/在线搜索搜索的定义三国华容道找出：一个移动序列，放出曹操Introducedin1878bySamLoyd,whodubbedhimself“America’sgreatestpuzzle-expert”类似游戏：数码（8，15，…,n2-1,…)12345678121511141013956784321....121411151013956784321121511141013956

2、784321?=$1000三国华容道不同的初始布局编程求解三国华容道状态：每个“局面”行动：可行的“移动”实现问题：如何在计算机内表示“状态”和“行动”定义一个“搜索”问题StatespaceSSuccessorfunction:xSSUCCESSORS(x)2SInitialstates0Goaltest:xSGOAL?(x)=TorFArccost，路径耗散S132StatespaceS==〉Stategraph每个节点表示一个状态弧及其两个端点表示后继函数可能包括多个不连通的分量搜

3、索问题的“解”IG解：从初始节点“I”到任何目标节点“G”的一条路径（沿箭头方向）解是路径，可能存在多条从I到G的路径，最优解就是路径耗散(路径上cost之和）最小的路径最短路径问题？搜索问题的“解”无解解就是连通源点和目标点的路径IG构建好的状态空间问题状态定义状态数目8-数码每个格子放置一个数9！=362,88015-数码每个格子放置一个数16!~2.09x101324-数码每个格子放置一个数25!~1025八皇后问题每行放一个皇后88N皇后问题每行放一个皇后NNN皇后问题任何一个位置都可以放一

4、个皇后(N2)!/(N2-N+1)!存在大量“不可达/违背约束”的状态！n2-1数码问题的状态空间逆序值（每个数被逆序的次数之和）的奇偶性，将整个状态图分为两个不联通的分量所以SamLoyd不用担心他的钱被领走！！！121411151013956784321121511141013956784321?121511146139510784321n2=0n3=0n4=0n5=0n6=0n7=1n8=1n9=1n10=4n11=0n12=0n13=0n14=0n15=0逆序值=7如何证明?什么是“好的”

5、状态空间所有状态？所有“可达的”状态？“不可达”状态的判断，在无解时非常重要！状态数目：少，越少越好？最少？状态数目一般情形下，太多！（无法全部在计算机内表示出来<存储空间受限>，或者遍历一次<计算时间受限>）状态空间/状态图的设计和后继函数密切相关！数码问题的搜索时间8-puzzle362,880states15-puzzle2.09x1013states24-puzzle1025states100millionsstates/sec0.036sec~55hours>109years我们的搜

6、索问题是寻找一个“状态”迁移的序列，为什么搜索状态空间大小个状态就一定可以完成搜索任务？基准算法：搜索整个状态图图的宽度优先搜索算法生成树Searchtree我们关心的搜索算法仅仅搜索整个状态空间的一小部分相同点：(与基准算法比）算法大框架所有的解（可行+不可行）构成的集合不同点：从状态图中选择的子集S不一样S构成的状态图（弧）不一样，后继函数空间大小/解的数量为N，则搜索过的部分是log(N)的多项式函数获得状态空间/状态图后，执行“搜索”8皇后问题和n2-1数码问题的求解方法的异同！8皇后问题，

7、简单的解法就是在空棋盘上不停添加皇后，其解是“构造”出来，构造出一个状态，然后对状态进行目标测试，不同状态之间不迁移，相邻两次目标测试之间的“动作序列”是“后继函数”！(深度优先？）n2-1数码问题，求解过程是从初态出发，不停地在不同状态之间迁移，直到到达目标状态状态的解释事物可能的抽象表示，关键属性上相同，不重要细节的影响可以忽略不计比如棋盘的布局，棋子偏移1毫米，对布局/状态没有影响状态空间是离散的，有限或者无限后继函数的解释数独求解器的例子。每个状态可行的所有“行动”的集合函数的返回值，行动的

8、结果（后继状态）和行动的代价（cost）后继函数是算法设计的“关键”！最复杂的部分路径耗散/代价路径耗散/代价是沿着某条边/弧，转移到下一个状态，执行动作的代价（后继函数执行的代价），一般总是正数；数码问题，每移动一次，代价为1N皇后问题，每放置/撤回一个皇后，代价为1，从一个状态转移到下一个状态，花费的代价<=2N我们总是假设，任何一条边/弧的路径耗散/代价c总是大于等于某个正常数ε，即c>=ε>0Why？目标状态可以是一个被精确定义的状态可以是满足某些条件的状态可