Ricerca di un bersaglio immobile o mobile su una rete

Oggetto di questo lavoro sono i modelli di gioco di ricerca, che rappresentano una contrapposizione tra due giocatori, il cercatore ed il nascosto. Questi modelli sono presentati come giochi a due persone a somma nulla, in cui il cercatore desidera minimizzare il tempo richiesto per catturare il nascosto. Si assume sempre che i giocatori non abbiano alcuna conoscenza sul movimento dell'antagonista finché la distanza non sia inferiore o eguale al raggio di scoperta, nel quale istante la cattura avviene.
Si distinguono due casistiche: si definisce il nascosto immobile se attende in modo stazionario, senza quindi motivi personali riguardanti il tempo di cattura e può scegliere solo il suo punto di occultamento. Si parla di nascosto mobile se si può muovere indipendentemente, con obiettivo antitetico rispetto al suo antagonista e può scegliere qualsiasi traiettoria nello spazio di ricerca.
Si intende fornire gli strumenti essenziali per un'efficiente costruzione di un modello in tutti i suoi principali aspetti formali e risolutivi in riferimento ad una rete. I problemi di interesse, rappresentabili con le reti possono essere: cartine stradali, planimetrie, progetti tecnici, circuiti elettrici, reti informatiche, rappresentazioni economiche, finanziarie e sociali.
L'analisi dei modelli si concentra sullo studio del tempo di cattura e sulla conseguente determinazione delle strategie, rispettivamente di ricerca e di occultamento dei giocatori.
Si assegna allo spazio di ricerca costituito dalla rete una misura, corrispondente alla somma delle lunghezze di tutti gli archi e si assume che il raggio di scoperta sia nullo, cioè che la cattura avvenga quando il cercatore incontra il nascosto.
La caratterizzazione dei modelli include la presentazione del tasso massimo di scoperta del cercatore, definito come la misura dell'insieme dei punti visitati in rapporto al tempo.
In genere per ottenere un comportamento più efficiente, il giocatore utilizza una strategia mista, ovvero una distribuzione di probabilità sull'insieme delle strategie (pure). In tal caso il tempo di cattura diviene una variabile casuale, cosicché ogni giocatore può garantire un tempo atteso di cattura. La trattazione riporta infatti i limiti inferiore e superiore del tempo atteso di cattura per il nascosto in funzione della misura dell'insieme e del tasso massimo di scoperta del cercatore, esaminando differenti casi.
Inoltre si considera l'eventuale presenza di più cercatori cooperativi con il medesimo obiettivo. Il numero minimo di tali cercatori necessari per il ritrovamento del nascosto è chiamato numero di ricerca. Se sono usate solo delle strategie pure di ricerca per garantire la cattura sono necessari diversi cercatori.
Nel caso in cui sia immobile, il nascosto può scegliere casualmente il proprio punto di occultamento utilizzando una strategia uniforme. Per tale strategia si dimostra che esiste un limite inferiore per il tempo di cattura di qualsiasi gioco di ricerca.
Supponendo che il cercatore si muova ad una velocità unitaria, il tempo atteso di cattura è pari alla metà della misura della rete se il grafo è euleriano. Se il grafo non è euleriano, il tempo di cattura è pari alla metà della lunghezza del tour del postino cinese, che non eccede il doppio della misura del grafo essendo uguale al doppio nel caso degli alberi.
Viene esaminato inoltre il caso in cui il nascosto sia mobile, ovvero abbia la possibilità di muoversi all'interno dello spazio di ricerca e abbia un proprio interesse, contrastante con quello del cercatore, di ritardare il più possibile la cattura.
Nel caso in cui il nascosto sia mobile, viene considerato il gioco in una rete costituita da k archi di lunghezza unitaria che uniscono una coppia di nodi, in cui il cercatore si muove a velocità massima unitaria mentre il nascosto può eccedere tale velocità. Il cercatore parte da un nodo, sceglie in modo equiprobabile un arco e lo percorre. Quando arriva all'altro nodo sceglie ugualmente in modo equiprobabile quale percorrere tra i k archi, senza sostare nel nodo e continua così. Il tempo di cattura è k ed è elaborata anche la strategia ottima del nascosto.
A completamento del lavoro, si accenna a particolari estensioni verificabili. Si considerano le strategie erratiche in cui il cercatore può attendere, con determinata distribuzione di probabilità, in un dato nodo tendendo una sorta di agguato; si generalizza agli spazi di ricerca non omogenei, in cui si permette che la velocità massima del cercatore dipenda dalla sua posizione.
Si trattano quindi in breve alcune applicazioni dei problemi di ricerca in distinti contesti: la ricerca dell'uscita in un grafo definito come labirinto, l'individuazione di un valore in un intervallo mediante una sequenza di supposizioni, la difesa di una zona sensibile, la ricerca in un grafo in cui è possibile accumulare risorse in distinte locazioni.