Vi visar hur man optimerar sökningen efter ett dolt objekt, terrorist, eller helt enkelt Hider, beläget på en punkt H enligt en känd eller okänd distribution på ett rotat nätverk Q. Vi ändrar den traditionella "pathwise search"-metoden till en mer allmän uppfattning om "expanderande sökning". När Hidern är begränsad till noderna i Q; en expanderande sökning S består av en beställning (a 1 ; a 2 ; : : ) av bågarna i en spanning delträd så att rot noden är i en 1 och varje båge a i är intilliggande till en tidigare båge a j ; j < i: Om en k innehåller H; söktiden T är (a 1 ) + + (a k ) ; där är längdmått på Q: För mer allmänna fördelningar ; en expanderande sökning S beskrivs av den näste familjen av anslutna uppsättningar S (t) som anger det område av Q som har täckts av tid t: S (0) är roten, (S (t) = t; och T = min ft : H 2 S (t)g : För en känd Hider distribution på ett träd Q; den förväntade tiden minimering strategi S börjar med rotat delträd Q 0 maximerarheten (Q 0 ) = (Q 0 ) : (För godtyckliga nätverk, använder vi detta kriterium på alla spanning delträd.) Sökningen S kan tolkas som den optimala metoden för gruvdrift kända kolsömmar, när tiden att flytta gruvarbetare eller maskiner är försumbar jämfört med grävtid. När Hider-distributionen är okänd, betraktar vi sökspelet nollsummor där Hidern plockar H; Sökaren S och payo¤ är T: För träd Q; värdet är V = (Q) + D) = 2, där D är ett medelavstånd från rot till blad noder. Om Q är 2 båge ansluten, V = (Q) =2. Tillämpningar och tolkningar av det expanderande sökparadigmet ges, särskilt till flera agentsökningar.
Expandera sökning på ett nätverk infördes i REF, med fokus på Bayesian problemet att minimera den förväntade söktiden mot en känd Hider distribution.
Mining Coal or Finding Terrorists: The Expanding Search Paradigm
{'venue': 'Oper. Res.', 'journal': 'Oper. Res.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}