人工智能与神经网络笔记3.ppt

《人工智能与神经网络笔记3.ppt》由会员分享，可在线阅读，更多相关《人工智能与神经网络笔记3.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、Lecture Notes on AI-NN Chapter 5Information Processing&UtilizationCategories of Information Processing -Problem-Solving -Game-Playing -Theorem-Proving -Logic-DeductionSection 5.1 Problem-Solving5-1 IntroductionDescription of a problem:Problem defining:the start-goal conditions Rule defining:a set of

2、 IF-THEN Strategy-finding:rule-application controllingExample The Water Jug ProblemInitial Base:There are 2 jugs,a 4-kilo jug and a 3-kilo jug.Neither has any measurement marks on it.Rule Base:(1)There is a pump that can be used to fill the jug with water,or (2)You can pour water from jug on the gro

3、und or into another jug.Question:How to get exactly 2-kilo of water into the 4-kilo jug?Representation and Solution:Kilos in 4-kilo jug kilos in 3-kilo jug 0 0 0 3 3 0 3 3 4 2 0 2 2 0R1R2R13R21R222R2It is clear that the Production System is suitable meansof representation for Problem-Solving.Procedu

4、re PRODUCTION1.DATA initial database2.Until DATA satisfies the termination condition,do:i)begin ii)select some rule,R,in the set of rules that can be applied to DATA iii)DATA result of applying R to DATA In most of AI applications,the information availableto the control strategy is usually not suffi

5、cient to permitselection of the most appropriate rule on every stage.The operation of AI production system can thus becharacterized as a SEARCH PROCESS in which rulesare tried until some sequence of them is found that produces a database satisfying the termination conditionFurther,if the database of

6、 the problem to be solved isrepresented by means of graph,the search is calledGRAPH-SEARCH.Procedure GRAPH-SEARCH1.Create a search graph,G,consisting sole of the start node,S.Put S on OPEN(OPEN:a list of nodes just generated but not examined yet).2.Create a list,CLOSED,that is initially empty.(CLOSE

7、D is a list of nodes examined already)3.LOOP:if OPEN is empty,exit with failure.4.Select the first node on OPEN,remove it from OPEN to CLOSED,Call it node n.5.Examine n:if n is a goal node,exit with success.The solution is obtained by tracing a path along the pointers from n back to S in G.6.Expand

8、n(Apply a rule to n),generating the set,M,of its successors that are not ancestors of n.Install these members of M as successors of n.7.Establish a pointer to n from these members of M that were not already on either OPEN or CLOSED.Add there members of M to OPEN.For each member of M that was already

9、 on OPEN or CLOSED,decide whether or not to redirect its pointer to n.For each member of M already on CLOSED,decide for each of its descendants in G whether or not to redirect its pointer.8.Reorder the list OPEN according to a certain rule.9.Go LOOPSNode on CLOSEDNode onOPEN1=n23546Pointersneed to b

10、eredirectedtoRedirection The crucial factor in search process is the ordering regulation that determines the fashion of the selectionof nodes for expansion next.The search efficiency is dependent on the utility ofproblem information in node selection.In accord with the utility of problem information

11、 innode selection,search strategy can be divided into:a)Blind Search,and b)Heuristic Search5-1-1 Blind Search on Tree1)Breadth-First Search Node ordering:FIFOProcedure BFS1.Put start node s on OPEN.Set pointer P=02.If OPEN=NIL,failure.3.Select the first node on OPEN.Put it on CLOSED,Call it node n.4

12、.If n=g,successful.The solution is obtained by tracing a path along the pointers from g to s in G.5.Expand n.If it has no successors,go to step 2.Or,generate all its successors,add them successively to the end on OPEN,and establish pointers from them to n;go to step 2.Example:BFS 1238 47652831647 51

13、=S46=g283164 7528316475 2831 4765283 641752345678910113435 36 37 38283 147652 318476528314 76528316 75419See Nilsson p.71 Fu p.37The shortest solution path4539442033 832641752836 4175 83214765283714 65 2318476523 18476528 14376528314576 2831 675428 1637548 3264175123 84765 2 368417528364 1752836741

14、58 32147652837146 583 26417540 41 42 4323418 7652 81437652831457 62 81637542 31867542831567 4 1628375421322223 2425262728293031Comments on BFS:It is guaranteed to find a optimal solution because ofits systematic search feature.The major weakness with BFS is its inability to use the information relat

15、ed to the problem and thusa)It requires a large memory to store the great number of the nodes;b)It require a great amount of work to examine the great number of the nodesc)As result,BFS has low efficiency of search.5-1-2 Depth First Search:Node Ordering:LIFOProcedure DFS1.Put start node s on OPEN.Se

16、t d(s)=0,P=02.If OPEN=NIL,F.3.Select the first node on OPEN.Put it on CLOSED.Call it node n.4.If n=g,S.5.If d(n)=d ,go to step 2.6.If n is not expandable,go to step 2.7.Expand node n,generating all its successors.Establish pointers from them to n.Let d(successor)=d(n)+1.Add them to the front on OPEN

17、 in any order,then go to step 2.BExample:DFS d =5 2831847652831647 51=S283164 7528316475 2831 4765283 64175234567891011283 147652 3765283714 76528314 765See Nilsson p.70 Fu p.42The solution pathB 832641751883 2641758632 41758 3264175121314151617 832148 321483 2148132 476519202122236 4175684175 23684

18、17523 68417564 17528 64317528364517 2836741 5283674 1528367415 2 3765283 652837146 52837 461528371465 1238 4765123784 658 4 23184765123 847652425262728293031Compared with BFS,DFS has the following features:1)If d is too small,the goal node may be missed,if too large,the greater amount of storage is

19、needed.2)DFS may find the goal faster than BFS,while the the solution path may not be the shortest one if there are more than one goal node.3)DFS can often be carried out using a reasonably small amount of storage.Bgg5-1-3 Informed(Heuristic)Search on Tree(1)General Remarks -The weakness in blind se

20、arch:ignoring the information associated with the problem in selecting node for expansion next.-Solution:Try to use the heuristic information in node ordering on OPEN-Heuristic Search.-The heuristic information is used in terms of Evaluation Function,f(.):f(n):node n Real number mapping nodes to the

21、ir promising values.For any node n on a tree,let g*(n)be the actual cost of a minimal cost path from s to n.h*(n)be the cost of minimal cost path from n to g.f*(n)=g*(n)+h*(n)be the cost of an optimal path from s to g constrained to going through n.Let againg be an estimation of g*,h be an estimatio

22、n of h*,andf(n)=g(n)+h(n)be an estimation of f*(n),which can be used as an evaluation function for ordering nodeson OPEN.Practically,g(n):the sum of the arc costs encountered while tracing the pointers from n to s.h(n):a function based on heuristic information from the problem,hence is called Heuris

23、tic Function.The practical regulation is If h(n)is very high,node n may be ignored;If h(n)is low,node n may be chosen to expand next.(2)Algorithm A and Algorithm A*on Tree Algorithm A is a special Tree-Search using evaluation function f(n)for ordering nodes on OPEN and always selecting for expansion

24、 the node with the lowest value of f(n).The key for Algorithm A is the settings of h and g:When h=0,g=d,it reduces to BFS;h=0,g=0,random search;h=1/d,g=0,DFS;hh*,the optimal path may be lost;hh*,some search may be redundant,but optimal path can be found.Algorithm A with h(n)h*(n),for all n,is Algori

25、thm A*.Thus BFS is Algorithm A*and A*can always find aminimal length path to a goal.Informed-ness of Algorithm A*:A1*:f1(n)=g1(n)+h1(n)A2*:f2(n)=g2(n)+h2(n)with h1(n)h*(n),h2(n)h2(n)h1(n)for all non-goal node n.Example of A*:8-Puzzle ProblemLet f(n)=g(n)+h(n)=d(n)+w(n)d(n):depth of node n on search

26、tree w(n):number of misplaced digits at node n2831842831647 5283164 7516475 2831 4765 283 14765765283 76528314 765 83 184214 23 2 3765714 65 1238 4765123784 658 4 23184765123 847651#0+4=42#3#4#6#7#8#12#13#14#15#26#27#1+5=61+3=41+5=62+3=52+3=52+4=63+3=63+4=73+2=53+4=74+1=55+0=513 out of 27Algorithm A

27、*with h(n)=w(n)is more informed thanBFS which uses h(n)=0.h(n)=w(n)is a lower bound on the exact number ofsteps needed to reach the goal,h*(n),hence it is anAlgorithm A*.However,w(n)does not provide good-enough estimateof h*(n).The information of“following order”is notutilized in w(n).A better estim

28、ate of h*(n)is h(n)=P(n)+3S(n)P(n):the sum of the absolute distances that a digit is from“home”;S(n):a sequence score,taking value 2,for each non-central digit not proper followed 1,if a digit in the center 0,for other digitsE.g.,for s=and g=,we have2164 87531238 4765P(s)=(3x1)+(3x2)+(1x3)+(1x0)=12

29、(1,2,5)(3,4,8)(6)(7)S(s)=8x2=16By using this h(n),we have f(n)=g(n)+P(n)+3S(n)with g(n)=d(n)and the above problem will find thesame optimal path but with fewer nodes expanded:2831842831647 5283164 7516475 2831 4765 283 14765765 28314 765 184 23 2 3765 1238 4765123784 658 4 23184765123 8476511 out of

30、 13Since 0 w(n)h*(n)P(n)+3S(n),the solution path found happens to be of minimal path,although we were not guaranteed of finding an optimal path.Summary:From the example above,we can see that the key in heuristic search is to determine the form of estimation function f(n)by utilizing heuristic inform

31、ation.As is seen,the crucial difference between blind search and heuristic search is the ordering regulation.In Heuristic search,the node with the smallest value ofevaluation function will be chosen to be expanded first.(3)Algorithm A*for Graph Search1.s OPEN.Set g(s)=0,f(s)=h(s)=whatever,P=0,CLOSED

32、=NIL2.If OPEN=NIL,F3.Take first node on OPEN,call it Best-Node(BN),BN CLOSED4.If BN=g,S5.If BN not expandable,go to step 26.Expand BN,generating successors(SUCs)and do:(1)Set P:SUC BN (2)Compute g(SUC)=g(BN)+g(BN,SUC)(3)If SUC=old node(OLD)on OPEN,add OLD to the list of BNs successors If g(SUC)g(OLD

33、),do nothing(4)If SUC=old node(OLD)on CLOSED,add OLD to the list of BNs successors;do the same thing as in step 6(3),set the parent link and g and f values appropriately;However,if g(SUC)g(OLD),the improvement must be propagate to OLDs successors.7.Go to step 2.(4)Heuristic PowerThe total cost of he

34、uristic search consists of two parts:(a)Path cost=(path length)x unit length cost(b)Search cost spent for searching the solution path(a)(b)CostsInformed-ness(5)Measures of Heuristic Performance(a)Penetrance,P,of A Search P is the extent to which the search has focused to a goal,rather than wandered

35、off:P=L/T where L:the length of the path found to the goal T:the total number of nodes generated during the search(including the goal node but not including the start node)Hence,P can be considered as a measure of search efficiency.(b)Effective Branching factor,B,of A SearchB is defined by the equat

36、ion:B+B +B =T(total number of nodes)Hence T=2L(B -1)BLB-1P=LTL(B-1)B(B -1)LWhere the assumptions are made:(1)The depth of the search tree=the length of path L(2)T=the number of nodes generated during search(3)B is a constant for all nodes in the treeHome-Works1.Propose two h functions for the travel

37、ing salesman problem.Is either these h functions a lower bound on h*?Which of them would result in more efficient search?Apply algorithm A with these h functions to the TSP problem.2.Use the evaluation function f(n)=d(n)+w(n)with algorithm A to search backward from the goal to the start node in the

38、8-puzzle problem.3.Discuss ways in which an h function might be improved during a search.5-2 Game-Playing:AND/OR Graph SearchI.Game-Playing and AO GraphTwo-Person-Zero-Sum-Perfect Information Games Example:Grundys Game Two Players,Max and Min,have a pile of pennies.The first player,Min,divides the o

39、riginal pile into twopiles that must be unequal.Each player alternativelythereafter does the same to some single pile when it ishis turn to play.The game proceeds until every pile haseither just one penny or two.The player who first cannot play is the loser.7;Min5,2;Max6,1;Max4,3;Max5,1,1;Min4,2,1;M

40、in3,2,2;Min3,3,1;Min3,2,1,1;Max4,1,1,1;Max2,2,2,1;Max2,2,1,1,1;Min3,1,1,1,1;Min2,1,1,1,1,1;MaxWining pathfor MaxAND/OR GraphFrom Maxs point of view,a win must be obtainablefrom all of Mins successors and from at least one ofMaxs successors.It is an AND/OR graph.In AND/OR graphs,there are hyper-arcs

41、connectinga parent node with a set of its successors.The hyper-arcs are called connectors.Each k-connector is directed from a parent node to aset of k successor nodes.II.Features of AND/OR Graph SearchThe choice of the node to expand next must dependnot only on the f value of that node itself,but al

42、so onwhether that node is part of the current best pathfrom the initial node.E.g.,ABCDh=5 3 49ABCDJIHGFE510343417189920Thus,to search an AND/OR graph,it needs to dothree things at each step:1)Traverse the graph,starting at the initial node andfollowing the current best path,and accumulate the set of

43、 nodes that are on that path and havent been expanded.2)Pick one of these nodes and expand it.Add to thegraph its successors,compute f for each of them.3)Change the f value of the newly expanded node toreflect the new information provided by successors.Propagate this change backward through the grap

44、h.At each node that is visited while going up the graph,decide which of its successor arcs is the most promisingand mark it as part of the current best path.AABBCDCDEF345964410934ABCDGHEF5744104612This may cause thecurrent best pathto change.Thus,an important feature in AND/OR graph search is that o

45、ne must search a solution graph each time from the start node to the terminal node and needs tofrequently check to see if the start node solvable.The definition of solvable node in AND/OR graph:1)Terminal node is solvable node;2)An OR node is solvable iff at least one of its successors is solvable;3

46、)An AND node is solvable iff all its successors solvable.III.Procedure AO*(1)Create a search graph,G,consisting solely of the start node,s.Compute h(s).If s is a terminal node,h(s)=0,label s SOLVED.(2)Until s is labeled SOLVED,do:(3)Begin(4)Compute a partial solution graph,G,in G by tracing down the

47、 marked connectors in G from s.(5)Select any non-terminal tip node,n,of G.(6)Expand n generating all its successors and install these in G as successors of n.For each successor,n ,not already occurring in G,computing h(n).Label SOLVED any of these successors that are terminal nodes.jj(7)Create a sin

48、gleton set of nodes,S,consisting just of node n.(8)Until S is empty,do:(9)Begin(10)Remove from S a node m such that m has no descendants in G occurring in S.(11)Revise the cost h(m)for m,as follows:For each connector directed from m to a set of nodes n ,n ,compute h (m)=c +h(n )+h(n ).Set h(m)to the

49、 minimum over all outgoing connectors of h (m)and mark the connector through which this minimum is achieved,erasing the previous marking if different.likiii1ikii If all of the successors through this connector are labeled SOLVED,then label node m SOLVED.(12)If m has been marked SOLVED,or if the revi

50、sed cost of m is different than its just previous cost,then add to S all these parent of m such that m is one of their successors through a marked connector.(13)End(14)EndIV Search The Game Tree:MinMax Procedure1.Localized SolutionIt is usually impossible to decide a best move based on an entire sea