兩類在線算法問(wèn)題的研究.pdf

1、本文的研究對(duì)象——在線算法，是計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)、操作研究學(xué)中的一個(gè)基本主題。以下主要針對(duì)在線算法中的兩類典型問(wèn)題分別做了相應(yīng)研究。 一、移動(dòng)機(jī)器人在線構(gòu)建地圖的最優(yōu)探測(cè)法。 對(duì)復(fù)雜未知環(huán)境構(gòu)建地圖，是移動(dòng)機(jī)器人所面臨的一大問(wèn)題。通常忽略未知環(huán)境的幾何特征，將其抽象成未知無(wú)向連通圖，機(jī)器人只沿著圖的邊進(jìn)行搜索，并將走過(guò)每條邊的成本看成是1。機(jī)器人對(duì)一未知環(huán)境在線構(gòu)建地圖時(shí)，所有的邊至少都要走一遍，走過(guò)的總邊數(shù)越少越好，整

2、個(gè)探測(cè)過(guò)程中的成本用機(jī)器人走過(guò)的總邊數(shù)來(lái)表示。 對(duì)于一個(gè)完全未知的環(huán)境，將其抽象成未知無(wú)向連通圖G=（E，V），其中E為圖G的邊，V為圖G的頂點(diǎn)。從G中的一點(diǎn)S出發(fā)，限制移動(dòng)機(jī)器人最遠(yuǎn)能走r（如安全線或通信線）步（邊數(shù)）的范圍內(nèi)，基于深度受限剪枝生成子樹(shù)的方法，結(jié)合廣度優(yōu)先搜索和受限的深度優(yōu)先搜索染色策略，給出了對(duì)未知環(huán)境構(gòu)建完整地圖的有效算法，該算法的成本為｜E｜+0｜V｜。 二、單個(gè)批處理機(jī)器的在線任務(wù)安排問(wèn)題在批容

3、量受限制的單個(gè)批處理機(jī)器在線任務(wù)安排問(wèn)題中，所有待處理事件都是以在線方式動(dòng)態(tài)隨機(jī)到達(dá)的，所有事件的相關(guān)屬性在事件到達(dá)之前是未知的。其需要處理的時(shí)間也是未知的。問(wèn)題是如何安排這些未知的、隨機(jī)到達(dá)的工作，從而使整個(gè)任務(wù)安排用時(shí)最短，效率最高。 一臺(tái)批處理機(jī)器可以同時(shí)處理b個(gè)工作事件，一批待處理事件的處理時(shí)間用這一批中需要最長(zhǎng)處理時(shí)間的事件的處理時(shí)間來(lái)描述。在線任務(wù)安排的目標(biāo)是讓所有任務(wù)都被處理后，所用的總的處理時(shí)間跨度最小。在這篇文