Проблем линеарне претраге — разлика између измена
Направљено превођењем странице „Linear search problem“ |
(нема разлике)
|
Верзија на датум 27. октобар 2015. у 12:21
У теорији рачунарске комплексности, проблем линеарне претраге је оптималан проблем претраге представљен од стране Ричарда. Е. Белмана.[1] (незавнисно разматран од стране Анотили Бека[2][3][4]).
Проблем
"Непокретни скривач се налази на стварној линији према познатој могућности расподеле. Трагач, чија је максимална брзина један, почиње од почетка и жели да открије скривача у минималном очекиваном времену. Претпоставља се да трагач може да промени свој правац кретања без губитка времена. Такође се претпоставља да трагач не може да види скривача док не дође до места где се скривач налази, а време које је протекло до тог тренутка је време трајања игре. " Очигледно је да у циљу да пронађе скривача трагач треба да иде до места x1 једним правцем, па да се врати на почетак и крене у место x2 другим правцем, итд, (дужина од n корака се означава са xn), и ту претрагу уради на одговарајући начин. (Међутим, оптимално решење не мора имати први корак и може да почне са бесконачним бројем малих "осцилација".) Овај проблем се обично назива проблем линеарне претраге и план претраге се зове путања.
Проблем линеарне претраге за општу могућност расподеле је нерешен.[5] Међутим, постоји динамичко програмирање алгоритма које даје решење за било коју дискретну расподелу[6] и такође је приближно решење за било коју могућност расподеле, са било које жељене тачности.[7]
Проблем линеарне претраге је решен од стране Анатоли Бека и Доналда Ј. Њумана (1970) као теорија нулте суме два играча. Њихова минимакс путања је да удвостручи удаљеност на сваком кораку, а одговарајућа стратегија је мешавина путања које повећавају удаљеност од неке фиксне константе.[8] Ово решење даје стратегија претрага које нису осетљиве на претпоставкама које се тичу расподеле мете. Према томе, то такође представља горње везано за најгори могући случај. Ово решење је добијено у оквиру онлине алгоритма од Самуела Гала, који је такође генерализовао овај резултат на скуп истовремених зрака.[9] Најбољи онлајн конкурентни однос за претрагу на линији је 9, али се може смањити на 4,6 помоћу случајне стратегије. Онлајн решење са окретним трошковима је дато.[10]
Ови резултати су откривени 1990. од стране информатичара као проблем путање краве.
Види још
Референце
- ^ R. Bellman.
- ^ A. Beck.
- ^ A. Beck.
- ^ A. Beck and M. Beck.
- ^ 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
- ^ F. T. Bruss and J. B. Robertson.
- ^ S. Alpern and S. Gal.
- ^ A. Beck and D.J. Newman.
- ^ S. Gal.
- ^ E. Demaine, S. Fekete and S. Gal.