Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

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.

Mostra/Nascondi contenuto.
1. Introduzione 1.1 Introduzione In tale capitolo iniziale si presenta la dissertazione medesima, introducendone i suoi argomenti, delineando i suoi contenuti e chiarendo altresì le ragioni della sua stesura. Si considera ora in dettaglio ciò che viene trattato nei prossimi paragrafi: Nel secondo paragrafo "Argomento della Dissertazione", dopo aver esposto le motivazioni della stesura, si presentano il soggetto dell'elaborato, i giochi di ricerca, ed il loro ambito di studio. Nel terzo paragrafo “ Analisi della Letteratura ”, si espone una breve bibliografia sull'argomento della dissertazione, accennando lo sviluppo assiomatico; si forniscono inoltre alcuni campi applicativi. Nel quarto paragrafo " Scopo e Articolazione della Dissertazione", si trattano le f inalità previste dell'elaborato e si prende in esame la sua articolazione, analizzando in dettaglio i distinti capitoli ed i loro contenuti, tracciando in tal modo un percorso logico di svolgimento. Nell'ultimo paragrafo “ Conclusioni ”, mediante considerazioni ed osservazioni si esamina il capitolo terminato e si espone la metodica con cui prosegue la dissertazione . 1.2 Argomento della Dissertazione Nel seguito, dopo aver motivato la stesura dell'elaborato, si espone in modo sintetico la materia in oggetto dei capitoli seguenti. Le ragioni della stesura della disertazione sono di carattere puramente personali e riguardano il crescente interesse nell'approfondimento della materia trattata dalla teoria dei giochi in un differente contesto. Dopo aver appurato lo sviluppo delle recenti ricerche, la consapevolezza della vasta applicabilità e adattabilità scaturita dall'integrazione di tale teoria con un insieme di riferimento come il grafo, ha stimolato e motivato ancor più l'analisi e l'esposizione. Si considera che nelle iniziali analisi della Teoria della Ricerca si studiano problemi in cui viene formalizzata una situazione in cui un cercatore desidera minimizzare il tempo richiesto per trovare un oggetto nascosto (chiamato nascosto, ricercato, fuggitivo o semplicemente “bersaglio”). In genere il cercatore sceglie un percorso nello “spazio di ricerca” e trova il bersaglio quando è sufficientemente vicino ad esso. Tradizionalmente, il bersaglio si assume non avere motivi personali riguardanti il tempo 1

Tesi di Laurea

Facoltà: Scienze Statistiche

Autore: Paolo Barberis Contatta »

Composta da 111 pagine.

 

Questa tesi ha raggiunto 382 click dal 16/12/2011.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.