小编

1. 问题办理与搜索1.1. 办理问题的能力无疑是区分人类和其他动物的关键能力之一1.1.1. 办理问题是须要聪慧的1.2. 汉诺塔1.2.1. 对付三个金环而言1.2.1.1. 你不可能找到少于7次的办理方案了1.2.2. 最初，我们只能选择移动最小的金环，只有将它移动到中间或者最右边的柱子上1.2.2.1. 以是对应第一步，我们只有两种移动可能，以及两种不同的新状态1.2.3. 如果我们选择将最小的金环移动到中间柱子，那么我们随后可以实行三种操作1.2.3.1. 将最小的金环移动到最左侧或者最右侧的柱子1.2.3.2. 将第二个金环移动到最右侧柱子(不能将第二个金环移动到中间柱子）1.2.4. 以此类推1.3. 所有类似汉诺塔的问题都有着相通的办理方案1.3.1. “状态”这个术语在人工智能领域指的是某个事物或者问题在某个特定时刻呈现的构造1.3.2. 首先，从初始状态开始，我们考虑每个可能的动为难刁难初始状态的影响，实行每一步操作都会将初始状态转换为一个新的状态1.3.3. 如果个中某个新状态是我们的目标状态，那就意味着操作成功1.3.3.1. 这个问题的办理步骤便是从初始状态达到目标状态所实行的操作1.3.4. 否则，在每一个新状态上，连续考虑所有可能导致状态变更的操作，重复这样的过程，以此类推1.4. 穷举搜索1.4.1. 穷举搜索的办法不仅能担保在问题可解的时候探求到问题的解，还能担保探求到问题的最优解1.4.1.1. 作为打算机的算法，穷举搜索非常大略，编写一个程序来实现它非常随意马虎1.4.2. 大略的穷尽式搜索是一项非常原始的技能1.4.2.1. 可以利用启示式方法来对它进行优化，但是并不担保一定有效1.4.2.2. 你会创造对搜索办法的优化可以改进一些东西，但是，终极你仍旧无法绕过组合爆炸1.4.2.2.1. 在大多数情形下，能在理论上确保问题可以办理的方案，在实践中都会碰着这个问题1.4.3. 学会避免做一些徒劳的移动1.4.3.1. 一台大略实行穷举搜索的打算机却无法做到1.4.3.2. 它只能穷举出所有移动下的所有新状态，哪怕某些穷举步骤便是在摧残浪费蹂躏韶光，它也会走转头路，回到已经被确认过失落败的状态1.4.4. 除了太多重复和低效率以外，穷举搜索还有一个根本的问题1.4.4.1. 搜索树随着分支因子能增长到多大1.4.4.1.1. 常日一局围棋游戏要走大概200步，在围棋搜索树中存储200步走棋的搜索树状态数目1.4.4.1.2. 是一个大到你我都无法想象的天文数字，它比我们宇宙中所有原子的数目还大几百个数量级1.4.4.2. 对确定了分支因子数的搜索树，在不同层级有多少种状态1.5. 搜索树这种迅速、荒诞的增长速率导致了无法想象的问题，我们称之为组合爆炸，它是人工智能所面临的最主要的实际问题1.5.1. 在人工智能发展初期，组合爆炸被认为是根本性问题，麦卡锡将其确定为1956年人工智能暑期学校的主要研究课题之一1.5.2. 搜索树中的每个层级都呈指数型增长1.5.2.1. 在层级增多的时候，组合爆炸会导致可能涌现结果的增长速率超乎想象1.5.2.2. 彻底列举每一种组合可能性的办法，是不可行的1.5.2.3. 理论上它行得通(如果韶光足够，总会得到精确的答案)，但在实践中它毫无意义(由于对每种可能的组合做判断须要的韶光是天文数字)2. 深度优先搜索2.1. 并非逐级建立完全的搜索树，而是沿着个中一个分支构建搜索树2.2. 通过深度优先搜索，我们沿着一个分支往下扩展，直到得到办理方案或者确信无法得到办理方案2.3. 如果碰着困难，那么我们就停滞在该分支上的扩展，返回到上一级，选择其余的分支2.4. 深度搜索的紧张优点在于不用存储全体搜索树，只须要存储当前正在处理的分支即可2.5. 毛病2.5.1. 如果选择了缺点的分支进行探索，可能会在缺点的路上越走越远，永久找不到办理方案2.6. 首先我们得确认哪个分支最值得搜索3. 启示式搜索3.1. 启示式搜索的观点便是利用所谓的“履历法则”来辅导搜索的重点3.2. 常日我们也无法探求到直示正确搜索路径的启示式方法，但我们每每可以在感兴趣的问题上找到启示式搜索方向3.3. 启示式搜索是一个自然而然产生的观点，多年来它被重新定义了很多次，以是辩论到底是谁发明了它已经毫无意义3.4. 第一个运用在人工智能程序的启示式搜索来自一个玩跳棋游戏的程序，由IBM的亚瑟·塞缪尔(Aithur Samuel)于20世纪50年代中期创造3.4.1. 塞缪尔利用的是IBM701打算机，只能处理相称于几页文本长度的程序代码3.4.2. 塞缪尔跳棋程序的关键点在于给棋盘的各个位置授予不同的权重，用以评估对选手而言位置“好”的程度3.4.3. 从直觉来说，某些“好”的位置可能让某位选手更随意马虎取得胜利，而一些“坏”的位置则会导致失落败3.4.4. 程序将不同的评估参数整合起来，给出棋盘位置的一个综合评估代价分数，形成一个量化的评估标准3.4.5. 再根据启示式搜索方法来选择最佳的棋盘移动路径3.5. 极大极小值搜索3.5.1. “最坏情形推理”的方法3.5.2. 假设对手的行为会使得自己的得分最大化，让你的得分最小化3.5.3. 是对抗性游戏的基本观点3.6. 大部分早期的启示式搜索算法，包括塞缪尔的程序，都利用了某种特殊的启示办法：“考试测验—实践—判断”3.7. 20世纪60年代末，美国SRI人工智能研究中央的尼尔斯·尼尔森(Nils Nilsson)和他的同事取得了打破，他们开拓出名为A的技能3.7.1. 在A之前，启示式搜索不过是一个猜谜游戏3.7.2. 在A之后，它是一个数学上很随意马虎理解的过程3.7.3. A现在被视为打算机科学中的根本算法之一，并且在实践中得到了广泛的运用3.7.4. 只管A很惊艳，但它仍旧依赖于利用特定的启示式搜索：好的启示能很快地找到办理方案，而差的启示就没什么代价4. 繁芜性障碍4.1. 图灵发明打算机可能算是打算机科学史上最大的讽刺之一，由于他的本意是证明有些事情打算机永久也办不到4.2. 在图灵的研究成果问世后的几十年里，探索打算性能做和不能做的事情的范围形成天下各地数学系的小分支的研究方向4.2.1. 事情的重点在于把那些固有的不可剖断问题(无法用打算机办理的问题)和可剖断问题(能够用打算机办理的问题)区分开来4.3. 不可剖断的问题存在层次构造4.3.1. 即存在某些问题，不仅不可剖断，还是高阶不可剖断的4.4. 在20世纪60年代，确定一个问题是否可剖断，还远远不足4.4.1. 一个问题在图灵看来是可以办理的，并不虞味着它在实际操作上是可以实现的4.4.2. 图灵只是从理论上证明某些问题有解，但是有些问题的办理办法须要花费弘大的打算资源4.4.2.1. 须要动用的打算机内存大到不可估量，或者打算机的运行速率慢得出奇，能打算出结果的韶光遥遥无期4.4.2.2. 期待英特尔的工程师们供应打算速率更快的芯片也无济于事4.4.2.3. 传统打算机技能再怎么突飞年夜进，也无法在合理的韶光内完成10^29这个数量级的打算任务5. NP完备问题5.1. “NP”代表“不愿定多项式韶光”5.1.1. 详细的技能定义相称繁芜5.1.2. NP完备问题背后的逻辑很大略5.2. NP完备问题的基本构造早在20世纪70年代就已成形5.2.1. 1971年美籍加拿大数学家斯蒂芬·库克(Stephen Cook)的一篇论文确定了NP完备问题的核心思想5.2.2. 随后美国人理查德·卡普(Richard Karp)证明了库克NP完备问题的范畴比最初想象的要广泛得多5.3. 全体20世纪70年代，人工智能领域的研究职员开始利用NP问题完备性理论来研究他们的课题，结果令人震荡5.3.1. 不管哪个领域（办理问题、玩游戏、操持、学习、推理任何方面），彷佛关键性的问题都是NP完备问题(乃至更糟)5.3.2. 到了20世纪70年代，NP完备性理论和组合爆炸成为笼罩在人工智能领域的阴影，以打算繁芜性的形式阻拦在人工智能发展道路上，使它陷入结束5.4. 组合问题是一个NP完备问题5.5. 旅行推销员问题5.5.1. 旅行推销员问题和团队培植问题一样，都会面临组合爆炸的难题5.5.2. 如果你发明了一种可以高效又准确办理团队培植问题的方法，那么就等同于你发明了可以高效又准确办理旅行推销员问题的方法5.5.3. 这种神奇的方法并不仅仅适用于这两个问题，而是可以办理所有NP完备问题5.6. 所有的NP完备问题都能共通，可以相互转换5.6.1. 要么所有NP完备问题存在通用的解，要么它们都无解5.6.2. 如果你能找到高效又准确办理某个NP完备问题的方法，就意味着你能够办理所有NP完备问题5.7. 事实上NP完备问题能否有效办理，是当今科学界最主要的开放性问题之一5.7.1. 这个问题被称为P与NP问题5.7.2. 我们还没有明确地证明NP完备问题不可解5.8. 如果你创造自己要办理的问题是NP完备问题，这就意味着传统意义上的打算机技能在办理该问题上是行不通的5.8.1. 从精准的数学意义来说，你的问题太难了6. 人工智能寒冬6.1. 20世纪70年代初，人工智能的瓶颈让科学界越来越沮丧，没有太多有用的核心研究进展6.1.1. 某些研究职员又大肆鼓吹人工智能的未来6.1.2. 当年的研究职员没故意识到正在研究的问题实质上是打算机无法处理的，因而总存在涌现打破性进展，使得问题迎刃而解的可能性6.2. 到了70年代中期，批评人工智能的风潮达到狂热的程度6.3. 德莱弗斯选择的报告题目是《炼金术与人工智能》，明白无误地表达了他对这一领域及其事情职员的唾弃6.3.1. 他的某些不雅观点是有道理的，特殊是关于人工智能先驱者们浮夸的不雅观点和宏伟的预测6.4. 20世纪70年代初到80年代初这10年被称为人工智能寒冬6.4.1. 更确切地说该当是人工智能的第一个寒冬，由于此后还有类似事宜发生