006队列2.ppt

电路布线复杂度分析 网格编号过程需耗时 O (m2 ) 重构路径的过程需耗时 Q（PathLen） * * * * 数字化图像是一个m×m 的像素矩阵。 单色图像中，每个像素的值要么为 0，要么为1。 值为0的像素表示图像的背景，而值为1的像素则表示图元上的一个点，我们称其为图元像素。 如果一个像素在另一个像素的左侧、上部、右侧或下部，则称这两个像素为相邻像素。 识别图元就是对图元像素进行标记，当且仅当两个像素属于同一图元时，它们的标号相同。 6.4.3识别图元 识别图元 * * * * 一间工厂由m台机器组成。 工厂中所执行的每项任务都由若干道工序构成，一台机器用来完成一道工序，不同的机器完成不同的工序。 一旦一台机器开始处理一道工序，它会连续不断地进行处理，直到该工序被完成为止。 6.4.4工厂仿真 * * 对于一项任务中的每道工序来说，都有两个属性：一是工时（即完成该道工序需要多长时间），一是执行该工序的机器。 一项任务中的各道工序必须按照一定的次序来执行。一项任务的执行是从处理第一道工序的机器开始的，当第一道工序完成后，任务转至处理第二道工序的机器，依此进行下去，直到最后一道工序完成为止。 当一项任务到达一台机器时，若机器正忙，则该任务将不得不等待。 工序属性 * * 在工厂中每台机器都可以有如下三种状态：活动、空闲和转换。 在活动状态，机器正在处理一道工序。 在空闲状态机器无事可做。 在转换状态，机器刚刚完成一道工序，并在为一项新任务的执行做准备，比如机器操作员可能需要清理机器并稍作休息等。每台机器在转换状态期间所花费的时间可能各不相同。 机器状态 * * 当一台机器可以处理一项新任务时，它可能需要从各个等待者中挑选一项任务来执行。 在这里，每台机器都按照FIFO的方式来处理等待者，因此每台机器旁的等待者构成了一个FIFO队列。 在其他类型的工厂中，可以为每项任务指定不同的优先权，当机器变成空闲时，从等待者中首先选择具有最高优先权的任务来执行。 任务队列 * * 为了让顾客满意，希望尽量减少任务在机器队列中的等待时间。 如果能够知道每项任务所花费的等待时间是多少 并且知道哪些机器所导致的等待时间最多 就可以据此来改进和提高工厂的效能。 目标 * * 在对工厂进行仿真时，采用一个模拟时钟来进行仿真计时，每当一道工序完成或一项新任务到达工厂时，模拟时钟就推进一个单位。在完成老任务时，将产生新的任务。每当一道工序完成或一项新任务到达工厂时，称发生了一个事件(event)。 另外，还存在一个启动事件(start event)，用来启动仿真过程。 工厂仿真实现 * * 三台机器M1、M2和M3的转换状态所花费的时间分别为2、0和1。 因此，当一道工序完成时 机器M1在启动下一道工序之前必须等待2个时间单元 机器M2可以立即启动下一道工序 机器M3必须等待1个时间单元 示例 * * 每道工序用形如(machine，time)的值对来描述。 各项任务的长度分别为7，6，8和4。 四项任务的特征 * * 仿真 * * 2号和4号任务在第12时刻完成，1号任务在第15时刻完成，3号任务在第19时刻完成。 由于2号任务的长度为6，而它的完成时刻为12，所以2号任务在队列中所花费的等待时间为12 - 6 = 6个时间单元。 类似地，4号任务在队列中的等待时间为12 -4 = 8个时间单元，1号和3号任务的等待时间分别为8和11个时间单元。 总的等待时间为33个时间单元。 结果 * * 队列的逻辑结构和实现方式 火车车厢重排 电路布线 工厂仿真 第六章 总结 作业 假设一数列的输入顺序为1234,若采用队列结构调整数列输出顺序，设计算法求出所有可能的输出序列(合法序列)。 * * * 第 6 章 队列(QUEUES) * 本章内容 6.1 抽象数据类型 6.2 公式化描述 6.3 链表描述 6.4 应用 * * 队列的实现 队列的应用 本章重点 * 6.4 应用 6.4.1 火车车厢重排 6.4.2 电路布线 6.4.3 图元识别 6.4.4 工厂仿真 * 6.4.1 火车车厢重排 缓冲铁轨位于入轨和出轨之间 入轨右端-缓冲铁轨 入轨右端-出轨 缓冲铁轨右端-出轨 禁止 : 将车厢从缓冲铁轨移动至入轨 从出轨移动车厢至缓冲铁轨 铁轨Hk 为可直接将车厢从入轨移动到出轨的通道 * 车厢移动到缓冲铁轨的原则 车厢c应移动到这样的缓冲铁轨中： 该缓冲铁轨中现有各车厢的编号均小于c；如果有多个缓冲铁轨都满足这一条件， 则选择一个左端车厢编号最大的缓冲铁轨； 否则选择一个空的缓冲铁轨（如果有的话）。 * * 从前至后依次检查入轨上的所有车厢。 如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。 如果