智能调度系统学习报告.doc

题目：人工智能调度系统院系名称：理工学院信科系专业班级：计科1101学 号：2011110696 李敏2011110698 李红霞 智能调度 - 旅行员销售实例 智能：人的智能是人类理解和学习事物的能力，或者说，智能是思考和理解的能力而不是本能做事的能力。 人工智能：是研究和设计具有智能行为的计算机程序，以执行人或动物所具有的智能任务。 智能调度技术：是根据现实遇到问题的诊断与预测，运用智能计算方法形成可行的方案，利用仿真技术进行多种调度方模拟分析，并实现对方案的跟踪管理。 人工智能学家们曾经研究过若干组合问题的求解方法。智能组合调度与指挥方法已被应用于汽车运输调度、列车的编组与指挥、空中交通管制以及军事指挥等系统。 确定最佳调度或组合的问题是人们感兴趣的又一类问题。在这些问题中有几个（包括推销员旅行问题）是属于理论计算机科学家称为NP完全性一类的问题。他们根据理论上的最佳方法计算出所耗时间（或所走步数）的最坏情况来排列不同问题的难度。1、 图灵机计算机科学与人工智能之父A. Turing (图灵): 年提出图灵机；年第一届图灵奖（侧重在计算机科学理论和软件方面）1、1图灵机的形式化描述图灵机是一个五元组（Q，A，F，q0，qn ），其中：Q 是有穷个状态的集合；A 是字母表，即符号的集合；q0Q是初始状态；qnQ 是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；F是转移函数，即控制器的规则集合1.2计算“x+1”的图灵机目标：利用二进制来设计一个专门计算“x+1”的图灵机，要求计算完成时，读写头要回归原位 状态集合K：start，add，carry，noncarry，overflow，return，halt；字母表：0，1，*；初始状态s：start；停机状态集合H：halt；规则集合：1.3举例：“51”的计算过程2、 P与NP类问题 一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。 在图灵机计算模型下，这类问题的计算复杂性至今未知。 为了研究这类问题的计算复杂性，人们提出了另一个能力更强的计算模型，即非确定性图灵机计算模型，简记为NDTM(Nondeterministic Turing Machine)。 在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。2.1非确定性图灵机 在图灵机计算模型中，移动函数是单值的，即对于QTk中的每一个值，当它属于的定义域时，Q(TL，R，S)k中只有唯一的值与之对应，称这种图灵机为确定性图灵机，简记为DTM(Deterministic Turing Machine)。 非确定性图灵机（ NDTM ）：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，b，q0，qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数具有不确定性，即对于QTk中的每一个值(q;x1,x2,xk)，当它属于的定义域时，Q(TL，R，S)k中有唯一的一个子集(q;x1,x2,xk)与之对应。可以在(q;x1,x2,xk)中随意选定一个值作为它的函数值。2.2 P类与NP类语言 P类和NP类语言的定义：P=L|L是一个能在多项式时间内被一台DTM所接受的语言 NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。2.3 NP完全问题的近似算法迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略：(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解3、 旅行员问题3.1问题描述售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。设有p个城市，假设每两个城市之间都有直通通道，两个城市之间的路程已知，一个售货员要到每个城市推销产品，然后返回原出发地，问这个售货员应该如何选择路线，能使每个城市都经过一次且仅一次，并且行程最短，这就是著名的旅行售货员问题，也即货郎担问题。用图论的术语来描述旅行售货员问题：即在一个正权完全图中寻找一个具有最小权的哈密顿回路，对于此问题，由于完全图中必然存在哈密顿回路，那么目前可以用于求解的方法有枚举法，分枝限界法，这两种算法可以求得此问题的精确解，但到目前为止，还没有求解这一问题的有效算法，我们可以利用分支限界法，回溯法求解此问题的近似解，以求得与最优解最为接近的解。3.2问题的求解方法1）枚举法 枚举法就是一一列出问题的所有解，然后进行比较，取权值最小的解为最优解，这种方法虽然可以求取问题的最优解，但是我们知道旅行售货员问题是对完全图而言的，对有N个结点的完全图，存在个不同的哈密顿回路，如果采用枚举法求解，则要对上述数目的不同的哈密顿回路一一进行运算且需要相互之间比较，当N取值较小时，此种求解方法没有任何问题，但若N值较大时，计算量则以级数级别递增，况且没有有效的算法，所以在计算机中也较难实现，故枚举法在大多数的实际应用中是不可取的。2）回溯法旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成1，2，n的所有排列的递归算法perm类似。开始时，相应的排列树由的所有排列构成。在递归算法backtrack中，当i=n时，当前的扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点到顶点的边和从顶点到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时算法还需要判别这条回路的费用是否优于当前已经找到的最优回路的费用bestc。如果是，则必须更新当前的最优值bestc和当前的最优解bestx。 当时，当前的扩展结点位于排列树的第层。图G中存在从顶点 到达顶点的边时，构成图G中的一条路径，且当的费用小于当前最优值时算法进入排列树的第i层；否则，则剪去相应的子树。算法中用变量cc记录当前路径的费用。3）分枝限界法的基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树时表示问题解空间的一棵有序树，常见的由子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法的主要不同在于它们对当前扩展结点所采用的扩展方式。在分支限界法中，每一个活结点只有一次机会成为扩展检点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点总，导致不可行的解或者非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后从活结点表中取下一结点成为当前扩展结点，并重复上述扩展过程。这个过程一直持续到找到所需的解或活结点表空为止。从活结点表中选择下一扩展结点的不同方式将导致不同的分支限界法。最常见的有以下两种方式。（1）队列式（FIFO）分支限界法 队列式分支限界法将活结点表组织成一个队列，并按照队列的先进先出FIFO(first in first out )原则选取下一个结点为当前扩展结点。（2） 优先队列式分支限界法 优先队列式的分支限界法将活结点表组织成一个优先队列，并按照优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。优先队列中规定的结点优先级常用一个与该结点相关的数值p表示。结点优先级的高低与p值的大小相关。最大优先队列规定p值较大的结点优先级较高。在算法是现实通常用最大堆来实现最大优先队列，用最大堆的removeMax运算抽取堆中下一个结点成为当前扩展结点，体现最大效益优先的原则。类似的，最小优先队列规定p值较小的结点优先级较高。在算法实现时通常用最小堆来实现最小优先队列，用最小堆的removeMin运算抽取堆中下一个结点成为当前的扩展结点，体现最小费用优先的原则。用优先队列式分支限界法解具体问题式，应该根据具体问题的特点确定选用最大优先队列或者最小优先队列表示解空间的活结点表4）普利姆算法求最小生成树的主要思想此算法是普利姆与1957年提出的一种构造最小生成树的算法，主要思想是：假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从U=u0(u0V),TE=开始，重复执行下述操作：在所有uU,vV-U的边（u,v）E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，E）为N的最小生成树。 最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。3.3、算法分析(1)枚举法 枚举法是最差的一种算法，即将所有可能的结果都排列一次，并比较解与当前最优解的大小，因此其时间复杂度很高，在实际应用中当结点数很多时不可取。(2)回溯法 如果不考虑更新bestx所需的计算时间，则算法backtrack需要计算时间。由于算法backtrack在最坏的情况下可能需要更新当前最优解次，每次更新bestx需计算时间，从而整个算法的计算时间复杂性为。(3)分支限界法 由于是NP问题，其时间复杂度很高，当相对于回溯法而言，分支限界法剪掉了一些不必要的计算，效率有很大的提高，但是在最坏的情况下可能需要满历所有的结点。此时的时间复杂度也是很高的。（4）普里姆算法分析在其算法中，首先，初始化一个图给参数g,然后定义closedge用于存放最小生成树中的顶点，调用函数Locate()求出起点u在顶点向量表中的位置，初始化U=u，利用for循环对V-U中的顶点i,初始化，再利用for循环找n-1条边，其中，调用函数Minium()求出辅助数组中权值最小的边,并将其在辅助数组中的相应位置返回到主调函数中，最后，输出起点、终点和权值。voidMiniSpanTree_PRIM(MGraphG,Vertexu)inti,j,k;minsideclosedge; k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj; closedgek.lowcost=0;/*将顶点vk加入生成树中*/ printf(最小代价生成树的各条边为:n);for(i=1;iG.vexnum;+i)k=minimum(closedge,G); printf(%s-%s)n,closedgek.adjvex,G.vexsk);/*输出最小边及权值*/ closedgek.lowcost=0; for(j=0;jG.vexnum;+j)if(G.arcskjclosedgej.lowcost)strcpy(closedgej.adjvex,G.vexsk); closedgej.lowcost=G.arcskj;/*修改权值域*/分析上述算法，假设网中有n个点，则第一个初始化的循环语句的频率为n，第二个循环语句的频率为n-1。其中两个内循环：其一是在closedgek.lowcost中求最小值，其频率为n-1,其二是重新选择具有最小代价的边，其频率是n。由此，普利姆算法的时间复杂度为O(n2),与网中边数无关3.4、满足三角不等式的旅行售货员问题对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。void approxTSP (Graph g)1）选择g的任一顶点r；2）用Prim算法找出带权图g的一棵以r为根的最小生成树T；3）前序遍历树T得到的顶点表L；4）将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。四、前序遍历 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。若二叉树为空则结束返回，否则：（1）访问根结点。（2）前序遍历左子树。（3）前序遍历右子树 。前序遍历需要注意的是：遍历左右子树时仍然采用前序遍历方法。如右图所示二叉树前序遍历结果：ABDECF已知后序遍历和中序遍历，就能确定前序遍历五、哈密顿回路天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不一定是双向的。比如AB不允许，但BA是允许的。换一种说法，对于一个给定的网络，确定起点后，如果存在一条路径，最后又回到原出发点,且满足每个顶点只被访问一次的情况下能穿过这个网络，我们就说这个网络存在哈密顿路径。1、判断哈密顿图是较为困难的.哈密顿图的充分条件和必要条件在无向简单图G=中½V½³3,任意不同结点，则G是哈密顿图.（充分条件，