本文的研究对象——在线算法,是计算机科学、经济学、操作研究学中的一个基本主题。以下主要针对在线算法中的两类典型问题分别做了相应研究。一、移动机器人在线构建地图的最优探测法。对复杂未知环境构建地图,是移动机器人所面临的一大问题。通常忽略未知环境的几何特征,将其抽象成未知无向连通图,机器人只沿着图的边进行搜索,并将走过每条边的成本看成是1。机器人对一未知环境在线构建地图时,所有的边全少都要走一遍,走过的总边数越少越好,整个探测过程中的成本用机器人走过的总边数来表示。对于一个完全未知的环境,将其抽象成未知无连通图G=(E,V),其中E为图G的边,V为图G的顶点。从G中的一点S出发,限制移动机器人最远能走r(如安全线或通信线)步(边数)的范围内,基于深度受限剪枝生成子树的方法,结合广度优先搜索和受限的深度优先搜索染色策略,给出了对未知环境构建完整地图的有效算法,该算法的成本为|E|+O|V|。二、单个批处理机器的在线任务安排问题在批容量受限制的单个批处理机器在线任务安排问题中,所有待处理事件都是以在线方式动态随机到达的,所有事件的相关属性在事件到达之前是未知的。其需要处理的时间也是未知的。问题是如何安排这些未知的、随机到达的工作,从而使整个任务安排用时最短,效率最高。一台批处理机器可以同时处理b个工作事件,一批待处理事件的处理时间用这一批中需要最长处理时间的事件的处理时间来描述。在线任务安排的目标是让所有任务都被处理后,所用的总的处理时间跨度最小。在这篇文章中,通过对部分正在处理事件重新安排的方式,给出了一种批容量受限制的单个机器在线任务安排算法,通过证明得知此算法的竞争率(在线情况下的执行结果与离线情况下的最优执行结果的比值即为竞争率)是3/2。