Lineært søkeproblem - Linear search problem
I beregningskompleksitetsteori er det lineære søkeproblemet et optimalt søkeproblem som ble introdusert av Richard E. Bellman og uavhengig vurdert av Anatole Beck .
Problemet
"En immobil skjuler er lokalisert på den virkelige linjen i henhold til en kjent sannsynlighetsfordeling. En søker, hvis maksimale hastighet er en, starter fra opprinnelsen og ønsker å oppdage skjuleren i minimal forventet tid. Det antas at søkeren kan endre bevegelsesretning uten tap av tid. Det antas også at søkeren ikke kan se skjuleren før han faktisk når det punktet der skjuleren befinner seg og tiden som er gått til dette øyeblikket er varigheten av spillet. " For å finne skjuleren må søkeren gå en avstand x 1 i den ene retningen, gå tilbake til opprinnelsen og gå avstanden x 2 i den andre retningen etc., (lengden på det n-th trinnet er angitt med x n ) , og for å gjøre det på en optimal måte. (Imidlertid trenger en optimal løsning ikke å ha et første skritt og kan starte med et uendelig antall små 'svingninger'.) Dette problemet kalles vanligvis det lineære søkeproblemet, og en søkeplan kalles en bane. Det har tiltrukket seg mye forskning, noe av det ganske nylig.
Det lineære søkeproblemet for en generell sannsynlighetsfordeling er uløst. Imidlertid eksisterer det en dynamisk programmeringsalgoritme som produserer en løsning for enhver diskret distribusjon og også en omtrentlig løsning, for enhver sannsynlighetsfordeling, med ønsket nøyaktighet.
Det lineære søkeproblemet ble løst av Anatole Beck og Donald J. Newman (1970) som et to-personers nullsumspill. Deres minimaks- banen er for å doble avstanden i hvert trinn, og optimal strategi er en blanding av baner som øker avstanden av noen fast konstant. Denne løsningen gir søkestrategier som ikke er følsomme for forutsetninger om fordelingen av målet. Dermed presenterer den også en øvre grense for et verst tenkelig scenario. Denne løsningen ble oppnådd innenfor rammen av en online algoritme av Shmuel Gal , som også generaliserte dette resultatet til et sett med samtidige stråler. Det beste konkurranseforholdet på nettet for søket på linjen er 9, men det kan reduseres til 4,6 ved å bruke en randomisert strategi. Demaine et al. ga en online løsning med en turn -kostnad.
Disse resultatene ble gjenoppdaget på 1990 -tallet av datavitenskapere som kubaneproblemet .
