Linjärt sökproblem
Inom beräkningskomplexitetsteori är det linjära sökproblemet ett optimalt sökproblem som introducerats av Richard E. Bellman och oberoende övervägt av Anatole Beck .
Problemet
"En orörlig gömmer är placerad på den verkliga linjen enligt en känd sannolikhetsfördelning. En sökare, vars maximala hastighet är en, utgår från origo och vill upptäcka gömmern på minimal förväntad tid. Det antas att sökaren kan ändra riktning av sin rörelse utan tidsförlust. Det antas också att den som söker inte kan se gömman förrän han faktiskt når den punkt där gömman befinner sig och tiden som förflutit till detta ögonblick är spelets varaktighet."
För att hitta döljaren måste sökaren gå en sträcka x 1 i en riktning, gå tillbaka till origo och gå sträcka x 2 i den andra riktningen etc. (längden på det n:te steget betecknas med x n ) , och att göra det på ett optimalt sätt. (En optimal lösning behöver dock inte ha ett första steg och kan börja med ett oändligt antal små 'svängningar'.) Detta problem brukar kallas det linjära sökproblemet och en sökplan kallas en bana. Det har lockat till sig mycket forskning, en del av det ganska nyligen. [ när? ]
Det linjära sökproblemet för en generell sannolikhetsfördelning är olöst. Det finns emellertid en dynamisk programmeringsalgoritm som producerar en lösning för vilken diskret fördelning som helst och även en ungefärlig lösning, för vilken sannolikhetsfördelning som helst, med vilken noggrannhet som helst.
Det linjära sökproblemet löstes av Anatole Beck och Donald J. Newman (1970) som ett nollsummespel för två personer. Deras minimaxbana är att dubbla avståndet på varje steg och den optimala strategin är en blandning av banor som ökar avståndet med någon fast konstant. Denna lösning ger sökstrategier som inte är känsliga för antaganden om fördelningen av målet. Därmed utgör den också en övre gräns för ett värsta scenario. Denna lösning erhölls inom ramen för en onlinealgoritm av Shmuel Gal , som också generaliserade detta resultat till en uppsättning samtidiga strålar. Det bästa konkurrensförhållandet online för sökningen på linjen är 9 men det kan reduceras till 4,6 genom att använda en randomiserad strategi. Demaine et al. gav en onlinelösning med en turkostnad.
Dessa resultat återupptäcktes på 1990-talet av datavetare som kovägsproblemet .