Vi anser att problemet med att söka efter ett objekt på en linje på ett okänt avstånd OPT från den ursprungliga positionen av sökaren, i närvaro av en kostnad av d för varje gång sökaren ändrar riktning. Detta är en generalisering av det välstuderade linjära sökproblemet. Vi beskriver en strategi som är garanterad att hitta objektet till en kostnad av högst 9 · OPT + 2d, som har den optimala konkurrensförhållandet 9 med avseende på OPT plus den minsta motsvarande tillsatsterm. Vårt argument för övre och nedre gräns använder ett oändligt linjärt program, som vi löser genom experimentell lösning av en oändlig serie av approximerande finita linjära program, uppskatta gränserna, och lösa de resulterande upprepningar för ett uttryckligt bevis på optimalitet. Vi anser att denna teknik är intressant i sig själv och bör hjälpa till att lösa andra sökproblem. I synnerhet anser vi att problemet med stjärnsökning eller ko-väg med turn kostar, där det dolda objektet placeras på en av m-strålar som utgår från den ursprungliga positionen av
Nyligen, Demaine et al. Ref beaktade ko-pat problemet med en dubbel komponent pris: den första är avstånd och den andra är tur kostnad.
Online Searching with Turn Cost
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}