Википедија

Проблем линеарне претраге

У теорији рачунарске комплексности, проблем линеарне претраге је оптималан проблем претраге представљен од стране Ричарда. Е. Белмана.[1] (незавнисно разматран од стране Анотили Бека [2][3][4]).

Проблем уреди

"Непокретни скривач се налази на стварној линији према познатој могућности расподеле. Трагач, чија је максимална брзина један, почиње од почетка и жели да открије скривача у минималном очекиваном времену. Претпоставља се да трагач може да промени свој правац кретања без губитка времена. Такође се претпоставља да трагач не може да види скривача док не дође до места где се скривач налази, а време које је протекло до тог тренутка је време трајања игре. " Очигледно је да у циљу да пронађе скривача трагач треба да иде до места x1 једним правцем, па да се врати на почетак и крене у место x2 другим правцем, итд, (дужина од n корака се означава са xn), и ту претрагу уради на одговарајући начин. (Међутим, оптимално решење не мора имати први корак и може да почне са бесконачним бројем малих "осцилација".) Овај проблем се обично назива проблем линеарне претраге и план претраге се зове путања.

Проблем линеарне претраге за општу могућност расподеле је нерешен.[5] Међутим, постоји динамичко програмирање алгоритма које даје решење за било коју дискретну расподелу[6] и такође је приближно решење за било коју могућност расподеле, са било које жељене тачности.[7]

Проблем линеарне претраге је решен од стране Анатоли Бека и Доналда Ј. Њумана (1970) као теорија нулте суме два играча. Њихова минимакс путања је да удвостручи удаљеност на сваком кораку, а одговарајућа стратегија је мешавина путања које повећавају удаљеност од неке фиксне константе.[8] Ово решење даје стратегија претрага које нису осетљиве на претпоставкама које се тичу расподеле мете. Према томе, то такође представља горње везано за најгори могући случај. Ово решење је добијено у оквиру онлајн алгоритма од Самуела Гала, који је такође генерализовао овај резултат на скуп истовремених зрака.[9]Најбољи онлајн конкурентни однос за претрагу на линији је 9, али се може смањити на 4,6 помоћу случајне стратегије. Онлајн решење са окретним трошковима је дато.[10]

Ови резултати су откривени 1990. од стране информатичара као проблем путање краве.

Види још уреди

Референце уреди

  1. ^ R. Bellman. An optimal search problem, SIAM Rev. (1963).
  2. ^ A. Beck. On the linear search Problem, Israel J. Mathematics (1964).
  3. ^ A. Beck. More on the linear search problem, Israel J. Mathematics (1965).
  4. ^ A. Beck and M. Beck. The linear search problem rides again, Israel J. Mathematics (1986).
  5. ^ 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, стр. 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."
  6. ^ F. T. Bruss and J. B. Robertson. A survey of the linear-search problem. Math. Sci. 13, 75-84, (1988).
  7. ^ S. Alpern and S. Gal. The Theory of Search Games and Rendezvous. Springer (2003): 139--143.
  8. ^ A. Beck and D.J. Newman. Yet More on the linear search problem. Israel J. Math. (1970).
  9. ^ S. Gal. SEARCH GAMES, Academic Press (1980).
  10. ^ E. Demaine, S. Fekete and S. Gal. Online searching with turn cost. Theoretical Computer Science (2006).
Преузето из „https://sr.wikipedia.org/w/index.php?title=Проблем_линеарне_претраге&oldid=26983082”