（计算机应用技术专业论文）r_时刻表求解时间规划问题.pdf

安徽大学硕十毕业论文 摘要 摘要 本文通过对时间规划中k 时刻表这个主题的深入探讨，以时间关系矩阵为基 础，给出了r _ 时刻表算法的详细步骤，并设计了一个通用的时间规划系统，将时 间规划应用于大学课程和田径运动会竞赛项目安排中，从中我们学习并了解了时 间规划的原理和机制。 时间规划是以时间关系约束作为推理的依据，给出各事件发生、结束时间的 时刻表。现实世界是个时空的世界，现实生活中的许多问题都属于时间规划问题。 r _ 时刻表是时间规划算法的种，它可以在若干存在关系约束的时间区间中找到 同时满足所有关系约束的规划方案。 本论文主要工作是。 在算法的实现过程中发现了算法些不完善的地方，通过实践给算法加入 一些功能对其进行了完善，给出了完善后的算法。在矩阵化简中，通过线性表记 录了简化时间矩阵和原时间关系矩阵的行列对应关系，在主算法中，通过线性表 记录了哪些区间端点对应同个相容子集，以便在输出r _ 时刻表时查找。 在完善的算法基础上，设计并实现了一个通用的时间规划系统，该系统可 以很好的完成关系矩阵构造、关系矩阵的简化和r f 时刻表的求解，说明了改进后 算法是有效可行的。 利用集合的性质，将多成份关系约束看成几个单成份时间关系约束并集， 我们给出了多成份关系约束的最优分解。在此基础上，给出了关系矩阵的构造、 关系矩阵的化简和求解r _ 时刻表的算法，该算法能给出r _ 时刻表或判断无解但计 算量未必一定收敛。 遗传算法是一种将生物进化原理应用到计算机上，用来寻找难解问题近似 解的一种全局优化搜索算法。我们尝试使用遗传算法来求解多成份时间关系下r - 时刻表，并给出了相应的算法，大大降低了多成份下求解r _ 时刻表的复杂度。 关键词：时间规划r 时刻表时间矩阵遗传算法 安徽火学硕士毕业论文 r 。时刻表求解时间规划问题 a b s t r a c t i nt h i sp a p e r ，w ef u r t h e rd i s c u s sr _ t i m e t a b ! eo f t i m ep r o g r a m m i n ga n d g i v et h e d e t a i l e da c c o u r l to f t h ea l g o r i t h m sb a s e do i lr e l a t i o n m a t r i xw e d e s i g nag e n e r a l s o f t w a r es y s t e mo f t e m p o r a lp l a n n i n ga n da p p l yi ti nt h ea r r a n g e m e n to f c a m p u s g a m ea n dc o l l e g ec o u r s ew ec a nl e a r na n du n d e r s t a n dt h ep r i n c i p l ea n dm e c h a n i s m f r o mt h e m t e m p o r a lp l a n n i n gi st h et i m e t a b l eo f e a c ha f f a i r o fs t a r ta n dt e r m i n a lt i m e a c c o r d i n ga sr e s t r i c t i o no f t i m er e l a t i o n t h er e a l i s t i cw o r l di sas p a c e t i m ew o r l d m a n yp r o b l e m si nt h er e a l i s t i cl i f eb e l o n gt oat e m p o r a lp l a n n i n gr _ t i m e t a b l ei so n e k i n do f p l a n n i n ga l g o r i t h m i tc a n g e tas c h e m em e e t i n ga l lr e l a t i o n - r e s t r i c t i o n m a i n j o bi nt h i sp a p e r ： t h r o u g hi m p l e m e n t i n gr _ t i m e t a b l ea l g o r i t h m w ef i n ds o m el i m i t a t i o na n d f a u l t i n e s sp l a c eo f i tt h r o u g hp r a c t i c e ，w ea d ds o m en e wf u n c t i o nt oi m p r o v e a l g o r i t h ma n dg i v et h ei m p r o v e da l g o r i t h mw h i l ep r e d i g e s t i n gr e l a t i o n m a t r i x ，l i n e a r l i s tr e c o r dt h ec o r r e s p o n d i n gr e l a t i o n sb e t w e e nr e d u c e dt e m p o r a l - m a t r i xa n do r i g i n a l t e m p o r a l m a t r i xi nm a i na l g o r i t h ml i n e a rl i s tr e c o r dt h a tc o m p a t i b l es u b s e ti n c l u d e p o i n t ，i no r d e rt os e a r c hw h e nr - t i m e t a b l ei so u t p u t b a s e do nt h ei m p r o v e da l g o r i t h m w ed e s i g na g e n e r a ls o f t w a r es y s t e mo f t e m p o r a lp l a n n i n gt h es o f t w a r es y s t e mc a nb eg o o da tc o n s t r u c t i n gr e l a t i o n m a t r i x ， p r e d i g e s t i n gr e l a t i o n - m a t r i xa n ds o l v i n gr t i m e t a b l e i ti sp r o v e dt h a tt h e i m p r o v e m e n to f t h ea l g o r i t h mi sf e a s i b l ea n de f f e c t u a l m a k i n gu s eo fa na g g r e g a t i v ep r o p e r t y w er e c o r dm u l t i - i n g e r d i e n tt i m e r e l a t i o na sm e r g i n gs e to f af e ws i n g l ei n g r e d i e n ta n dg i v eo p t i m a ld e c o m p o s i t i o n u n d e rm u l t i i n g e r d i e n tt i m er e l a t i o nw eg i v ea l g o r i t h mh o wt oc o n s t r u c t r e l a t i o n m a t r i x ，p r e d i g e s tr e l a t i o n - m a t r i xa n dg e tr _ t i m e t a b l e t h ea l g o r i t h mc a ng i v e r _ t i m e t a b l eo rj u d g en or e s u l t ，b u tc a l c u l a t i o nm a yb en o tc o n v e r g e n c e a g e n e t i ca l g o r i t h m ( g a ) i sao p t i m i z a t i o na n ds e a r c ha l g o r i t h mu s e dt of i n d i i 安徽大学硕士毕业论文 a b s t r a c t a p p r o x i m a t es o l u t i o n st od i f f i c u l t - t o - s o l v ep r o b l e m st h r o u g ha p p l i c a t i o no f t h e p r i n c i p l e so f e v o l u t i o n a r yb i o l o g yt oc o m p u t e rs c i e n c et h ee n do f p a p e r ，w eg i v e a l g o r i t h mh o wt os o l v er _ t i m e t a b l eu n d e rm u l t i i n g e r d i e n tt i m er e l a t i o nu s i n g g e n e t i ca l g o r i t h mi t sa d v a n t a g eg r e a t l yr e d u c e sc o m p l e x i t y k e yw o r d ：t e m p o r a lp l a n n i n g ，rt i m e t a b l e ，t e m p o r a l m a t r i x ，g e n e t i c a l g o r i t h m i j 安徽大学硕士毕业论文 r - 时刻表求解时问规划闭题 表索引 表2 - 1 基于区间时间逻辑和基于点时问逻辑的1 3 种关系7 表4 - 1 功能模块描述2 5 表4 - 2 计算机系课程关系一览表4 6 表4 - 3 课程之间的约束关系4 7 表4 4 项目约束关系一5 0 v 1 安徽大学硕士毕业论文 图索引 图索引 图2 - 1 时间关系的平面表示( 1 ) ，8 图2 2 时闯关系的平面表示( 2 ) 8 图2 3 点与区闻的关系9 图3 - 1 主算法流程图1 4 图3 - 2 构造关系矩阵流程图1 6 图3 3 事件关系2 0 图3 - 4 事件关系2 1 图4 1 顶层数据流图2 3 图4 2 子数据流图。2 3 图舢3 功能模块图2 4 图4 4e x c e l 表结构2 6 图4 5 输入向导一事件个数和事件名称2 8 图4 - 6 输入向导一设置事件关系3 0 图4 7 相容子集流程图3 9 图4 - 8 运算过程和结果4 3 图4 - 9 事件关系4 4 图4 1 0 事件关系4 5 图4 - l l 课程编排，4 8 图4 - 1 2 运动会项目编排5 2 图5 1 区间分解记录图，5 7 图5 2 遗传算法流程图6 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获健襄必天乎或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签氢欲但氏 签字日期多磷嘶 学位论文版权使用授权书 本学位论文作者完全了解煅炙孚有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权宴留袭幻昀以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：秀乏彬氏导师签名：彳家尚 签字日期：一声够喇日 。 签字日期： 卅年牛月哕日 学位论文作者毕、出去向： 工作单位 通讯地址 电话 邮编 安徽大学硕士毕业论文 第一章绪论 1 1 时间规划概述 第一章绪论 规划( p l a n n i n g ) - - 词在我们的日常理解中是指在行动之前拟订行动步骤，属 于人工智能研究范围。人工智能( a t ) d e 的规划问题大部分是n p 难题或n p 完全 问题。规划是人工智能研究领域较早发展起来的一个热门分支，由于其广泛的实 用性，受到研究者的高度重视。 规划过程是一种问题求解方法，一个规划系统我们可以认为就是一个问题求 解系统，若用它求解比较复杂的问题，即可求得一个动作序列，依次执行此动作 序列可以完成某一特定的具体任务，最终得到一个特定的目标。另一方面，就规 划这个词来说，其含义是指在求解实际问题时，执行一系列动作之前，事先指定 出求解过程的一系列步骤，即先作出规划，然后再付之实施。 时间规划是人工智能所涉及的特殊规划领域，它是以时间关系约束作为推理 依据的。时间规划是指：有一组与时间有关的事件或动作的集合，并给定一组约 束条件，要求在满足这些约束条件下，给出各事件发生、结束时间的时刻表。时 间规划问题分为只有时间先后关系约束的问题和既有时间先后关系又有时间宽 度约束的问题。 现实世界是一个时空的世界，人类任何活动都离不开时间的约束。现实生活 中有许多实际问题都属于时间规划问题，由于其广泛的使用性，所以已有一系列 的研究成果，并给出了一些好的模型。自7 0 年代初以来，时间规划发展历程中 的一些重要研究成果如下。 7 0 年代初，r e f i k e s ，m $ t e f i k ，e d s a c e r d o t i 等都先后讨论过时间规划问题 i t - 3 ，不过他们的理论都有一个共同的不足之处，即没有一个很好的明确的时间 模型，并且对两个事件之问的时间关系，只假设。在前”和“在后”两种简单情 况。而现实生活中一组事件之间的关系，不单纯为“前”和“后”的关系，所以 他们的方法能够处理问题的范围很小。 8 3 年sa v e r e 4 1 针对上述方法的缺陷，提出了一个时间规划的新模型，一个 关于包( p a c k a g e ) 的概念，所谓包是由两个元素“窗口w i n d o w ) 和“宽度 ( d u r a t i o n ) l 窭堡奎兰堡主兰兰兰堕奎坠堕i ! 墨塑堕塑望型塑垦 组成。 窗口是用二元组( e ，l ) 表示，其中e 表示包中事件最早可能发生的时间，l 表 示包中事件最迟可能发生的时间。“宽度”用一个实数表示，表示在包中的事件 发生的时间长度。 这个模型比上面只有“前”和“后”关系的模型进步了很多，它可以描述两 个事件之间的各种相互关系，并且记录了事件持续了多长时间，但仍有两个不足 之处。 首先是每个发生的事件要求落在给定的窗口上，即其发生的时间“基本”上 确定了。在处理具体问题时这个限制太强。如定制火车时刻表时，在定制之前我 们并不能指定某列火车一定要在指定的“窗口”中开始进行。故“窗口”的概念 在解决实际问题时还不是很好用。 其次，模型中用一个固定的正实数描述事件的时问宽度，这在实际问题中要 求也过严。因为实际中，事件的时间宽度往往只是给出一个范围，而不是一个准 确的数字。如一列火车开的快可能要1 2 个小时到，若开的慢可能要1 2 3 个小时才 到，即实际宽度应是在1 2 至1 2 a d , 时之间。 同年jfa l l e n 取i j a k o o m e n 睁1 0 1 提出时间世界模型( t e m p o f a lw o r l dm o d e l ) 来 描述时间规划问题。他克服了v e r e 模型中的两个不足之处，这个模型能比较全面 地反映各事件之问的时间关系，a l l e n 的时间世界模型是当前关于时间规划问题 比较好的模型之一。目前绝大多数研究者都是以a l l e n 的时间区间代数为研究出 发点，推导出一个时间关系矩阵，在此基础上锝到一个时刻表用于确定各个时区 的时刻。但a l l e n 利用这个模型提出的求解时间规划的“时间逻辑”方法并不是 很理想。 t s a n g ，e p k t 5 1 对a l l e n 的一套方法做了推广，提出“部分世界描述方法”( a p a r t i a lw o r l d d e s c r i p t i o na p p r o a c h ) 。t s a n g , e p k 使用搜索方法来求满足约束的 时刻表，但是仍未能克服其计算量大、计算方法复杂的缺点。 1 2 时间规划问题研究的意义 规划是大量现实问题的抽象，人工智能在解决规划问题时通常将规划变成某 种形式的推理。通过建立一种逻辑体系，使规划变成逻辑推理，而不是像运筹学 2 安徽大学硕士毕业论文第章绪论 那样的数值计算。在解决许多现实的规划问题中，时间是一个必需考虑的因素， 因为规划所涉及的各种事件都是在一定时间中产生，并在一定时间中消失。因此 在规划系统中应该把时间明显的表示出来。 我们将与时间相关的规划称为时间规划。在现实生活中常常会遇到时间规划 的相关问题，比如运动会的比赛项目安排，课程表的安排，生产计划安排，机器 人装配动作的自动生成以及运输调度的日程表制定等等。它的广泛使用性使得研 究该类问题具有更深的意义。 现实生活中很多规划问题所涉及的事件个数多，事件之间的关系复杂。人们 在面对复杂的、难于准确把握的闯题时候，通常是通过逐步尝试的办法，最终只 能达到有限合理的目标。通过对时间规划问题的研究，使得能通过计算机很好的 解决这类问题。为我们的生产，运输调度等给出更合理的安排，提高我们做事的 效率，降低生产成本。 1 3 时间规划的表示方法 有关时间规划中时间结构的表示方法主要有三种【6 】。 ( 1 ) 基于事件的时间逻辑( e v e n t - b a s e d t e m p o r a l l o e , i e ) ，即以事件作为时间的 摹本单元，来讨论不同事件之间在时间上的关系。 【2 ) 基于区间的逻辑结构( i n t e r v a l b a s e d ) ，即以时间区间作为时间的基本单 元，来讨论不同事件之间在时间上的关系。我们将事件a 与事件发生的时间区 间i 联系在一起，于是讨论不同事件之间的时间关系，就转化为讨论事件对应时 间区间之间的关系。 ( 3 ) 基于点的结构( p o i n t - b a s e d ) ，即以时间的点作为时间的基本单元，来讨论 不同事件之问在时间上的关系。一个区间由两个端点确定，于是两个时间区间之 间的关系就可用四个时间点之间的位置关系来确定，这称为基于点的时间逻辑。 设有两个事件i l 、h ，事件i l 、h 发生的时间区间分别为( a l ，b 1 ) ，( a 2 ，b 2 ) 。事 件1 1 、1 2 之间的关系可以用区间( a l ，b 1 ) 和( a 2 ，b 2 ) 之间的关系来表示，两区间之间的 关系有1 3 种情况。而区间( a l , b 0 和( a 2 血) 的关系可以用点a l 、b i 和点a 2 、b 2 之问 的关系来表示，两个点之间的关系有三种情况，即“ ”，“= ”，“ “这样我 们可以用两个点之间的简单关系来描述事件之间的约束关系，显然以上三种时问 安徽大学硕士毕业论文r 时刻表求解时间规划问题 结构是可以相互转换。 1 4 本论文的内容安排 第一章绪论，对时间规划问题进行了概述，介绍了时间规划问题已有的一些 重要研究成果，并讨论了这些成果的优点和不足之处。时间规划是人工智能所涉 及的特殊规划领域，表示方式主要有三种：基于事件的时间逻辑、基于区间的时 间逻辑和基于点的时间逻辑。 第二章，根据a l l e n 提出的时间世界模型，将事件与事件发生的时间区间i 联 系起来，并且规定了两个区间之间的1 3 种不同关系。在此基础上，介绍了时间规 划的两种表示方式，主要阐述了基于点关系的时间逻辑，和以此为基础如何构造 时间关系矩阵，用时间关系矩阵表示事件之间的约束关系。为下一章求解r _ 时刻 表奠定了理论基础。 第三章，以上一章构造关系矩阵理论为基础，在关系矩阵方法下，给出了求 解单成份关系r - 时刻表的算法。此方法求解的g _ b g n 表是只有时间关系先后约束 的时刻表。本章对其算法进行了较为详细的介绍和分析。 在实际应用中我们发现耻时亥4 表算法存在一定的局限性和不完善之处，如时 间关系矩阵的化简会破坏事件发生的时间区间和矩阵的对应关系，如不记录这种 变化，将无法得到区间端点在化简后关系矩阵中的位置；算法的时间复杂度较高； 事件之间关系约束较强等。 结合后面的实例，我们对r - 时刻表算法进行了深入的研究，并在原算法的基 础上，提出了记录、查找方法，并给出了改进后的r _ 时刻表算法。 第四章，基于完善后的r - 时刻表算法，设计了一个通用的时间规划应用软件， 用以完成事件基本信息、事件间约束条件的输入，关系矩阵的生成，时间关系矩 阵的化简，r - 时刻表的求解，结果显示等功能。初步形成了一个基于r - 时刻表算 法的时间规划软件。 在本章节的后续部分通过两个实例：高校课程编排和校园运动会项目编排， 对通用时间规划软件的实际运行效果进行考察，彳导到了基本令人满意的结果。 第五章，从上面两个实例我们可以看到，算法比较好的解决了只有关系约束 的单成份时间规划问题。但在使用时我们发现了一些不足之处，主要表现为该算 4 安徽大学硕士毕业论文第一章绪论 法只考虑事件之间的约束关系，并且要求时间关系约束是单成份的，算法的应用 范围受到限制。在本章中对算法进行改进，给出了多成份下r - 时刻表的求解算 法。对多成份下关系矩阵的构造和化简进行了详细的阐述。 遗传算法是一种通过将生物进化原理应用到计算机上用来寻找难解问题近 似解的启发式方法。遗传算法是一类特殊的进化算法。章节后续部分尝试利用遗 传算法来求解多成份时间关系下的r _ 时刻表，来解决约束条件太强的问题。将求 解关系矩阵中求到相容子集中元素的个数作为染色体的适应度，算法的终止条件 是根据关系矩阵求得的相容子集中元素个数等于事件个数的2 倍。 第六章，在本文的最后总结和展望中，对全文的工作进行了总结。并就以后 可以继续开展的研究方向加以说明。 安徽大学硕士毕业论文r 时刻表求解时间规划问题 第二章时间规划的关系矩阵表示法 目前有很多学者1 7 , 训叼对时间关系进行了研究，绝大多数研究都是以a l l 【1 o 】 的时间区间代数为研究出发点，推导出一个时间关系矩阵，在此基础上得到一个 时刻表用于确定各个时区时刻。 a l l e n 提出的时间世界模型是当前提出的关于时问规划问题中较好的模型， 此模型的优点在于可以描述很广泛的类时间规划问题，克服了过去一些时间规 划模型的局限性，然而这种模型是利用时间关系约束的传播规律来求解的，使得 规划时计算量较大，有时求不到满足时间约束的时刻表。但a l l e n 将事件与事件 发生的时间区间i 联系起来，并且规定了两个区间之间的1 3 种不同关系，而这 1 3 种关系能比较全面地反映各事件之间的时间关系。关系矩阵方法就是基于这 1 3 种不同关系基础上建立起来的一种求解时刻表的有效方法。 2 1 基于区间的逻辑结构 a l l e n 将事件与事件发生的时间区间i 联系起来，于是讨论不同事件之同的 约束关系就转化为对事件相应区间之间关系的讨论。 a l l e n 规定了两个区间之间的不同关系有1 3 种，如表2 - 1 。为了进行区间之 间的时间关系的推理，他g i 入所谓“时间逻辑”的概念，并证明1 3 种不同关系 均可用“遇”( m e e t ) 来定义。还引入关于“m ”运算的五条公理，又给出三个区 间i ，j ，k 之间的约束传播规律，如i ( ) j 且j ( ) k ，得i ( ) k 。于是三区间之间 的可能关系共有1 3 1 3 = 1 6 9 种情况。 在此模型上，主要利用三区间的传递律来求解对各事件均一致满足的时刻 表。但对一组事件来说，即使任意三个事件都是一致的，仍不能保证所有事件的 时间关系都是一致的时刻表存在。 2 。2 基于点关系的时间逻辑 一个时间区间可由两个端点来确定，于是两个时间区间之间的关系就可以用 四个端点之间的相对位置关系来确定，这称为基于点的时间逻辑。假设在一维时 6 安教大学硕士毕业论文第二章时问规划的关系矩阵表示法 问轴上两个时刻点a 、b ，固定一个时刻点b ，通过比较另一个时刻点a 相对于固 定时刻点b 的位置关系，可以容易的得出a 、b 之间的关系有三种： 1 当时刻a 在时刻b 之前时，称时刻a 超前( b e f o r e ) 时刻b ，记为a b ； 我们将区间之间的关系用四个时间端点之间的关系来描述，两者之间的关系 如表2 - 1 所示。i 和j 表示区间，a l 和b l 表示i 的两个端点，a 2 和b 2 表示j 的两 个端点。 表z 一1 基于区间时闻逻辑和基于点时间逻辑的1 3 种关系 t a b l e 2 - 1t h e t h i r t e e nr e l a t i o n so f i n t e r v a l b a s e d t e m p o r a l l o g i ca n d p o i n t - b a s e d t e m p o r a l l o g i c 符号基于区阀基于点的逻辑：图形表示“”事律i 和事件i 的多g 表刁舶逻辑 一z j = ：。 e = 系，。：。；， i ( ) j a l a 2 ，b l b 2 l 一一，1 _ j i 先于j 发生 m l ( m ) j b l = a 2 j 紧跟i 后发生 0 i ( o ) ja l a 2 b l b 2 一1 j - l i 与重叠j f i i ( f i ) j a l a 2 b l = b 2c ；三兰j i 先，i 与j 同时结束 d 。i ( d ，) ja l a ： b 2 b l 广l 一1 i 包含j s i ( s ) ja l = a ： b l b 2 1 同时开始，i 先结束 l ( = ) j a l = a 2 且b l = b 2e 兰三三|i 与j 同始同终 s i i ( s ) j a l = a 2 b 2 b l - - - r o 同时开始，j 先结束 d 1 ( d ) ja 2 a 1 b t b 2 r l 1 j 包含i f i ( f ) j a 2 a l b 产b 2 r 1 j 先，同时结束 o l1 ( o ) j a 2 a l b 2 b l r r 一_ j 重叠l m i ( m 。) ja 2 ) ja 2 b 2 a l a j 、b 2 a 2 ，所以我们用平面上位 于直线x = y j ：方的点表示区间，见图2 1 。我们将区间( a 2 ，b 2 ) 固定在x 和y 轴上，a l 与1 2 的关系在x 轴上表示，b l 与1 2 的关系用y 轴表示，那a l l 在直线研上方不同区 域代表i l 与1 2 之间的不同关系，我们就可以用平面来表示两区间之间的1 3 种关系， 7 安徽大学硕士毕业论文r 时刻表求解时问规划问题 详见图2 - 1 。 在图2 1 中，两个区间为： i l = ( a 1 ，b o ，a i b 1 ；i 爿a 2 ，嗡，a 2 b 2 。 四条射线为： l l ：x = b 2 l 2 ：y = b 2 ；l 3 ：x = a 2 ；l 4 ：y 2 a 2 。 把上半平面划分为六个区间，从下而上，从左而右依次代表 ；把四条射线划分为六个线段，从下而上，从左面右依次代表m ，s ，s i ， f ，1 1 1 。；和一个交叉点，代表：。 从图2 一l 中我们可以看出，i l 在直线x = y 上方任何区域，i t 在x 轴上的投影 a l 与区间( a 2 ，b 2 ) 酗j 关系只有五种情况：a l a 2 、a l = a 2 、a 2 a 一m ( i d ，所以矩阵m 是反对称矩阵。 安徽大学硕士毕业论文第二章时间翔划的关系矩阵表示法 由此可得，n 个事件间的关系可用一个2 n x 2 n 的关系矩阵来表示，对n 个事件 的操作和运算也就转化为对此矩阵的操作和运算。有关矩阵的操作运算已有很多 算法，从而使我们对事件之间的复杂关系操作转化为我们熟悉的矩阵运算。 2 4 本章小结 本章将事件与事件发生的时间区间联系起来，介绍了时间规划中时间结构的 两种表示方法，主要阐述了基于点关系的时间逻辑，和以此为基础构造时间关系 矩阵，用矩阵来表示一组事件间的关系。下一章将在时间关系矩阵基础上，给出 仅仅有时间关系约束单成份的r - 时刻表求解算法。 安徽大学硕士毕业论文 r j l 于刻表求解时间规划问题 第三章r - 时刻表算法 在人工智能中，时间规划问题可大致描述为：有一个与时间有关的“事件” ( “动作”) 集合，并且给出一些约束条件。现在要求在满足所有时间关系约束的 条件下，给出各事件发生与结束的时刻表安排，这种时刻表称为r _ 时刻表。 时间规划问题分为只有时间先后关系约束的问题和既有时间先后关系又有 时间宽度约束的问题，r _ 时刻表算法是求解只有时间先后关系约束的问题。 本章所讨论的r _ 时刻表的算法是以上一章介绍的关系矩阵表示法为基础， 单成份前提下的r - 时刻表。事实上r _ 时刻表就是一个一致满足所有时间关系约 束的端点集合的有序划分。 3 1 相关概念 定义3 1 ( 有序划分) 设t = x l ，x 2 一，x f 。) 是一有限集合，e _ e l ，c 2 ，e 。) 是t 的一个划分。在e 中定义序关系如下： 若x 岛，y e e j ，则x y i j 。记作x ( y ( e ) 。在时间关系矩阵中表示，在一 维时间轴上，时刻x 超前时刻y 。 若x ，y e i ，则记作x y ( e ) 。在时间关系矩阵中表示，在一维时间轴上时刻 x 和时刻y 是同一时刻的点。 则称划分e 连同上面定义的序为t 的一个有序划分。 定义3 2 ( r - 时刻表) 设m 是时间规划的关系矩阵，t = t “t 2 ，t 2 n 是对应 的1 3 个时间区间的端点时刻的集合。令e - e l ，c 2 ，e n i 是t 的一个有序划分， 且满足 任意x ，y e t ，x y ( e ) = 一lm ( x ，y ) 任意x ，y e t ，x y ( e ) = ，om ( x ，y ) 其中m ( x ，y ) 是m 中对应于x ，y 的元素，则称有序划分e 是m 的一个r 一时 刻表，即e 是n 个事件的2 n 个端点排列的先后顺序，也就是发生的先后顺序。 显然，将t 的元素按e 的序，安排在时间轴上( x y ( e ) 的x ，y 放在同一点上) ， 即得到一个一致满足所有时间关系约束的时间安排。 安徽大学硕士毕业论文第三章r 刻表算法 设m 。= ( m ( i ，1 ) ，m ( i ，2 ) ，m ( i ，2 n ) ) 是m 中第i 行行向量。令 a l j - - - m m t l t em ( i ，j ) ) 得到 a i 爿a i l a i 2 一，a t 2 n ) 若a i 的每个分量均s 0 ，则称m i 是非正行向量。其实m j 表示时间区间端点i 和 其它时间区间端点之间的关系。a i 的每个元素s o ，表示时问区间端点i 在其它时 间区间端点先或同时发生，即在有序划分中应排在前面的点。 设m 是关系矩阵，j ( m ) 表示m 的行号集合。设f = ( f i ，f 2 ，f m ) 是j ( m ) 的一个 给定的有序子集。 以m ( f ，i ) 表示在m 中将v j f i ，6 一， 的i 行( 列) 都删去后所得到的子矩 阵。例如，设f = l ，2 ，5 ，3 ，) ，则m ( f ，3 ) 即为将m 矩阵中第1 ，2 ，5 行( 歹n ) 都删 去后余下的子矩阵。 我们用j ( m ( f ，i ) ) 表示子矩阵m ( f ，i ) 的行号集合。 3 2r _ 时刻表算法 3 2 1 主算法1 1 l l 算法如下： 第一步：输入事件之间的关系，构造m ( m 为关系矩阵) ，若失败停止，否 则进入第二步。 第二步：求出m 的简化矩阵，若失败停止。不然得简化矩阵，仍记为m 。 令s = 0 ，j 习( m ) ，进入第三步。 第三步：若j 一巾，则输出s ，称s 为m 的r - 时刻表，算法结束。否则，进 人第四步。 第四步：求m 的所有非正行向量，并用c 表示非正行向量的行号集合。若c = 由，失败，停止。否则进人第五步。 第五步：求e 的相容子集，若失败，停止。否则得e 的一相容子集，记为d 。 进入第六步。 第六步：将m 中v j e d 的第j 行( 列) 删去，得到的子矩阵记为m l 。令m 一 安徽大学硕士毕业论文r - 时刻表求解时阃规划问题 m l ，j d ，d ，s + - ( s ，d ) ，返回第