数学建模中用到的启发式算法
- 格式:doc
- 大小:65.50 KB
- 文档页数:8
初中数学建模的若干简要案例1.找出一个公园内最短游览路径的问题假设一个公园有多个景点,每个景点之间有不同的距离,我们希望找到一条最短的路径,使得可以在最短时间内游览完所有的景点。
我们可以将每个景点表示为节点,距离表示为边,然后利用图论中的最短路径算法(如迪杰斯特拉算法)来解决这个问题。
2.优化一家快递公司的邮件投递路径假设一个快递公司需要投递邮件到不同的区域,每个区域的邮件数不同,我们希望找到一条最优的路径,使得快递员可以在最短时间内投递完所有的邮件。
我们可以将每个区域表示为节点,不同区域之间的距离表示为边,然后利用图论中的最短路径算法或者启发式算法(如A*算法)来解决这个问题。
3.设计一个购物车的最佳装载方案假设一个网上购物平台需要将一些商品装载到购物车中,每个商品有不同的体积和重量,而购物车有一定的容量限制。
我们希望找到一个最佳的装载方案,使得购物车可以装载尽可能多的商品。
我们可以将每个商品表示为节点,商品之间的限制条件(如体积和重量限制)表示为约束条件,然后利用线性规划算法(如简单的背包问题)来解决这个问题。
4.优化一条生产线的生产效率假设一个工厂有多个生产环节,每个生产环节有不同的效率和成本,我们希望找到一个最优的生产线配置方案,使得生产效率最高,成本最低。
我们可以将每个生产环节表示为节点,不同生产环节之间的依赖关系和成本表示为边,然后利用图论中的最优路径算法(如最小生成树算法)来解决这个问题。
5.设计一个最优的课程表假设一个学校有多个班级和多个教师,每个班级需要上不同的课程,每个教师可以同时教授多个班级的课程,我们希望找到一个最优的课程表,使得教师的利用率最高,学生的课程安排最优。
我们可以将每个班级和教师表示为节点,教师的教学能力和班级的需求表示为边的权重,然后利用图论中的最大流算法或者启发式算法(如基因算法)来解决这个问题。
这些案例都是初中数学建模的常见问题,通过数学建模的方法,可以帮助我们解决这些实际问题,提高问题的解决效率和准确性。
数学建模离散优化模型与算法设计数学建模在离散优化问题的解决中起着重要的作用。
离散优化问题是指在给定的离散集合上寻找最优解的问题,一般包括整数规划、组合优化、排班优化等。
数学建模则是将实际问题转化为数学模型的过程,在离散优化问题中,需要设计相应的数学模型,并通过算法求解最优解。
离散优化问题的数学模型通常包括目标函数和约束条件两个方面。
目标函数用于衡量解的优劣程度,约束条件则是对解的限制条件。
通过定义合适的目标函数和约束条件,可以将实际问题转化为一个数学优化问题。
在构建数学模型时,需要考虑实际问题的特点。
例如,在排班优化问题中,需要考虑员工的需求以及工作时间的限制,将员工的排班安排转化为一个数学模型。
在整数规划问题中,需要考虑变量的取值范围,将问题转化为整数规划模型。
在数学建模的基础上,需要设计相应的算法来求解离散优化问题。
常见的算法包括贪心算法、动态规划算法、遗传算法等。
选择合适的算法取决于问题的规模和特点。
贪心算法是一种简单而直观的算法,每一步都选择当前最优的解来构建解空间,在一些问题上具有较好的效果。
动态规划算法则通过将问题划分为一系列子问题,并保存子问题的解,从而避免重复计算,提高计算效率。
遗传算法则是一种模拟生物进化的算法,通过遗传、交叉和变异等操作来最优解。
除了算法设计,还需要考虑算法的优化。
例如,在排班优化问题中,可以通过合理的约束条件和目标函数设计,来减少空间,提高算法效率。
此外,还可以使用启发式算法等方法来加速过程。
总之,数学建模在离散优化问题的解决中起着重要的作用。
通过合适的数学模型和算法设计,可以有效地求解离散优化问题,并得到最优解。
在实际应用中,还需要考虑问题的特点来选择合适的算法,并通过优化算法提高求解效率。
带时间窗的车辆路径问题(VRPTW)是一种重要的组合优化问题,在许多实际的物流配送领域都有着广泛的应用。
该问题是对经典的车辆路径问题(VRP)进行了进一步扩展,考虑了车辆在每个节点进行配送时的时间窗约束。
VRPTW的数学建模和求解具有一定的复杂性,需要综合考虑车辆的路径规划和时间限制方面的因素。
本文将对带时间窗的车辆路径问题进行数学建模,并探讨一些常见的求解方法和算法。
一、问题描述带时间窗的车辆路径问题是一个典型的组合优化问题,通常可以描述为:给定一个具有时间窗约束的有向图G=(V,E),其中V表示配送点(包括仓库和客户),E表示路径集合,以及每个节点v∈V都有一个配送需求q(v),以及一个时间窗[Tmin(v),Tmax(v)],表示了可以在节点v进行配送的时间范围;另外,给定有限数量的车辆,每辆车的容量有限,且其行驶速度相同。
问题的目标是设计一组最优的车辆路径,使得所有的配送需求都能够在其对应的时间窗内得到满足,且最小化车辆的行驶距离、行驶时间或总成本,从而降低配送成本和提高配送效率。
二、数学建模针对带时间窗的车辆路径问题,一般可以采用整数规划(IP)模型来进行数学建模。
以下是一个经典的整数规划模型:1. 定义决策变量:设xij为车辆在节点i和节点j之间的路径是否被选中,若被选中则为1,否则为0;di表示节点i的配送需求量;t表示车辆到达每个节点的时间;C表示车辆的行驶成本。
2. 目标函数:目标是最小化车辆的行驶成本,可以表示为:minimize C = ∑(i,j)∈E cij*xij其中cij表示路径(i,j)的单位成本。
3. 约束条件:(1)容量约束:车辆在途中的配送总量不能超过其容量限制。
∑j∈V di*xij ≤ Q, for i∈V(2)时间窗约束:Tmin(v) ≤ t ≤ Tmax(v), for v∈Vtij = t + di + dij, for (i,j)∈E, i≠0, j≠0(3)路径连通约束:∑i∈V,x0i=1; ∑j∈V,xji=1, for j∈V(4)路径闭合约束:∑i∈V xi0 = ∑i∈V xi0 = k其中k表示车辆数量。
数学建模大作业习题答案数学建模大作业习题答案作为一门应用数学课程,数学建模在现代科学研究和工程技术中具有重要的地位和作用。
通过数学建模,我们可以将实际问题转化为数学模型,从而利用数学方法进行分析和求解。
在数学建模的学习过程中,我们经常会遇到一些习题,下面我将为大家提供一些数学建模大作业题目的答案,希望能对大家的学习有所帮助。
1. 题目:某城市的交通拥堵问题解答:针对这个问题,我们可以采用图论的方法进行建模和求解。
首先,我们将城市的道路网络抽象为一个图,图的节点表示交叉口,边表示道路。
然后,我们可以给每条边赋予一个权重,表示道路的通行能力。
接着,我们可以使用最短路径算法,比如Dijkstra算法,来计算从一个交叉口到另一个交叉口的最短路径,从而找到最优的交通路线。
此外,我们还可以使用最小生成树算法,比如Prim算法,来构建一个最小的道路网络,以减少交通拥堵。
2. 题目:某工厂的生产调度问题解答:对于这个问题,我们可以采用线性规划的方法进行建模和求解。
首先,我们可以将工厂的生产任务抽象为一个线性规划模型,其中目标函数表示最大化生产效益,约束条件表示生产能力、物料供应和市场需求等方面的限制。
然后,我们可以使用线性规划求解器,比如Simplex算法或内点法,来求解这个线性规划模型,得到最优的生产调度方案。
此外,我们还可以引入一些启发式算法,比如遗传算法或模拟退火算法,来寻找更好的解决方案。
3. 题目:某股票的价格预测问题解答:对于这个问题,我们可以采用时间序列分析的方法进行建模和求解。
首先,我们可以将股票的价格序列抽象为一个时间序列模型,比如ARIMA模型。
然后,我们可以使用历史数据来拟合这个时间序列模型,并进行参数估计。
接着,我们可以利用这个时间序列模型来预测未来的股票价格。
此外,我们还可以引入其他的预测方法,比如神经网络或支持向量机,来提高预测的准确性。
通过以上的例子,我们可以看到,在数学建模的过程中,我们需要将实际问题抽象为数学模型,然后利用数学方法进行分析和求解。
无人机调度是一个复杂的数学问题,涉及到无人机飞行控制、路径规划、任务分配等多个方面。
下面我将尝试构建一个简化的数学模型,来描述无人机调度问题。
假设我们有n个无人机,每个无人机都有一定的飞行能力(如航程、速度、载荷等),并且需要完成m个任务。
每个任务都有一定的时间和位置要求。
我们的目标是通过最优的无人机调度,使得所有任务都能在规定时间内完成,同时尽可能地提高无人机的利用率。
我们可以将这个问题视为一个组合优化问题,可以使用启发式算法(如遗传算法、模拟退火算法等)进行求解。
以下是一个简化的数学模型:1. 变量定义:x[i][j]表示第i架无人机是否执行第j个任务,其中x[i][j]=1表示执行,x[i][j]=0表示不执行。
2. 目标函数:总时间最短:min∑[任务所需时间]3. 约束条件:(1)无人机数量限制:∑[i=1]ni=n(总共有n架无人机)(2)任务数量限制:∑[j=1]mj≤m(总共有m个任务)(3)每个任务只能由一架无人机执行:∑[i=1]xi[j]=1(j=1,2,...,m)(4)无人机的飞行范围和时间限制:对于每一架无人机和每一个任务,都需要满足相应的飞行范围和时间要求。
这个模型只是一个简化的版本,实际情况可能更加复杂。
例如,无人机之间的协同、干扰、通信等问题都需要考虑。
此外,还需要考虑任务优先级、安全因素、环境因素等其他因素。
因此,在实际应用中,还需要根据具体情况进行适当的调整和优化。
无人机调度问题的数学建模是一个非常有挑战性的问题,需要综合考虑多个因素。
通过建立合理的数学模型,可以更好地理解和解决这个问题,为无人机在实际应用中的调度和控制提供理论支持。
同时,随着无人机技术的不断发展,无人机调度问题也将不断演变和优化,为未来的智能无人机系统提供更多的可能性。
货运车物流运输计划问题在整数线性规划的基础上建立适当的模型、再运用分支定界法找到满足约束条件的较优变量,同时比较两种算法的迭代次数和运行时间,为进一步提高算法的利用率提供了依据。
最后通过MATLABGUI做成软件模拟在不同配置下相对应的分配方案,在总费用最小的前提下,程序运行时间短、效率高、能够较精确快速的找到合适的解决方案。
通过分析相应的整数线性规划建立相关的数学模型最后通过软件计算得到理想的效果,但是考虑到装箱调度决策过程中有多种可能,保证所有运输任务完成的情况下分配尽可能少的车辆来运输,因此,我们选择在货运车尽可能满载的情况下的分配方案。
这样可以减程序中少大量的矩阵运算和程序运行时间以及变量的迭代次数。
随着变量个数的增多,约束条件下不能得到较优的目标值,因此我们采用分支定界法先定出可选择的分配方案,再在优化的分配方案中找出相对较优的分配方案,例如运用整数线性规划得到不同车配置方案,运用分支定界法改变约束条件得到结果,在有路径的约束条件下我们运用两阶段法考虑整个分配方案。
先考虑第一阶段数量上的优化再考虑第二阶段路径上的优化。
运用逐步调优的策略在相同路程下就不优先考虑路径的优化,进一步调整配置方案。
在给定装配任务和分配任务的同时我们运用关联分类器先按题目要求将两张表建立关联,通过所给轿用车型的长、宽、高建立一个分类器。
按照表二中长、宽、高的不同分类分为12类,根据调度经验改用启发式算法将分类数降低至10类。
在满足题目要求的前提下我们采用货运车车型混装的形式,在一定程度上减少货运车的使用数量。
从而达到最充分的发挥资源的效能去获取最佳的经济效益。
对整车装箱调度问题进行研究从而降低运输成本具有一定的意义。
1、问题重述智能装载的问题描述:在一个配送中心,有N件货物需要分别配送至目的地A,B,C……,可以使用M辆车。
问如何规划车辆的配送路线,以及如何合理分配车辆的货物装载情况,提高车辆的实载率,减少车辆的数量。
数学建模在旅游规划中的应用随着人们生活水平的提高和旅游业的蓬勃发展,越来越多的人选择旅行作为放松和休闲的方式。
然而,随之而来的问题是如何高效地规划旅游路线,使得旅行者能够在有限的时间内尽可能多地游览目的地,同时又能享受到旅行的乐趣。
数学建模在旅游规划中的应用正是为了解决这一问题而发展起来的一种研究方法。
本文将介绍数学建模在旅游规划中的应用,并从旅游路线规划和旅游时间优化两个方面进行讨论。
一、旅游路线规划旅游路线规划是一项复杂而困难的任务,尤其是在目的地众多、时间有限的情况下。
数学建模为我们提供了一种系统而有效的解决方案。
首先,我们可以将每个旅游目的地看作图中的节点,而节点之间的连接则表示不同目的地之间的交通和距离关系。
通过构建一个旅游目的地网络,我们可以利用图论中的算法来寻找最短路径,从而确定一条最优的旅游路线。
例如,可以使用迪杰斯特拉算法来计算旅游路线中的最短路径,以确保在有限的时间内尽可能多地游览目的地。
其次,我们还可以考虑到不同目的地之间的旅游资源差异和游客的偏好因素,从而进一步优化旅游路线。
通过对游客的偏好和目的地资源进行评价和打分,我们可以使用启发式算法来确定一个旅游路线,使得游客能够在有限时间内游览到他们最感兴趣的目的地,从而提高旅行的满意度。
二、旅游时间优化除了旅游路线规划,数学建模还可以帮助我们优化旅游时间,以便更好地利用有限的假期时间。
首先,我们可以使用数学模型来确定最佳的出发时间。
通过分析历史数据和旅游景点的人流情况,我们可以建立一个预测模型,以预测不同时间段内的游客数量和拥堵程度。
这样,我们就可以选择在游客较少、拥挤程度较小的时间段出发,从而避免拥堵和浪费时间。
其次,我们还可以使用数学模型来优化每个景点的停留时间。
通过分析不同景点的游览时间和游客评价,我们可以建立一个评估模型,以评估不同旅游景点对游客满意度的贡献度。
通过优化每个景点的停留时间,我们可以使得游客在有限的时间内尽可能多地享受到旅行的乐趣。
2020(旅游行业)最佳旅游线路数学建模随着旅游行业的不断发展,如何挖掘和设计最佳的旅游线路成为了一项非常重要的任务。
在这方面,数学建模可以提供一些有效的方法和工具,帮助旅游公司和旅游从业者寻找最佳旅游线路,提高旅游体验质量。
本文将探讨如何应用数学建模来设计最佳旅游线路。
1. 数据收集与处理要设计最佳旅游线路,首先需要收集和处理大量的相关数据,包括旅游景点的信息、交通路线和时间表、住宿和餐饮等方面的数据。
这些数据可以通过网络搜索、问卷调查、实地考察等方式获取,并用Excel或其他数据处理软件进行整理和分析。
在处理数据的过程中,需要注意数据的准确性和完整性,同时考虑到数据的局限性和不确定性。
2. 构建旅游网络模型根据收集到的数据,可以构建旅游网络模型,将旅游景点和交通路线连接起来,并计算出各景点之间的交通距离和时间。
在建模过程中,可以采用图论、网络分析等方法。
通过旅游网络模型,可以分析不同旅游线路的可行性和效益。
3. 旅游线路规划在旅游网络模型的基础上,可以使用启发式算法或优化算法等方法来设计最佳旅游线路。
其中,启发式算法包括贪心算法、模拟退火算法、遗传算法等,能够有效地寻找最优解,但需要一定的计算资源和时间。
优化算法包括线性规划、整数规划、动态规划等,计算方法简单,但只能找到次优解。
通过旅游线路规划,可以实现旅游资源的最优配对,减少行车时间和费用,提高旅游效益和用户体验。
4. 评估和优化设计完成旅游线路后,需要对其进行评估和优化。
评估的主要指标包括旅游成本、旅游时间、旅游景点的质量和数量等。
根据不同的评估指标,可以进行多目标的优化,以得到最优的旅游线路。
在优化过程中,可以根据用户的反馈和评价进行调整和改进,不断提升旅游线路的质量和吸引力。
符号回归算法原理简介符号回归算法(Symbolic Regression)是一种机器学习方法,旨在从给定的数据样本中发现并表示出数学表达式。
与传统的回归算法不同,符号回归不仅可以帮助我们理解数据之间的关系,还可以给出更加准确和解释性强的模型。
在本文中,我将介绍符号回归算法的原理,并对其应用和优势进行讨论。
1. 算法原理符号回归算法通过搜索算法探索数学表达式的空间,以找到最佳的模型。
它通过基因编码的方式表示数学表达式,并使用遗传算法进行搜索和优化。
符号回归算法需要定义一个函数空间,其中包含了可能的数学表达式。
可以选择基本的数学运算符(如加法、减法、乘法和除法),以及一些常用的数学函数(如指数函数、对数函数等)。
这样的函数空间将定义了可能的模型空间。
算法通过种群编码的方式表示候选解。
种群是由一组个体组成的,每个个体都是一个数学表达式的编码。
通过交叉、变异等遗传操作,种群逐代地进化,以找到最佳的个体表达式。
算法使用适应度函数对个体表达式进行评估和排序。
适应度函数可以根据拟合程度、复杂度等准则来定义。
个体表达式得分越高,表示其与数据样本的拟合越好。
2. 应用和优势符号回归算法在多个领域都有广泛的应用,包括数学建模、数据挖掘、工程设计等。
它具有以下几个优势:2.1 发现隐含规律:符号回归算法可以挖掘数据背后的隐含规律和关系。
它不仅可以预测未知的数据点,还可以揭示数据变量之间的内在联系。
2.2 解释性强:符号回归模型给出的数学表达式具有很高的解释性。
相比于黑盒模型(如神经网络),符号回归算法可以给出易于理解和解释的数学公式。
2.3 模型优化:符号回归算法采用遗传算法进行优化,能够找到最佳的数学模型。
它可以自动进行特征选择和模型构建,减少人工干预的需求。
2.4 非线性建模:符号回归算法可以处理非线性问题,适用于各种复杂的数据集。
它可以自由组合基本的数学运算符和函数,以适应不同的数据特征。
3. 观点和总结从符号回归算法的原理和应用来看,它在数据建模和分析中具有一定的优势。
mathorcup数学建模题目数学建模是运用数学方法与技巧来解决实际问题的过程,不仅需要数学知识的深度理解和灵活应用,还需要在实际问题中进行建立模型、求解和分析的能力。
数学建模题目通常来源于工程、科学研究以及社会实践中的实际问题,对于参与数学建模竞赛的学生来说,题目的难度和复杂性也会较高。
下面将给出两个数学建模题目,并介绍相关的参考内容。
一、题目:某物流公司的配送问题某物流公司需要设计一个有效的配送方案,使得货物能够以最短的时间送达各个客户,同时要考虑车辆的装载容量和配送距离的限制,为了提高效率,还需考虑多个物流中心的选择和货物配送路线的规划。
参考内容:1. 车辆路径规划算法:可以使用启发式搜索算法(如A*算法)、模拟退火算法、遗传算法等来求解车辆的最佳路径规划问题。
2. 车辆装载问题:可以使用整数规划、动态规划等方法来解决车辆的装载问题,以最大化每次装载的货物数量。
3. 多物流中心选择:可以使用多指标决策模型,综合考虑物流中心的地理位置、服务能力、成本以及客户需求等因素来选择最佳的物流中心。
4. 路线规划算法:可以使用图论算法(如Dijkstra算法、Floyd算法、网络流算法等)来求解货物配送的最短路径问题。
5. 模拟实验与算法验证:可以通过建立数学模型,使用某个具体案例进行模拟实验,从而验证算法的有效性和可行性。
二、题目:某医院急诊科的医疗资源优化问题某医院急诊科需要合理安排医疗资源,以提高医院的服务效率和患者满意度,同时要考虑医护人员的工作强度和患者的病情紧急程度,需要设计一个合理的医疗资源优化方案。
参考内容:1. 医疗资源需求预测:可以使用时间序列分析、回归分析等方法来预测医疗资源的需求,以便合理安排医护人员和设备的调度。
2. 医疗资源调度算法:可以运用离散事件仿真、排队论等方法来设计医疗资源的调度策略,以最小化患者等待时间。
3. 人员任务分配问题:可以运用整数规划、图论算法等方法来合理安排医护人员的工作任务,以保证每个人员的工作强度平衡。
广告投放问题的数学建模及算法研究一、引言广告投放是现代营销中非常重要的一环。
正确的广告投放可以有效提高品牌知名度和销售额。
然而,广告投放并非简单的直接付款投放广告,而是需要通过科学方法来制定投放策略和优化方案,以达到最优效果。
数学建模和算法研究在这个过程中发挥着重要的作用。
本文就广告投放问题的数学建模及算法研究进行探讨,希望为广告投放领域的从业者提供一些有用的思路和方法。
二、广告投放问题的数学建模广告投放问题通常可以转化为一种带约束的优化问题:给定一定的投放预算和一些投放渠道,如何安排投放计划,以达到最大化目标(如点击量、转化率等)并满足预算和渠道投放限制。
具体来说,我们可以将广告投放问题建模为一个线性规划问题。
假设有m个渠道,每个渠道都有一个各自不同的点击率和转化率,那么我们可以用下面这样的公式来表示每个渠道的效果:效果 = 点击率 x 转化率然后我们定义x1, x2, ..., xm为每个渠道的投放数量,那么每个渠道的总效果可以表示为:总效果 = x1 x 点击率1 x 转化率1 + x2 x 点击率2 x 转化率2 + … + xm x 点击率m x 转化率m我们的目标是最大化总效果,并同时满足预算和每个渠道的最小和最大投放限制。
具体而言,我们可以把上述目标转化成线性规划问题的形式:最大化:总效果 = x1 x 点击率1 x 转化率1 + x2 x 点击率2 x 转化率2 + … + xm x 点击率m x 转化率m约束条件:1. 总投放额度不超过总预算:x1 + x2 + … + xm <= 预算2. 每个渠道的最小投放限制: xi >= 最小投放量i,i = 1,2,…,m3. 每个渠道的最大投放限制: xi <= 最大投放量i,i = 1,2,…,m上述线性规划问题可以用已有的优化算法进行求解,得到最优解,即最大化效果的投放方案。
三、广告投放问题的算法研究1. 简单贪心算法最简单的广告投放算法是贪心算法。
数学建模常用模型方法总结无约束优化线性规划连续优化非线性规划整数规划离散优化组合优化数学规划模型多目标规划目标规划动态规划从其他角度分类网络规划多层规划等…运筹学模型(优化模型)图论模型存储论模型排队论模型博弈论模型可靠性理论模型等…运筹学应用重点: ①市场销售②生产计划③库存管理④运输问题⑤财政和会计⑥人事管理⑦设备维修、更新和可靠度、项目选择和评价⑧工程的最正确化设计⑨计算器和讯息系统⑩城市管理优化模型四要素:①目标函数②决策变量③约束条件④求解方法(MATLAB--通用软件 LINGO--专业软件)聚类分析、主成分分析因子分析多元分析模型判别分析典型相关性分析对应分析多维标度法概率论与数理统计模型假设检验模型相关分析回归分析方差分析贝叶斯统计模型时间序列分析模型决策树逻辑回归传染病模型马尔萨斯人口预测模型微分方程模型人口预测控制模型经济增长模型Logistic 人口预测模型战争模型等等。
灰色预测模型回归分析预测模型预测分析模型差分方程模型马尔可夫预测模型时间序列模型插值拟合模型神经网络模型系统动力学模型(SD)模糊综合评判法模型数据包络分析综合评价与决策方法灰色关联度主成分分析秩和比综合评价法理想解读法等旅行商(TSP)问题模型背包问题模型车辆路径问题模型物流中心选址问题模型经典 NP 问题模型路径规划问题模型着色图问题模型多目标优化问题模型车间生产调度问题模型最优树问题模型二次分配问题模型模拟退火算法(SA)遗传算法(GA)智能算法蚁群算法(ACA)(启发式)常用算法模型神经网络算法蒙特卡罗算法元胞自动机算法穷举搜索算法小波分析算法确定性数学模型三类数学模型随机性数学模型模糊性数学模型。
启发式搜索 "启发"( heuristic)是关于发现和发明规则及方法的研究。在状态空间搜索中, 启发式被定义成一系列规则, 它从状态空间中选择最有希望到达问题解的路径。 人工智能问题求解者在两种基本情况下运用启发式策略: 1.一个问题由于在问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断即是一例。所给出的一系列症状可能有多个原因; 医生运用启发搜索来选择最有可能的论断并依此产生治疗的计划。视觉问题又是一例。看到的景物经常是模糊的, 各个物体在其连接、范围和方向上可以有多个解释。光所造成的幻觉加大了这些模糊性, 视觉系统可运用启发式策略选择一给定景象的最有可能解释。 2.一个问题可能有确定解, 但是求解过程中的计算机代价令人难以接受。在很多问题(如国际象棋)中, 状态空间的增长特别快, 可能的状态数随着搜索的深度呈指数级增长、分解。在这种情况下, 穷尽式搜索策略, 诸如深度优先或广度优先搜索,在一个给定的较实际的时空内很可能得不到最终的解。 启发式策略通过指导搜索向最有希望的方向前进降低了复杂性。通过仔细考虑, 删除某些状态及其延伸, 启发式算法可以消除组合爆炸, 并得到令人能接受的解。 然而, 和发明创造的所有规则一样, 启发式策略也是极易出错的。在解决问题过程中启发仅仅是下一步将要采取措施的一个猜想。它常常根据经验和直觉来判断。由于启发式搜索只有有限的信息,诸如当前Open表中状态的描述,要想预测进一步搜索过程中状态空间的具体的行为很难办到。一个启发式搜索可能得到一个次最佳解, 也可能一无所获。这是启发式搜索固有的局限性。这种局限性不可能由所谓更好的 启发式策略或更有效的搜索算法来消除。 启发式策略及算法设计一直是人工智能的核心问题。博奕和定理证明是两个最古老的应用: 二者都需要启发式知识来剪枝以减少状态空间。显然, 检查数学领域中每一步推理或棋盘上每一步可能的移动是不可行的。启发式搜索常常仅是实践中的解答。 近来, 专家系统的研究把启发式策略作为问题求解的一个重要部分。当一个专家解决问题时, 他检查所获取的信息并作出决定。实际上, 专家用来解决问题的"拇指法则"很大程度上是启发式的。 这些启发性知识被专家系统的设计者提取出来并形成规则。 通常启发式算法由两部分组成: 启发方法和使用该方法搜索状态空间的算法。本章先介绍最好优先搜索的算法, 再讨论启发式算法的设计和评估。 在一字棋游戏中(图4.5), 穷尽搜索的组合数很大。第一步移动共有九种移法 , 每一种又有八种对应走法……依次类推, 这个问题在穷尽搜索策略下需考虑9!个状态。 根据对称性可以减少搜索空间的数目。棋盘上很多构造是等价的。譬如, 第一步实际上只有三种移法, 角、边的中央以及网络正中。在状态空间的第二层上, 由对称性可进一步减少到12×7!种。在图5.1 中可见到该状态空间比最初的状态空间要小, 但它在扩展过程中还要继续分解。 然而, 一个简单的启发式策略几乎可以整个地消除复杂的搜索过程。首先, 将棋子移到棋盘上×有最多的赢线的点。最初的三种状态显示在图5.2中。 若两种状态有相等的赢的机率, 取其中的第一个。这样的话,可设计一种算法(完全实现启发式搜索), 它选择并移到具有最高启发值的状态。在这种情况下, ×占椐网络的中间点, 其它的各种状态都不再考虑, 它们的延伸状态同时也给消除了。如图5.3 所示三分之二的状态空间就这样给剪枝了。 第一步走完后, 对方只能有两种走法(见图5.3)。无论选择哪种走法,我方均可以通过启发式搜索选择下一步可能的走法。在搜索过程中, 每一步只需估价一下单个节点的子结点; 不需要强力搜索。图5.3 显示了游戏前三步简化了的搜索过程。每种状态都标记了它的启发值。 要精确地计算待检查的状态的数目比较难, 但可以大致计算它的上限。一盘棋最多走九步, 每步的下一步平均有四、五种走法。这样大约就是4.5×9, 近40种状态, 比9!改善了很多。
5.1 启发信息和估计函数 人工智能的核心课题是问题求解。所谓"问题求解"就是在广义图中寻找一条从初始状态出发, 到达目标状态的解树。例如旅行问题是解决从出发点到达目的地的路线和工具问题; 机器人装配机器, 就是给出把一堆零件变成一台机器的一系列操作; 定理证明就是寻找一条从前提条件到达结论的通路等等。 在实际解决一个具体问题时, 人们常常把一个具有复杂联系的实际问题抽象化,保留某些主要因素, 忽略掉大量次要因素, 从而将这个实际问题转化成具有明确结构的有限状态空间问题, 这个空间中的状态和变化规律都是已知的有限集合, 因此可以找到一个求解该问题的算法。 然而, 在智能活动中使用最多的不是具有完备性的算法, 而是不一定完备的启发式方法。其原因有二: 首先, 大多数情况下, 智能系统不知道与实际问题有关的全部信息, 因而无法知道该问题的全部状态空间, 不可能用一套算法来求解其中的所有问题, 这样就只能依靠部分状态空间和一些特殊的经验性规则来求解其中的部分问题。 其次, 有些问题在理论上存在求解算法, 但是在工程实践中, 这些算法不是效率太低, 就是根本无法实现, 为了提高解题的效率, 不得不放弃使用这些算法, 而求助于一些经验性的启发式规则。 例如在博弈问题中, 计算机为了保证最后胜利, 可以将所有可能的走法都试一遍, 然后选择最佳走步。这样的算法是可以找到的, 但计算所需的时空代价十分惊人。就可能有的棋局数讲, 一字棋是9!=3.6×105, 西洋跳棋是1078, 国际象棋是10120, 围棋是10761。假设每步可能选择一种棋局, 用极限并行速度(10-104年/步)计算, 国际象棋的算法也得1016年即1亿亿年才可以算完, 而我们已知的宇宙史才 100亿年! 由此看来, 启发式的问题求解, 不仅在实践上是需要的, 而且在理论上也是必不可少的。 对问题空间进行搜索时, 提高搜索效率需要有和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。有两种极端的情况: 一种是没有任何这种控制性知识作为搜索的依据, 因而搜索的每一步完全是随意的, 如随机搜索; 另一种是有充分控制性知识作为依据, 因而搜索的每步选择都是正确的, 这种搜索叫最佳搜索。一般情况是介于二者之间, 这些控制性信息反映在估价函数之中。 估价函数的任务就是估计待搜索结点的重要程度, 给它们排定次序。估价函数f(x)可以是任意一种函数, 如有的定义它是结点x处于最佳路径上的概率, 或是x结点和目标结点之间的距离, 或是x格局的得分等等。一般来说, 估价一个结点的价值, 必须综合考虑两方面的因素: 已经付出的代价和将要付出的代价。在此, 我们把估价函数f(n)定义为从初始结点经过n 结点到达目标结点的最小代价路径的代价估计值, 它的一般形式是: f(n)=g(n)+h(n) 其中g(n)是从初始结点到n的实际代价, h(n)是从n到目标结点的最佳路径的估计代价, 主要是h(n)体现了搜索的启发信息。因为实际代价g(n)可以根据生成的搜索树实际计算出来, 而估计代价h(n)却依赖于某种经验估计, 它来源于我们对问题的解的某些特性的认识, 这些特性可以帮助我们更快地找到问题的解。 一般地, 在f(n)中, g(n)的比重越大, 越倾向于广度优先搜索方式; h(n)的比重越大, 越倾向于深度优先搜索方式。 g(n)的作用一般是不可忽略的, 因为它代表了从初始结点经过n 到达目标结点的总代价估值中实际已付出的那一部分。保持g(n)项就保持了搜索的广度优先趋势, 这有利于搜索的完备性, 但影响搜索的效率。在特殊情况下, 如果只希望找到达到目标结点的路径而不关心已付出的代价, 则g(n)的作用可以忽略。另外, h(n)> >g(n)时, 也可以忽略g(n), 这时有f(n)=h(n), 这有利于搜索的效率, 但影响搜索的完备性。 给定一个问题后, 根据问题的特性和解的特性, 可以有多种方法定义估价函数, 用不同的估价函数指导搜索, 其效果可以相差很远。因此,必须尽可能选择最能体现问题特性的, 最佳的估价函数。
5.2 启发式搜索算法 5.2.1 局部择优搜索法(瞎子爬山法) 实现启发式搜索最简单的方法是瞎子爬山法(hill climbing)。 瞎子爬山法在搜索过程中扩展当前结点并估价它的子结点。最优的子结点被选择并进一步扩展; 该子结点的兄弟结点和父结点都不再保留。当搜索达到一种状态, 该状态比它的所有子结点都要好, 则搜索停止。瞎子爬山法可以这样理解──一个盲人急切地想登上山顶, 他总是沿着最陡的山路向上爬, 直到再不能找到新的路径。瞎子爬山法有这样一个缺陷: 一个错误的启发知识可能导致搜索无法沿着正确的路径前进, 从而增加了搜索的深度, 甚至是无穷尽地搜索。由于瞎子爬山法不保存所走过的结点信息, 故瞎子爬山算法无法修正错误的路径。 瞎子爬山法还可能在一个局部的最佳点上停止。当搜索到一个结点, 它的估计代价比任一个子结点都要小, 则算法结束。如果此时并不是目标状态, 而只是一个局部最优结点, 则该算法就不能得到目标解。因此, 在一个限定的环境下, 瞎子爬山法可能会极大地提高搜索效率, 但是对于整个搜索空间, 就有可能无法得到最佳解。重排九宫游戏就是一个突出的例子。为了将一个特定的格局移到它的目标位置上, 常常需要移动已经在其目标位置上的将牌。这对于完成拼图是必要的, 但它显然暂时恶化了拼板上的状态。由于"更好"并不是"最好", 瞎子爬山法无法区别局部和全局最优解。处理这个问题时有许多种方法, 譬如随时地修正估价函数来突破局部最优的限制。但是总的来说, 没有一种方法能保证瞎子爬山法的最佳效率。下面 介绍一个瞎子爬山法的例子──跳棋程序。 在人工智能中, Samuel的跳棋程序最早应用该方法。在跳棋程序中, 不仅运用了启发式搜索, 还实现了简单的学习功能。 跳棋程序中根据几个不同启发值的总和来估算棋局的状态: ∑aixii 其中xi是棋局的一系列特征, 如残局优势、残局棋子力量分布, 中心点位置