Vi studerar den kunskap om nätverket som krävs för att effektivt lösa en uppgift som rör detta nätverk. Effekterna av tillgänglig information på effektiviteten i att lösa nätproblem, t.ex. kommunikation eller prospektering, har undersökts tidigare, men antaganden gällde tillgången till vissa uppgifter om nätet, t.ex. storleken, diametern eller en karta över nätet. Däremot är vår strategi kvantitativ: vi undersöker det minsta antal bitar av information (bitar av råd) som måste ges till en algoritm för att utföra en uppgift med given effektivitet. Vi illustrerar denna kvantitativa inställning till tillgänglig kunskap genom uppgiften att utforska träd. En mobil enhet (robot) måste passera alla kanter av ett okänt träd, med så få kanttraversaler som möjligt. Kvaliteten på en prospekteringsalgoritm A mäts genom dess konkurrensförhållande, dvs. genom att jämföra dess kostnad (antal kanttraversaler) med längden på den kortaste vägen som innehåller alla kanter av trädet. DjupFirst-Search har konkurrensförhållande 2 och, i avsaknad av någon information om trädet, ingen algoritm kan slå detta värde. Vi bestämmer det minsta antal bitar av råd som måste ges till en prospekteringsalgoritm för att uppnå konkurrensförhållande strikt mindre än 2. Vårt huvudsakliga resultat fastställer ett exakt tröskelvärde antal bitar av råd som visar sig vara ungefär log D, där D är diametern på trädet. Mer exakt, för varje konstant c, konstruerar vi en prospekteringsalgoritm med konkurrensförhållande mindre än 2, med hjälp av de flesta log D − c bitar av råd, och vi visar att varje algoritm som använder log D − g(D) bitar av råd, för alla funktioner g obundet från ovan, har konkurrensförhållande minst 2.
I REF fastställde författarna storleken på de råd som behövs för att bryta konkurrensförhållandet 2 i en prospekteringsalgoritm i träd.
Tree Exploration with Advice
{'venue': 'Inf. Comput.', 'journal': 'Inf. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}