智能调度系统学习报告

《智能调度系统学习报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、题目：人工智能调度系统院系名称：理工学院信科系专业班级：计科1101学号：2011110696李敏2011110698李红霞17/17智能调度---旅行员销售实例智能：人的智能是人类理解和学习事物的能力，或者说，智能是思考和理解的能力而不是本能做事的能力。人工智能：是研究和设计具有智能行为的计算机程序，以执行人或动物所具有的智能任务。智能调度技术：是根据现实遇到问题的诊断与预测，运用智能计算方法形成可行的方案，利用仿真技术进行多种调度方模拟分析，并实现对方案的跟踪管理。人工智能学家们曾经研究过若干组合

2、问题的求解方法。智能组合调度与指挥方法已被应用于汽车运输调度、列车的编组与指挥、空中交通管制以及军事指挥等系统。确定最佳调度或组合的问题是人们感兴趣的又一类问题。在这些问题中有几个（包括推销员旅行问题）是属于理论计算机科学家称为NP完全性一类的问题。他们根据理论上的最佳方法计算出所耗时间（或所走步数）的最坏情况来排列不同问题的难度。17/17一、图灵机计算机科学与人工智能之父——A.Turing(图灵１９１２－１９５４):１９３６年提出图灵机；１９６６年第一届图灵奖（侧重在计算机科学理论和软件方面）1

3、、1图灵机的形式化描述图灵机是一个五元组（Q，A，F，q0，qn），其中：Q是有穷个状态的集合；A是字母表，即符号的集合；q0∈Q是初始状态；qn∈Q是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；F是转移函数，即控制器的规则集合1.2计算“x+1”的图灵机目标：利用二进制来设计一个专门计算“x+1”的图灵机，要求计算完成时，读写头要回归原位状态集合K：{start，add，carry，noncarry，overflow，return，halt}；字母表∑：{0，1，*}；初始状态s：s

4、tart；停机状态集合H：{halt}；规则集合δ：17/171.3举例：“5＋1”的计算过程17/1717/17一、P与NP类问题一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。在图灵机计算模型下，这类问题的计算复杂性至今未知。为了研究这类问题的计算复杂性，人们提出了另一个能力更

5、强的计算模型，即非确定性图灵机计算模型，简记为NDTM(NondeterministicTuringMachine)。在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。2.1非确定性图灵机在图灵机计算模型中，移动函数δ是单值的，即对于Q´Tk中的每一个值，当它属于δ的定义域时，Q´(T´{L，R，S})k中只有唯一的值与之对应，称这种图灵机为确定性图灵机，简记为DTM(DeterministicTuringMachine)。非确定性图灵机（NDTM）：一个k带的非确定性图灵机M是一个7元组：

6、(Q，T，I，δ，b，q0，qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数δ具有不确定性，即对于Q´Tk中的每一个值(q;x1,x2,…,xk)，当它属于δ的定义域时，Q´(T´{L，R，S})k中有唯一的一个子集δ(q;x1,x2,…,xk)与之对应。可以在δ17/17(q;x1,x2,…,xk)中随意选定一个值作为它的函数值。2.2P类与NP类语言P类和NP类语言的定义：P={L

7、L是一个能在多项式时间内被一台DTM所接受的语言}NP={L

8、L是一个能在多项式时间内被一台NDTM所接受的

9、语言}由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。2.3NP完全问题的近似算法迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略：(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解一、旅行员问题3.1问题描述售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城

10、市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。17/17路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。设有p个城市，假设每两个城市之间都有直通通道，两个城市之间的路程已知，一个售货员要到每个城市推销产品，然后返