好那接下来我们来谈论， A*Search ，也就是我们这一讲的重点，它的概念其实就是， 如果已经花费很多cost node，我们就避免展开它。 它已经，已经，到目前为止，已经花了太多cost 下去了，那我们可能， 不优先考虑它，这是很合理的一种想法。那它的做法，Evaluation方面就是， f（n）就是g加h，我们刚刚讲过的。那，目前呢，这个概念上就是， g就是cost so far，就是到目前为止，对不对，就是，我们如果从，好，我这边算starting point， start，那我走走走，走到这边是我的n，那假设n再走下去，可以走到， 我的goal，就是我们通常习惯用g。那所谓的g（n），其实就是这一段。 好，g（n）就是从starting一直走到， 然后node这个节点已经花的cost，那接下来再接下来从 呃，n开始要哦花多少，走到g呢，那个我们因为这边我们还没走， 走，我们目前人停留在这边，n就停留在这边，所以你还不知道，那我们有预，预估值就是， h（n），ok，所以还蛮明显的就是g， 加h它其实有个意义就是说，你从starting point开始走， 然后通过n这个节点，而走到goal的这一条路径的总 总，总totally cost，的预估值，这当然还是一个预估值，那我们把它， 就是，从这个方法来展，好，就是优先，这个最小，我们优先展。 好那我们刚刚也提过，其实它就是come back，如果你只用g 的话，就是uniform cost，那如果只用h 的话，就是greedy cost，呃，greedy search，那我们它实际上结合这两个 优点。好我们看一下，如果用A*Search，我们坐在刚 刚刚的就是呃，台北捷运的那张地图上，呃，结果会怎么样，好， 呃，好这边有，这边，这两张图是整个的展的过程，我觉得我们，呃， 直接回到原来地图示范一下好，好从古亭开始，那一开始我们要算，就是， 呃，古亭因为starting point，要不要算其实都还好，那我们就简单算一下，那古亭的话， 呃，你目前为止花的， 呃，g 是等于0，那你的h是58 ，这里， 所以其实就是0加58等于58， 好，这是g，这是h， 那你加完了就是f，好我们就是古亭的f是58 ， 在这边，那接下来你有两条路可以走，就是东门，还有呃，中正纪念堂， 那，呃，我们个别算一下，东门的话，你的， 我们先算东门好了，东门， 好，它的g，你如果走东门这一条路的话，你的g就是20，对不对，就是你已经花了20， 你才走到这边，那来看一下东门的h是48，花了20 ，你才走到这边。 所以它的f其实是68，ok，我们先记录一下，所以这边是， 58，那东门是68 ，那再来，我们再来算一下中正纪念堂，中正纪念堂的话，你的，呃， g是40，好，就是这一条，那你的h是， 33，就总共是73， 好，那所以这边是73 ，那在这种情况下，你可以选择这两条嘛。 那我们的A*选择的就是68，这个小的这一个， 好，已经，已经可以看到，跟刚刚我们的ii是有点不一样的，这次我们选的是东门， 这个，优先，优先展开，那当然同时，同时再继续展下去，那我们这边计算比较， 复杂，大家可以，我们有投影片，大家可以回去呃，真的走一下，那我们这里用讲的就好，我- 刚刚做完的就是这边， 好，73和68，那A*会优先选择68展，好，那这边展完以后， 这边全都在ii了，就是，我们还是回到iii search iii， 就不要忘了，就是我们展开不是说就直接从东门往下看，而是这些， 从东门，因为你优先展东门，那展开东门以后，这边有，如果是i search的话， 又有可能回到古亭好，这是有可能的，因为i search的话，它不 去考虑那state有没有重复，可这时候你会发现，因为A*的关系，导致古亭， 不再是同样的数字，好，古亭的f变了，好，它的，它是， 58，这是h预估值，开始它的cost，已经花的g 就是20加20， 好，因为你这样走的话呢，可能就是活，从古亭到东门，东门再回到古亭，好那就是20已经- 花了两次。 所以你会发现这个，iii会变越来越贵，所以你会在A*上你会越来越不倾向这样的， 无穷回旋，这样一直来回来回走，因为只要你一个地方来回走，它cost的不为0， state cost不为0的话，cost就一直ii上不去，就一直得加上去，那最后我们就， 以A*来说会越来越不prefer这样的呃，节点，呃，那这五个，这边，我们这边画的i- i的这五个， 五个node来说，五个一样，同样都去算它的f，这边算出来都是它的f ，大家可以check一下， 那这五个里面，我们一样优先展最少cost的，所以会发现其实我们， 不是说，A*并不是说决定往东门这边走，它也不管， 中正纪念堂的那一条路，也就是，因为中间那条，这边其实是这样，那我们下边的其实就是中- 正纪念堂。 好，所以到这边这一张图，就是东门这边会展开， 那我们刚决定展ii，刚刚的iii也是这样， 这是刚刚的ii，那我们在这五个节点里面，实际上最 小，我们会在展iii，那展开ii的时候，再展开是这个样子。 那接下来这八个， 节点都在ii2里面，那同样我们从，从里面再 选最小的开始那来展，那这里面最小的就是忠孝ii这一个， f等于80， 好那你在展忠孝ii，那你就会展成这个样，然后接下来，所， 这边做白色的一样，在这提醒一下，就一样，这边白色的这所有的节点都在， ii2里面1 2 3 4 5 6 7 8 9 10 11，好11,11个节点，11个node，node， 11个node， 好，都在，都子啊我们的ii2里面，好那这里面，一样，根据它 的f，我们再展最小的，那这最小是3到4， 好，就是80， 我们最后展开就会到这边，展开，那在这时候你展开其实已经到ii车站，但是 同样如果我们回顾我们i search，展开的时候，我们不去做 goal test，而是一样把它丢进ii了， 因为这样我们才能保证如果是最佳的话，那就最佳，那这些白色的一样，这边不好画啊，好， 好，那就这边全都在ii里面，好，这里面再找最小的站，那最小的是台北车站，那台北车站- 实际上是， 80，然后你拿出来的时候，从ii里i出来的时候，你这时候做goal test，那么发现，其实它已经走到目标了嘛， 好那这样的话，就，就搞定，那我们最后的这一条i呢，走的就是东门， 忠孝ii，ii，到台北车站， 好，如果各位回去看iiii的话，其实这是最佳路径。 这是最佳路径，没有，就没有比它，没有比80还够，更小的路径了。 好，那我们来一样从四个面向来看A* search这个特性，好，第一件事情是，它的 i呢，就是，原则上是yes， 原则上，好，那除非什么呢，除非有 无穷多的node，它们的f都比goal的f还小， 这是除除，非这个样，goal就给f， 好goal其实，我们等一下会讲到goal的f，在某些条件下， goal的f当然就是，g的，就是g加h嘛，所以这个等于， g的goal加上h的goal。 好，那等一下我们会讲，一些，一些特性。 好，在符合下面特性来说，这个，这一项大致上是， 那我们等一下会，会提，不过这个比i，我们读ih有一些，基本上有一些， 基本上有一些规范，因为，因为整个A*Search， 会它展的方法，就是从f，永远从最小的f开始展嘛，对不对， 展嘛，对不对，永，永远每次从i里面拿出来都f最小的， 一直拿出来的f其实是， 那个nodef基本上是越来越大，越来越大，那除非你今天有， 无穷多的node的f都小于goal的f，否则你迟早一定会走到goal， 好，这是yes，所以原则上是yes，这个条，后面有个条件，这个附加条件， 呃，很容易达成，呃，最简单的达成的case就是你的step cost， 就你的i，就step cost，我们之前i见过了，大致上都大于某一个， 正的值，好，这个当然大于0， 好，就大于等于f i，只要你是正的话，因为，你知道，你只要走够久的话，迟早会超过。 goal的那个f，原则上就是大部分的case都是这个case，所以A*基本上是保证- complete，ii， 比较复杂一点点，我们等下，等一下再回来看，我们现在来讲一下ii以及ii的题。 好，它的space i已经我们刚刚已经大概有感觉了，我们刚刚search，你会发现它的ii， 的那个白，白，白色的node骑士i越长越大，没错，它其实就是ii， 那因为我们讲说它迟早会走到goal嘛，所以走到goal，它被ii的，并不是b的 n次方，而是b的d次方，因为，它如果是complete的情况下，那它， 基本上会回旋goal，回旋到goal就停的时候，那时候，ii是d， 好那这时候你之前看到的节点大致上就是b的d次方，大致。 它的time complexity，它的时间复杂度 其实是稍微不好分析了，因为它跟H有密切的关系。大家记得 就是原则上它还是以iii时间，但是我们刚在讲那个 greedy search的时候有讲过一个例子，就是如果说有 在optimal path上的，在optimal那条路上有根iii， 然后其他就变得无穷大，那这样的话其实你的search瞬间就结束，跟就不可能expo- nent，因为你就直接会走 那一条路，在规定的情况下。所以跟H很有关系，所以基本上它会，它会跟这个H 有这个关系，可是我们现在定义一个F总称为relative arrow，好那这边 这个符号我们后面会不断的用，所以大家可以记一下，就是H*, H*是什么呢？就是完美的估计函式，那所谓完美的估计函式呢， 我们说估计函式就是从现在节点N然后你走到 G，你走到目前离你最近的G，这边还要花多少的估计值， 这是H OF N，那所谓完美的估计，那H*就是真正， 其实你从N走到G真正要花的那一个值，它要在花的COST。 那这个COST原则上设计上我们还不知道，对吧，原则上的类可能也不太清楚，但是你想象 反正总是一个存在，实际上是存在的一个函式。简单来讲就是 你如果H，你用的H*使用的H是跟完美的这个评估函式如果越接近的话， 那你的COMPLETENESS就会越好。譬如说 如果你如果刚好基本上如果刚好一样的话你epsilon=0, epsilon=0的情况下你的iii基本上就是iii或者 甚至是iii，iii不太可能啦，那实际上当然你套用这个式子看起来可能，这是一个- 预估啦。 那如果，差很多的话， 如果差很多，那它是哪一种，譬如说你的epsilon根本就是1， 然后我们就是1的话，就H给你0， 好，H给你0，就说这H是什么意思呢， 就是我给你H根没给你这H是一样的，我说iii，你说任何一个节点 就任何一个Node你问我说你离目标还有多远我就说，你就到了，你就到了。 好，那这样的话其实算出来你的epsilon就等于1了。 因为这个是0.好，这个是0，你算出来就是1，那这种情况下，整个iii就回到 BFS含BFS的III,就是B的B次方。 就是你的那个H对你完全没帮助。我给你一个蛮没用的H，那你完全没帮助的情况下， 那你就reduce原来的exponential。但是如果给你H有点道理的话就会大量- 的缩减设置的时间。 好那最后一个项就是optimality, optimality这边其实我们要探讨一阵子，但是它有条件， 就是原则上，你如果给你， 我给你一个任意的H的话它不能保证什么事，但它在某些条件下保证， 就是这个，iii的H是不是admissible，还有consistent, 好，如果，这个consistent是grave才需要。 好如果你的search是用graph search的话那你需要 多加一个consistent，原则上就是admissible就可以。 admissible意思是什么呢？是你的h永远不高估， 好，永远不高估，也就说所有的对，严格来，就你用数学上来讲的话 就是这个样子了。我们刚就讲到一个H*这个例子， 这个概念，就说你对每个state它传回的H值永远都小于等于真正要花费的test， 好，那这样的 iii我们称它为admissible,如果这种情况的话那基本上如果再去search， 再去search的话，那这样就够了， 就保证H*永远会给你最佳的solution。好这当然听起来不太直接，为什么这样就 可以保证那我们等一下会看一下，那如果你这样用的是graph search的话 除了admissible之外，你还要再加上一个条件就是consistent,con- sistent它有，它的式子写起来 是这个样子，式子写起来就是对任何一个从N节点， 然后它走一步就可以走到N'，对任何一个 N节点就是你走一个cost，这个cost就是step cost，就是你从N坐了A你会走到N'， 好，那这个的估计值，一定要小于等于N， N‘的这个估计值加上这个cost,如果你保证这件事的话我们成为consistent 那这个任意consistent这个特性我们等一下会提到那实际上其实就是 三角不等式，我们当然现在这样讲，各位可能还没有很有感觉，但是原则上就是我们等一下对- 这两个都会再提， 但是记得一件事，就是A* optimality要depend上你的heuristic,那你的heuristi- c如果在去research的话只要admissible 它就保证会拿到最佳。但是如果你在graph search的时候，那 heuristic除了admissible之外你还要再将consistent的条件 那就保证optimality。那大家也记一下这个是 我们是保证，也就说我们是充分但不必要条件， 也就是我们可能会有一些heuristic它 既不admissible又不consistent，但是它一样会 给你最佳解。就是讲我们这个条件是充分但是不必要，但是如果你如果H符合这两个条件的话， 我一定给你optimal solution。那你如果没有符合这两个的话 你还是有可能拿到optimal solution，我们讲最简单一个例子，如果我今天 我的H譬如说等于H*,假设我真的知道H*是什么， 加上100好了，我就把，全部 把它加上100，就是你的H，我用这个东西来做，因为我如果用H*做search的话它- 一定是optimal的， 因为就是万能的天神给你的一个heuristic,但是你如果把它全部加上100， 如果全部讲都是加constant 100,所以其实你真的做search的结果会一模一样，跟你用H*做起来一模一样， 可是这样的H根据我们的定义来说它并不admissible。 可是它可能会给你Optimal的结果。所以就记得这件事，你如果符合这两个特性， 我能保证你Optimal，你如果不符合这两个特性，其实还是有可能拿到optimal- 的，那要depends上你的， 就我们不能，在数学上不能做任何的证明。
