兩類在線算法問題的研究

1、蘭州理工大學碩士學位論文兩類在線算法問題的研究姓名：陳花申請學位級別：碩士專業(yè)：計算機軟件與理論指導教師：張遠平20090331兩類在線算泫問題的研究!寰I一：=一I皇曼!曼篁!!!曼曼皇詈!!!!!!!!!!曼曹AbstractOn—IinealgorithmistheobjectstudiedinthispaperItisalsoabasicthemeincomputerscience，economicsandoperationre

2、searchsystemThetwotypicalproblemsofon—linealgorithmareresearchedseparatelyasfoIlowsFirsttheoptimalon—lineexplorationmethodformapbuildingwithamobilerobot。TheprobIemfacedbyamobilerobotistoconstructacompletemapofanunknownen

3、vironmentThegeometricfeaturesoftheenvironmentareneglectedandtheenvironmentismodeledasanunknownconnectedundirectedgraphTherobotcanonlymovealongedgesofthegraphSupposethatthecostofeachedgetraversalis1Arobothastovisita11node

4、sandedgesofthegraph，usingasfewedgetraversalSaspossibleThecostofbuildingmapismeasuredbythenumberofedgestraversedduringtheexplorationInthiSpaperanunknownenvironmentismodeledasanunknownconnectedundirectedgraphG=(E，功，Eisthee

5、dgesnumberofG，VisthevertexhumberofGTherobotstartsatvertexS，andmovesnomorethantherangeof，stepsBasedontheapproachthatprunesatreewithaboundeddepth，combiningwiththestrategyofBFSandboundedDFScoloringmethodanefficientalgorithm

6、ofbuildingmapofunknownenvironmentiSpresentedThecostofthealgorithmiSlEfDI卅Second，theproblemofon—lineschedulingonasinglebatchprocessingmachine’Theproblemofonlinejobschedulingonasinglebatchprocessingmachinewithboundedbatchs

7、izeisattackedJobsarrivedynamicallyovertime，thecharacteristiesofjobsareunknownbeforetheirarrivalsAbatchprocessingmachinecanhandleupto6jobssimultaneouslyTheprocessingtimeofabatchisgivenbythelongestprocessingtimeofsomejobin