Problem linearne pretrage
U teoriji računarske kompleksnosti, problem linearne pretrage je optimalan problem pretrage predstavljen od strane Ričarda. E. Belmana.[1] (nezavnisno razmatran od strane Anotili Beka [2][3][4]).
Problem[uredi | uredi izvor]
"Nepokretni skrivač se nalazi na stvarnoj liniji prema poznatoj mogućnosti raspodele. Tragač, čija je maksimalna brzina jedan, počinje od početka i želi da otkrije skrivača u minimalnom očekivanom vremenu. Pretpostavlja se da tragač može da promeni svoj pravac kretanja bez gubitka vremena. Takođe se pretpostavlja da tragač ne može da vidi skrivača dok ne dođe do mesta gde se skrivač nalazi, a vreme koje je proteklo do tog trenutka je vreme trajanja igre. " Očigledno je da u cilju da pronađe skrivača tragač treba da ide do mesta x1 jednim pravcem, pa da se vrati na početak i krene u mesto x2 drugim pravcem, itd, (dužina od n koraka se označava sa xn), i tu pretragu uradi na odgovarajući način. (Međutim, optimalno rešenje ne mora imati prvi korak i može da počne sa beskonačnim brojem malih "oscilacija".) Ovaj problem se obično naziva problem linearne pretrage i plan pretrage se zove putanja.
Problem linearne pretrage za opštu mogućnost raspodele je nerešen.[5] Međutim, postoji dinamičko programiranje algoritma koje daje rešenje za bilo koju diskretnu raspodelu[6] i takođe je približno rešenje za bilo koju mogućnost raspodele, sa bilo koje željene tačnosti.[7]
Problem linearne pretrage je rešen od strane Anatoli Beka i Donalda J. Njumana (1970) kao teorija nulte sume dva igrača. Njihova minimaks putanja je da udvostruči udaljenost na svakom koraku, a odgovarajuća strategija je mešavina putanja koje povećavaju udaljenost od neke fiksne konstante.[8] Ovo rešenje daje strategija pretraga koje nisu osetljive na pretpostavkama koje se tiču raspodele mete. Prema tome, to takođe predstavlja gornje vezano za najgori mogući slučaj. Ovo rešenje je dobijeno u okviru onlajn algoritma od Samuela Gala, koji je takođe generalizovao ovaj rezultat na skup istovremenih zraka.[9]Najbolji onlajn konkurentni odnos za pretragu na liniji je 9, ali se može smanjiti na 4,6 pomoću slučajne strategije. Onlajn rešenje sa okretnim troškovima je dato.[10]
Ovi rezultati su otkriveni 1990. od strane informatičara kao problem putanje krave.
Vidi još[uredi | uredi izvor]
Reference[uredi | uredi izvor]
- ^ R. Bellman. An optimal search problem, SIAM Rev. (1963).
- ^ A. Beck. On the linear search Problem, Israel J. Mathematics (1964).
- ^ A. Beck. More on the linear search problem, Israel J. Mathematics (1965).
- ^ A. Beck and M. Beck. The linear search problem rides again, Israel J. Mathematics (1986).
- ^ Alpern, Steve; Gal, Shmuel (2003), „Chapter 8. Search on the Infinite Line”, The Theory of Search Games and Rendezvous, Part 2, International Series in Operations Research & Management Science, 55, str. 123—144, doi:10.1007/0-306-48212-6_8. On p. 124, Alpern and Gal write "no algorithm for solving the problem for a general probability distribution function has been found during about 37 years since the LSP was first presented."
- ^ F. T. Bruss and J. B. Robertson. A survey of the linear-search problem. Math. Sci. 13, 75-84, (1988).
- ^ S. Alpern and S. Gal. The Theory of Search Games and Rendezvous. Springer (2003): 139--143.
- ^ A. Beck and D.J. Newman. Yet More on the linear search problem. Israel J. Math. (1970).
- ^ S. Gal. SEARCH GAMES, Academic Press (1980).
- ^ E. Demaine, S. Fekete and S. Gal. Online searching with turn cost. Theoretical Computer Science (2006).