1.3　计算思维引论

思维是人脑对客观事物的概括和间接的反应过程。思维过程就是对信息的处理过程，可以说思维就是一种广义的计算。

1.3.1　计算与计算思维

本节主要对计算、思维、计算思维的定义和理解进行简要阐述。

1．计算的含义

计算的英文单词Calculation有相当精确的定义，例如：使用各种计算方法（常用的有加、减、乘、除等）所进行的简单“算术”（如：将3乘以4）。计算也有较为抽象的定义，例如：某一场竞争中有关“策略的计算”。Computation单词虽然也被译为计算，Calculation是指比较简单的“计数及算术”，而Computation是指应用比较复杂的规则与逻辑求解某个困难问题。后者的计算过程比前者复杂，也不一定与数字有关。其实，无论是加、减、乘、除等“算术”计算，或者是有关“策略的计算”，计算都是一种思考过程。

随着计算机日益广泛而深刻的运用，计算这个原本专门的数学概念已经泛化到了人类的整个知识领域，并上升为一种极为普适的科学概念和哲学概念，成为人们认识事物、研究问题的一种新视角、新观念和新方法。

在大众的意识里，计算首先指的就是数的加减乘除，其次则为方程的求解、函数的微分积分等；懂的多一点的人知道，计算在本质上还包括定理的证明推导。可以说，“计算”是一个无人不知无人不晓的数学概念，但是，真正能够回答计算的本质是什么的人恐怕不多。事实上，直到20世纪30年代，由于哥德尔（K.Godel，1906—1978）、丘奇（A.Church，1903—1995）和图灵等数学家的工作，人们才弄清楚什么是计算的本质，以及什么是可计算的、什么是不可计算的等根本性问题。

抽象地说，所谓计算，就是从一个符号串f变换成另一个符号串g。比如说，从符号串12+3变换成15就是一个加法计算。如果符号串f是x2，而符号串g是2x，从f到g的计算就是微分。定理证明也是如此，令f表示一组公理和推导规则，令g是一个定理，那么从f到g的一系列变换就是定理g的证明。从这个角度看，文字翻译也是计算，如f代表一个英文句子，而g为含意相同的中文句子，那么从f到g就是把英文翻译成中文。这些变换间有什么共同点？为什么把它们都叫作计算？因为它们都是从已知符号（串）开始，一步一步地改变符号（串），经过有限步骤，最后得到一个满足预先规定的符号（串）的变换过程。

从类型上讲，计算主要有两大类：数值计算和符号推导。数值计算包括实数和函数的加减乘除、幂运算、开方运算、方程的求解等。符号推导包括代数与各种函数的恒等式、不等式的证明，几何命题的证明等。但无论是数值计算还是符号推导，它们在本质上是等价的、一致的，即二者是密切关联的，可以相互转化，具有共同的计算本质。随着数学的不断发展，还可能出现新的计算类型。

2．思维概述

思维是主体对信息进行处理以及主体意识的能动活动，如对信息进行采集、传递、存储、提取、删除、对比、筛选、判别、排列、分类、整合和表达等。

人的思维过程包括对信息内容的接收、加工、储备与传递四个过程。其中接收过程是指从接收的信号中读取信息内容；加工过程是指对信息进行改造及格式化的过程；储备过程是指存储情感信息资料，进行备用的过程；传递过程则是使用信息内容的过程。

思维是人脑对客观事物本质和规律的反映，思维具有概括性、间接性和能动性等特征。思维的概括性是指在人的感性基础上，抽取一类事物的共同的、本质的特征和规律加以概括，例如，人们根据感知到的太阳东升西落，通过思维能揭示这种现象是地球自转的结果。思维的间接性是指非直接的、以其他事物作为媒介来反映客观事物，例如医生根据医学知识和临床经验，通过病史询问，再辅以一定的检查，就能判断病人体内的病变情况，并确定病因、病情，出治疗方案。思维的能动性是指通过思维不仅能认识和反映客观世界，而且还能对客观世界进行改造。思维过程是一种信息处理过程，从某种意义上来说，也是一种广义的计算。从信息论的角度来看，思维是人脑的信息加工过程。

科学思维通常是指理性认识及其过程，是人脑对科学信息的加工活动。科学思维必须遵守三个基本原则：具有严密的逻辑性，辩证地分析和综合，体系上完整统一。从人类认识世界和改造世界的思维方式出发，科学思维包括理论思维（逻辑思维）、实验思维（实证思维）和计算思维。

计算思维又称构造思维，是指从具体的算法设计规范入手，通过算法过程的构造与实施对问题进行求解。人们可以借助计算机解决各种问题，逐步实现人工智能的较高目标。

3．计算思维的概念

目前广泛使用的计算思维的概念是由美国学者周以真教授提出的：计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。

计算思维的定义主要强调以下三点。

第一，问题求解中的计算思维。利用计算手段进行问题求解时，首先将实际的应用问题转换为数学问题，然后建立模型、设计算法和编程实现，最后在实际的计算机中运行并求解。在这个过程中，前两步是计算思维中的抽象，最后一步是计算思维中的自动化。

第二，设计系统中的计算思维。R.Karp认为，任何自然系统和社会系统都可看作一个动态演化系统，演化过程中伴随着物质、能量和信息的交换，而这种交换可以映射为符号变换，使之能用计算机实现离散的符号处理。当动态演化系统抽象为离散的符号系统后，可以采用形式化的规范对其进行描述，通过建立模型、设计算法和开发软件来揭示演化的规律，对系统演化进行实时控制并自动执行。

第三，人类行为中的计算思维。计算思维是基于可计算的手段，以定量化方式进行的思维过程，能满足信息时代新的社会动力学和人类动力学要求。理论计算手段进行人类行为研究，即通过各种信息技术手段，设计、实施和评估人与环境之间的交互。研究生命的起源与繁衍、理解人类的认识能力、了解人类与环境的交互以及国家的福利与安全等，都属于该范畴，都与计算思维密切相关。在人类的物理世界、精神世界和人工世界这三个世界中，计算思维是建设人工世界所需要的主要思维方式。

计算思维的本质是抽象与自动化。计算思维是具有形式化、程序化、机器化特征的人类思维活动方式。计算思维的活动过程并不是某些特定的、程序化的思维过程，像计算机科学家那样思维并不意味着就是进行计算机程序设计，更为主要的是要求能够在抽象的多个层面上进行思维。计算思维中的抽象超越了物理的时空观，物理世界中的问题可以完全用符号进行表示，并且抽象结果最终需要能够机械地一步一步自动执行，所以计算思维的抽象过程中需要进行精确、严格的符号标记和问题建模。

计算思维是人类本身的一种根本的思维技能，是人类解决各种问题的一条途径，借助于计算机的强大计算能力，人类可以更好地解决各类需要进行大量计算的问题。由于计算机能够对信息与符号进行快速地处理，大大拓展了人类认知世界和解决问题的能力，因此，许多原本仅仅是理论上可行的处理过程变成了可以实现的过程，海量数据处理、复杂系统模拟和大型工程组织等许多方面的问题都可以借助于计算机实现从最初的想法到最终实现过程中的自动化、精确化和过程的可控制。

计算机不仅为不同专业提供了解决专业问题的有效方法和手段，而且提供了一种处理问题的构造思维方式。熟悉使用计算机及互联网，可为人们终身学习提供广阔的空间以及良好的学习工具与环境。这正是信息时代大学生必须掌握的信息素养，了解计算系统的思维——学习计算机工作原理，理解计算系统的功能如何能够越来越强大；利用计算系统的思维——理解结合计算系统如何控制和处理，满足数字化生存与发展的需求。

1.3.2　计算理论

计算理论是计算机科学的理论基础之一。本节从计算本质与计算模型出发，给出图灵机模型、可计算性、计算复杂性以及问题的求解过程。计算理论的基本思想、概念与方法已被广泛应用于计算科学的各个领域之中。

1．计算模型

计算模型是指用于刻画计算概念的抽象形式系统或数学系统。计算模型为各种计算提供了硬件和软件界面，在模型的界面约定下，设计者可以开发整个计算机系统的硬件和软件支持，从而提高整个计算系统的性能。

（1）图灵关于计算的定义

早在现代计算机出现之前，图灵对计算本质进行了研究。1936年他发表了著名论文《论可计算数及其在判定问题中的应用》，第一次把计算过程和自动机建立对应，提出了最原始的计算模型。模型结构简单，用它可以确切地表达任何运算，被称为图灵机模型，为计算机的发展奠定了理论基础。

图灵揭示了计算过程的本质特征。直观地说，计算过程就是计算者（人或机器）对一条两端可无限延长带子上的一串0 1输入串执行指令操作，经过有限步骤而一步步地改变带子上的0、1状态，得到满足预先规定的符号串的变换过程。

（2）人的计算过程

人在进行运算时需要遵守一套规则，规则是通过人的聪明才智构建起来的，规则要机械严格执行。计算时人把符号写在纸上，按以下计算步骤做计算动作并计算结果。

①将符号（数据信息、计算符号）写在纸上（用纸张存储信息）。

②根据计算符号，按步骤进行计算动作（计算规则控制动作）。

③计算动作的执行导致纸上出现符号变化（执行动作获得结果）。

例如，人在进行下面的算式计算时，首先在纸上写出计算式子，根据乘法的计算规则，按照逐位相乘、错位相加的规则得到了计算结果，计算结果的产生是人执行相应计算动作（如乘法计算动作、记录数据动作、加法计算动作）过程中出现的符号变化。

计算机器是对人的计算行为的模拟过程，不仅要模拟人的行为动作，同时对行为动作规则进行模拟。图灵把计算过程和自动机建立对应，抽象出如下计算过程。

①将运算介质确定为线性带子，而不是二维的纸。例如25×31=25+750=775，带子可设想为磁带，带子被划为方格，方格放一个符号。

②人在运算时一般每次注视五六个符号，图灵规定每次仅注视1个符号，注视由读写头执行。

③一组运算法则存放在有限状态控制器中，根据磁头注视的符号及当前状态决定下一步动作。

机器通过对人计算过程的模拟，将计算的对象（数据信息、计算符号信息）存储于运算介质（如内存、磁盘、磁带等），将一组运算法则存放于状态控制设备中，根据当前的状态控制运算设备执行一定的动作序列，在运算介质上记录结果信息，因此利用计算机进行问题求解，就是利用机器对人类的智能行为的模拟。

（3）图灵机模型

图灵第一次把计算过程和自动机建立对应，提出了可模拟人的运算过程的图灵机计算模型。图灵机不是一种具体的机器，而是一种理论模型。这种概念上的简单机器，运算能力极强，理论上可用来计算所有想象到的可计算函数。

图灵机由可无限延伸的带子和可在带子上左右移动的读写头以及控制器与状态寄存器组成。其中，运算介质（线性带子）注视当前符号（一次只看一个符号）以及一组规则，它们放在状态控制器中，根据当前符号与当前状态决定下一步动作。图灵机模型如图1.18所示。

图灵机中计算的每一过程（数据与程序）都可用字符串的形式进行编码，并存放在存储器中，需要使用时进行译码并由处理器自动执行。

图1-18　图灵机模型概念示意图

图灵机可以模拟人所能进行的各种计算过程，该模型从初始状态开始，在计算过程的每一时刻，通过读写头注视带子某一格子上的符号。根据当前时刻的状态和注视的符号，机器执行相应动作。

图灵机中由状态和符号对偶决定的动作组合称为指令，决定机器动作的所有指令表称为程序。当处于结束状态时图灵机停机，此时带子上的内容就是图灵机的输出。

图灵机理论奠定了通用电子计算机设计的理论基础，同电子技术的结合最终产生了20世纪最伟大的奇迹。

2．可计算性

可计算性理论是研究计算的一般性质的，也称算法理论或能行性理论。通过建立计算的数学模型，精确区分哪些问题是可计算的，哪些是不可计算的。对问题的可计算性分析可使得人们不必浪费时间在不可能解决的问题上（或尽早转而使用其他有效手段），并集中资源在可以解决的那些问题上。

可计算性定义：对于某问题，如果存在一个机械的过程，对于给定的一个输入，能在有限步骤内给出问题答案，那么该问题就是可计算的。

可计算性具有以下几个特性。

①确定性：在初始情况相同时，任何一次计算过程得到的计算结果都是相同的。

②有限性：计算过程能在有限的时间内、在有限的设备上执行。

③设备无关性：每一个计算过程的执行都是“机械的”或“构造性的”，在不同设备上，只要能够接受这种描述，并实施该计算过程，将得到同样的结果。

④可用数学术语对计算过程进行精确描述，将计算过程中的运算最终解释为算术运算。计算过程中的语句是有限的，对语句的编码能用数值表示。

3．计算复杂性

同样一个问题，不同的算法，在机器上运行时所需要的时间和空间资源的数量时常相差很大。因而用算法的复杂度作为度量算法优劣的一个重要指标。计算复杂性的度量标准一是计算所需的步数或指令条数（称为时间复杂度），二是计算所需的存储单元数量（称为空间复杂度）。

（1）问题规模表示

复杂性总是对于特定的问题类型来讨论的，这类问题包括无穷多个个别问题，有大有小，我们不可能也不必要研究每个具体问题的计算复杂性。

例如：矩阵乘法问题，相对地说，100阶矩阵相乘是个大问题，而2阶矩阵相乘就是个小问题。可以把矩阵的阶n作为衡量问题大小的尺度。又如在图论问题中，可以把图的顶点数n作为衡量问题大小的尺度。一个个别问题在计算之前，总要用某种方式加以编码，并可把这个编码的长度n作为衡量该问题大小的尺度，在图灵机理论中就是计算的输入字的长度n。

（2）复杂度表示

当给定待计算问题的一个求解算法之后，计算大小为n的问题所需要的时间、空间可以表示为n的函数。在图灵机理论中，假定算法在图灵机上计算的输入字的长度是n，那么完成此计算所需要的最长时间（即运算的最长步数）是n的一个函数，称此函数为此算法的时间复杂度。同样，完成此计算所需要的最大空间（即运算涉及的格子最大数量）也是n的一个函数，称此函数为此算法的空间复杂度。当要解决的问题规模越来越大时，时间、空间等资源消耗将以什么样的速率增长，即当n趋向于无穷大时，这个函数的增长的阶是什么，这就是计算复杂性理论所要研究的主要问题。例如函数不超过指数函数，就说此算法具有指数时间或指数空间复杂度。

常见的时间复杂度有：常数Ο（1）、对数阶Ο（logn）、线性阶Ο（n）、线性对数阶Ο（nlogn）、平方价Ο（n2）、立方阶Ο（n3）……k次方阶Ο（nk）、指数阶Ο（2n），这里的O表示数量级。

当n充分大时，上述不同类型的复杂度递增排列的次序为：

Ο（1）<Ο（logn）<Ο（n）<Ο（nlogn）<Ο（n2）<Ο（n3）<……<Ο（nk）<Ο（2n）

显然，时间复杂度为指数阶Ο（2n）的算法效率极低，当n值稍大时，算法所需的时间就会导致无法实际应用该算法。

类似于时间复杂度的讨论，一个算法的空间复杂度S（n）定义为该算法所消耗的存储空间，它也是问题规模n的函数。算法的时间复杂度和空间复杂度合称为算法的复杂度。

4．求解问题过程

随着计算科学的发展，计算理论与许多其他学科已相互影响，可用计算机求解问题的领域也非常广阔，既可求解数据处理、数值分析类问题，也可以求解物理学、化学和心理学等学科中所提出的问题。利用计算机求解问题的过程一般包括：问题的抽象、设计问题求解算法和问题求解的实现等过程。

（1）问题的抽象

建立数学模型的过程就是进行问题的抽象。建模过程是从需要解决的实际问题出发，引出求解该问题的数学方法，然后再回到问题的具体求解中去。

建模过程中的思维方法就是对实际问题的观察、归纳和假设，然后进行抽象，并将其转化为数学问题。对某个问题进行数学建模的过程中，可能会涉及许多数学知识，模型的表达形式不尽相同，有的问题的数学模型可能是一组方程形式，有的可能是一种图形形式，总之，是用字母、数字及其他数学符号建立起来的等式或不等式以及图表、图像、框图和数学结构表达式对实际问题本质属性的抽象而又简洁的刻画。

例如，哥尼斯堡七桥问题的解决就是进行问题抽象的典型实例。

在哥尼斯堡的一个公园里，有7座桥将普雷格尔河中的两个岛与河岸连接起来，问是否可能从这4块陆地中任一块出发，恰好通过每座桥一次，再回到起点？

数学家欧拉（E.Euler）在解决该问题的论文中，用字母A、B、C、D代表4个区域，用7条线代表7座桥（见图1.19），将该问题抽象为一个数学问题，即经过图中每条边一次且仅一次的回路问题，并用数学方法给出了判定规则，证明了这样的回路不存在。欧拉的论文为目前被广泛应用的图论奠定了基础，图论也已成为了对实际问题进行抽象的一个有力工具。

图1-19　哥尼斯堡七桥问题

（2）设计问题求解算法

计算机求解问题的具体过程可由算法进行精确描述，算法包含一系列求解问题的特定操作，具有如下性质。

①将算法作用于特定的输入集或问题描述时，可形成有限步动作构成的动作序列。

②该动作序列具有唯一的初始动作。

③序列中的每一动作具有一个或多个后继动作。

④序列或者终止于某一个动作，或者终止于某一陈述。

算法代表了对问题的求解，是计算机程序的灵魂，程序是算法在计算机上的具体实现。

（3）问题求解的实现

问题求解的实现是利用某种计算机语言编写求解算法的程序，将程序输入计算机后，计算机将按照程序指令的要求自动进行处理并输出计算结果。

1.3.3　可计算的典型问题

本节通过排序、汉诺塔、国王婚姻和旅行商这4个经典示例理解计算机求解的代表性技术，在计算中大量出现的排序涉及数据的组织技术，汉诺塔问题中使用的递归技术是将大问题归约为性质相同子问题的求解方法，国王婚姻问题涉及并行计算技术，而旅行商中路线选择则需要应用最优化方法。这些典型问题的代表性求解技术在计算机科学中占有重要地位。

1．排序——数据有序排列

排序是将一组“无序”的记录序列调整为“有序”的记录序列的过程。排列次序是人们在日常生活中频繁遇到的问题，排序问题在计算机学科中也占有重要地位。

例如在字典中查找生词，如果字典的字是杂乱无章地排列，可从头到尾一个个地检查，如果所检查到的字同不认识的生字一样，就算找到了。在上述过程中，假设字典中共有1 000个字，那么最坏情况需要检查1 000次，效率很低。当然，现在的字典中文字都排了序，英文单词按字母顺序，汉字按音序，另外还有偏旁部首索引，这大大加快了查字典时的查找速度。计算机里的查找算法，也用到排序和索引，实现过程同人查字典一样，只不过一个是人在查找，一个是计算机查找而已。

目前常用的几十种经典排序算法的效率不尽相同。冒泡排序（Bubble Sort）是一种最简单的排序算法。它的基本思想是反复扫描待排序数据序列（数据表），在扫描过程中顺次比较相邻两个元素的大小，若逆序就交换这两个元素的位置，这样，越大（或越小）的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的具体过程如下（设按照由小到大升序排列）。

①比较表中相邻的元素。如果第一个比第二个大（逆序）就交换。

②对每一对相邻元素依次做同样的工作，从开始第一对到表尾的最后一对。得到表尾元素是此次扫描序列中最大的数。

③表长度减1，针对剩余元素构成的表重复以上①②两个步骤。

④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较。

冒泡排序算法排序思路简单，但它的排序效率低，对于n个待排序序列最多需要做n-1趟比较，每一趟最大需要n-1次比较，最坏情况下，共需要Ο（n2）的比较次数。

快速排序（Quick Sort）是对冒泡排序的一种改进，其效率较高。对于规模为n的待排序数据序列，快速排序需要Ο（nlogn）的比较次数，有关快速排序的基本思想在此不进行深入探讨。

计算机中进行数据处理时，经常需要进行查找数据的操作，数据查找的快慢和数据的组织方式关系密切，排序是一种有效的数据组织方式，为进一步快速查找数据提供了基础。不同的排序算法在时间复杂度和空间复杂度方面不尽相同，计算机所要处理的往往是海量数据，因此在实际应用时需要结合实际情况合理选择采用适合问题的排序方法并加以必要改进。

2．汉诺塔求解——递归思想

汉诺塔问题（也称为梵塔）是印度的一个古老传说：在世界中心贝拿勒斯（位于印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：

①一次只移动一片，且只能在3根宝石针上来回移动。

②不管在哪根针上，小片必须在大片上面。

僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而汉诺塔、庙宇和众生也都将同归于尽。

汉诺塔问题是一个典型的可用递归方法求解的问题。计算机科学中的递归将一个较大问题归约为一个或多个子问题的求解，并且这些子问题的规模小于原问题，但结构与原问题相同。根据递归方法，可以将64个金片搬移转化为求解63个金片搬移，如果63个金片搬移能被解决，则可以先将前63个金片移动到第二根宝石针上，再将最后一个金片移动到第三根宝石针上，最后再一次将前63个金片从第二根宝石针移动到第三根宝石针上。依次类推，63个金片的汉诺塔问题可转化为62个金片搬移，62个金片搬移可转化为61个金片的汉诺塔问题，直到转换到了1个金片，此时可直接求解，如图1.20和图1.21所示。

图1-20　汉诺塔问题

图1-21　汉诺塔的执行过程（n=3）

汉诺塔求解方法如下。

①当n=1时，将编号为1的圆盘从宝石针A直接移到宝石针C上。

②当n>1时，需要利用宝石针B作为辅助，设法将n-1个较小的盘子按规则移到宝石针B中，然后将编号为n的盘子从A宝石针移到C宝石针，最后将n-1个较小的盘子移到C宝石针。

按照这样的计算过程，64片金片由一根针移到另一个针上，并且始终保持上小下大的顺序。这需要多少次移动呢？假设有n片，移动次数为f（n），显然f（1）=1，f（2）=3，f（3）=7，且f（k+1）=2×f（k）+1。此后不难证明f（n）=2n-1。

当n=64时，f（64）=264-1=18 446 744 073 709 551 615

假如每秒钟移一次，共需多长时间呢？一个平年365天有31 536 000秒，闰年366天有31 622 400秒，平均每年31 556 952秒，计算如下：

18 446 744 073 709 551 615÷31 556 952=584 554 049 253.855年

这表明，完成这些金片的移动需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。

汉诺塔问题的上述求解方法利用的是“递归”思想，递归就是把问题转化为规模缩小了的同类问题的子问题，然后递归调用函数（或过程）来求解原问题。求解汉诺塔的过程用一个简洁的递归程序即可实现。汉诺塔的求解计算在理论上是可行的，但由于时间复杂度问题，实际求解64个盘片的汉诺塔问题则并不一定可行。

3．国王婚姻问题——并行计算

很久以前，有一个酷爱数学的年轻国王，他聘请了当时最有名的数学家孔唤石当宰相。邻国有一位聪明美丽的公主，国王爱上了这位邻国公主，便亲自登门求婚。公主说：“你如果向我求婚，请你先求出48 770 428 433 377 171的一个真因子。一天之内交卷”。国王听罢，心中暗喜，心想：我从2开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？

国王十分精于计算，他一秒钟就算完一个数。可是，他从早到晚，共算了几万个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。

公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了”。国王立即回国，召见宰相孔唤石，大数学家在仔细地思考后认为这个数为17位，如果这个数可以分成两个真因子的乘积，则最小的一个真因子不会超过9位。于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏黄金万两。于是，国王发动全国上下的民众，再度求婚，终于取得成功。

在该故事中，国王采用了顺序求解的计算方式，所消耗的计算资源少，但需要更多的计算时间，而宰相孔唤石的方法则采用了并行计算方式。

并行计算是提高计算机系统数据处理速度和处理能力的一种有效手段，并行计算基本思想是：用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算将任务分离成了离散部分，有助于同时解决，从时间消耗上优于普通的串行计算方式，但这也是以增加了计算资源耗费所换得的。

4．旅行商问题——最优化思想

“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要去多个地点推销货物时，如何找到在每个地点去过一次且仅去过一次后再回到起点的最短路径，该问题规则虽然简单，但在地点数目增多后求解却极为复杂。

旅行商问题最简单的求解思路是枚举法，即列出每一条可供选择的路径，计算出路径长度后，从所有这些可供选择路径中选出一条最短的路径。这样的求解思路方法虽然简单，但当城市数目增多后却不一定可行。

当城市数目为n时，可供选择的组合路径数为（n-1）!。显然当n较小时，（n-1）!并不大，但随着城市数目的不断增加，组合路径数呈指数级数规律急剧增长。以20个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量为（20-1）!≈1.216×1017，数量之大，几乎难以计算出来，这就是所谓的“组合爆炸”问题，是一个典型的NP问题，目前计算机没有确定的高效算法来求解它。

2010年10月25日，英国伦敦大学皇家霍洛韦学院等机构研究人员的最新研究认为，在花丛中飞来飞去的小蜜蜂显示出了轻易破解“旅行商问题”的能力。研究人员利用人工控制的假花进行了实验，结果显示，不管怎样改变花的位置，蜜蜂在稍加探索后，很快就可以找到在不同花朵间飞行的最短路径，这是首次发现能解决这个问题的动物。研究报告认为，小蜜蜂显示出了轻而易举破解这个问题的能力，如果能理解蜜蜂怎样做到这一点，将有助于人们改善交通规划和物流等领域的工作，对人类的生产、生活将有很大帮助。

求解“旅行商问题”可采用最优化中的动态规划算法。最优化方法用于研究各种有组织系统的管理问题及其生产经营活动，对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。“旅行商问题”是最优化中的线性规划问题中的运输问题。最优化理论与方法也已成为了现代管理科学中的重要理论基础和不可缺少的方法，例如“旅行商问题”的求解方法可应用于如下实际问题：如何规划最合理高效的道路交通，以减少拥堵；如何更好地规划物流，以减少运营成本；如何在互联网环境中更好地设置节点，以更好地让信息流动等。

计算机的发展，归根结底是计算思维的传承与发扬，计算机从人工机械方式到动力机械方式，再到现在的电子器械方式，不仅是制造材料的进步，也是思维方式的进步。相信在不久的将来，计算机会成为结合众多学科交叉结合、继续传承和发扬计算思维的人类文明精灵，到那时，人类社会的文明程度必将会进入到一个史无前例的高度。