Att söka efter ett mål är ett centralt och omfattande problem inom datavetenskapen. I klassiska sökproblem, kostnaden för en sökfunktion är helt enkelt antalet frågor som görs till ett orakel som vet position målet. I många robotproblem, liksom i problem från andra områden, vill vi ta ut en kostnad som står i proportion till avståndet mellan frågor (t.ex. den tid som krävs för att resa mellan två frågepunkter). Med denna kostnadsfunktion i åtanke, det abstrakta problemet som kallas w-lane ko-pat problem utformades. Det finns kända optimala deterministiska algoritmer för kopatproblemet, och vi ger de första randomiserade algoritmerna i detta papper. Vi visar att vår algoritm är optimal för två vägar (w = 2), och ger bevis för att den verkligen är optimal för större värden på w. De randomiserade algoritmerna ger förväntad prestanda som är nästan dubbelt så bra som möjligt med en deterministisk algoritm.
REF studier randomiserade strategier för stjärnsökning (som också kallas "ko-pat problem", motiverat av en ko söker efter närmaste betesmark.)
Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem
{'venue': "SODA '93", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}