У теорији рачунарске комплексности, проблем линеарне претраге је оптималан проблем претраге представљен од стране Ричарда. Е. Белмана.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).).
Проблем "Непокретни скривач се налази на стварној линији према познатој могућности расподеле. Трагач, чија је максимална брзина један, почиње од почетка и жели да открије скривача у минималном очекиваном времену. Претпоставља се да трагач може да промени свој правац кретања без губитка времена. Такође се претпоставља да трагач не може да види скривача док не дође до места где се скривач налази, а време које је протекло до тог тренутка је време трајања игре. " Очигледно је да у циљу да пронађе скривача трагач треба да иде до места x1 једним правцем, па да се врати на почетак и крене у место x2 другим правцем, итд, (дужина од n корака се означава са xn), и ту претрагу уради на одговарајући начин. (Међутим, оптимално решење не мора имати први корак и може да почне са бесконачним бројем малих "осцилација".) Овај проблем се обично назива проблем линеарне претраге и план претраге се зове путања.
Проблем линеарне претраге за општу могућност расподеле је нерешен.. 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.
Проблем линеарне претраге је решен од стране Анатоли Бека и Доналда Ј. Њумана (1970) као теорија нулте суме два играча. Њихова минимакс путања је да удвостручи удаљеност на сваком кораку, а одговарајућа стратегија је мешавина путања које повећавају удаљеност од неке фиксне константе.A. Beck and D.J. Newman. Yet More on the linear search problem. Israel J. Math. (1970). Ово решење даје стратегија претрага које нису осетљиве на претпоставкама које се тичу расподеле мете. Према томе, то такође представља горње везано за најгори могући случај. Ово решење је добијено у оквиру онлајн алгоритма од Самуела Гала, који је такође генерализовао овај резултат на скуп истовремених зрака.S. Gal. SEARCH GAMES, Academic Press (1980).Најбољи онлајн конкурентни однос за претрагу на линији је 9, али се може смањити на 4,6 помоћу случајне стратегије. Онлајн решење са окретним трошковима је дато.E. Demaine, S. Fekete and S. Gal. Online searching with turn cost. Theoretical Computer Science (2006).
Ови резултати су откривени 1990. од стране информатичара као проблем путање краве.
Види још Линеарна претрага
Референце
Категорија:Математичка оптимизација