Problem med lineært søgning - Linear search problem
I beregningskompleksitetsteori er det lineære søgeproblem et optimalt søgeproblem introduceret af Richard E. Bellman og uafhængigt overvejet af Anatole Beck .
Problemet
"En immobil skjuler er placeret på den virkelige linje i henhold til en kendt sandsynlighedsfordeling. En søger, hvis maksimale hastighed er en, starter fra oprindelsen og ønsker at opdage skjuleren i minimal forventet tid. Det antages, at søgeren kan ændre retning af hans bevægelse uden tab af tid. Det antages også, at søgeren ikke kan se skjuleren, før han faktisk når det punkt, hvor skjuleren er placeret, og den tid, der er gået, indtil dette øjeblik er spillets varighed. " For at finde skjuleren skal søgeren gå en afstand x 1 i den ene retning, vende tilbage til oprindelsen og gå afstand x 2 i den anden retning osv. (Længden af det n-th trin er angivet med x n ) , og for at gøre det på en optimal måde. (En optimal løsning behøver dog ikke at have et første skridt og kunne starte med et uendeligt antal små 'oscillationer'.) Dette problem kaldes normalt det lineære søgeproblem, og en søgeplan kaldes en bane. Det har tiltrukket megen forskning, noget af det ganske nylig.
Det lineære søgeproblem for en generel sandsynlighedsfordeling er uløst. Der findes imidlertid en dynamisk programmeringsalgoritme, der producerer en løsning til enhver diskret distribution og også en omtrentlig løsning for enhver sandsynlighedsfordeling med enhver ønsket nøjagtighed.
Det lineære søgeproblem blev løst af Anatole Beck og Donald J. Newman (1970) som et to-personers nul-sum-spil. Deres minimaxbane er at fordoble afstanden på hvert trin, og den optimale strategi er en blanding af baner, der øger afstanden med en bestemt konstant. Denne løsning giver søgestrategier, der ikke er følsomme over for antagelser vedrørende fordelingen af målet. Således præsenterer det også en øvre grænse for et værst tænkeligt scenario. Denne løsning blev opnået inden for rammerne af en online algoritme af Shmuel Gal , som også generaliserede dette resultat til et sæt samtidige stråler. Det bedste online konkurrenceforhold for søgningen på linjen er 9, men det kan reduceres til 4,6 ved hjælp af en randomiseret strategi. Demaine et al. gav en online løsning med en turomkostning.
Disse resultater blev genopdaget i 1990'erne af computerforskere som kovejsproblemet .
