Syftet med online graf prospektering problem är att besöka alla noder i en given graf och komma tillbaka till start noden med den minsta totala passage kostnaden. Till skillnad från den klassiska Traveling Salesperson Problem, information om grafen ges på nätet. När en online algoritm (kallas en sökare) besöker en nod v, då det lär sig information om noder och kanter i anslutning till v. Sökaren måste bestämma vilken nod att besöka nästa beroende på partiell och ofullständig information om grafen som den har fått i sin sökning process. Algoritmens godhet utvärderas genom konkurrensanalysen. Om inmatningsgrafer som ska utforskas är begränsade till träd, den djup-första sökningen alltid returnerar en optimal tur. Men om grafer har cykler, problemet är icke-trivial. I detta dokument behandlar vi två enkla fall. Först behandlar vi problemet på enkla cykler. Nyligen, Asahiro et al. visade att det finns en 1,5-konkurrenskraftig online-algoritm, medan ingen online-algoritm kan vara (1,25 − )-konkurrenskraftig för någon positiv konstant. I det här dokumentet ger vi en optimal online-algoritm för detta problem; nämligen, vi ger en 1+ 3 2 ( 1.366)-konkurrenskraftig algoritm, och bevisa att det inte finns någon ( 2 − )-konkurrenskraftig algoritm för någon positiv konstant. Dessutom ser vi problemet med oviktade diagram. Vi ger också ett optimalt resultat, nämligen att vi ger en 2-konkurrenskraftig algoritm och bevisar att det inte finns någon (2 − )-konkurrenskraftig online-algoritm för någon positiv konstant. Nyckelord: problemet med grafprospektering, online-algoritm, konkurrensanalys
, medan för träd och oviktade grafer djup-första sökning är optimal REF.
The Online Graph Exploration Problem on Restricted Graphs
{'venue': 'IEICE Transactions', 'journal': 'IEICE Transactions', 'mag_field_of_study': ['Computer Science']}