Skip to content

Ricerca di un bersaglio immobile o mobile su una rete

Informazioni tesi

  Autore: Paolo Barberis
  Tipo: Tesi di Laurea
  Anno: 2007-08
  Università: Università degli Studi di Roma La Sapienza
  Facoltà: Scienze Statistiche
  Corso: Statistica
  Relatore: Vanda De Angelis
  Lingua: Italiano
  Num. pagine: 111

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.

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista
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

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista

FAQ

Per consultare la tesi è necessario essere registrati e acquistare la consultazione integrale del file, al costo di 29,89€.
Il pagamento può essere effettuato tramite carta di credito/carta prepagata, PayPal, bonifico bancario, bollettino postale.
Confermato il pagamento si potrà consultare i file esclusivamente in formato .PDF accedendo alla propria Home Personale. Si potrà quindi procedere a salvare o stampare il file.
Maggiori informazioni
Ingiustamente snobbata durante le ricerche bibliografiche, una tesi di laurea si rivela decisamente utile:
  • perché affronta un singolo argomento in modo sintetico e specifico come altri testi non fanno;
  • perché è un lavoro originale che si basa su una ricerca bibliografica accurata;
  • perché, a differenza di altri materiali che puoi reperire online, una tesi di laurea è stata verificata da un docente universitario e dalla commissione in sede d'esame. La nostra redazione inoltre controlla prima della pubblicazione la completezza dei materiali e, dal 2009, anche l'originalità della tesi attraverso il software antiplagio Compilatio.net.
  • L'utilizzo della consultazione integrale della tesi da parte dell'Utente che ne acquista il diritto è da considerarsi esclusivamente privato.
  • Nel caso in cui l'Utente volesse pubblicare o citare una tesi presente nel database del sito www.tesionline.it deve ottenere autorizzazione scritta dall'Autore della tesi stessa, il quale è unico detentore dei diritti.
  • L'Utente è l'unico ed esclusivo responsabile del materiale di cui acquista il diritto alla consultazione. Si impegna a non divulgare a mezzo stampa, editoria in genere, televisione, radio, Internet e/o qualsiasi altro mezzo divulgativo esistente o che venisse inventato, il contenuto della tesi che consulta o stralci della medesima. Verrà perseguito legalmente nel caso di riproduzione totale e/o parziale su qualsiasi mezzo e/o su qualsiasi supporto, nel caso di divulgazione nonché nel caso di ricavo economico derivante dallo sfruttamento del diritto acquisito.
  • L'Utente è a conoscenza che l'importo da lui pagato per la consultazione integrale della tesi prescelta è ripartito, a partire dalla seconda consultazione assoluta nell'anno in corso, al 50% tra l'Autore/i della tesi e Tesionline Srl, la società titolare del sito www.tesionline.it.
L'obiettivo di Tesionline è quello di rendere accessibile a una platea il più possibile vasta il patrimonio di cultura e conoscenza contenuto nelle tesi.
Per raggiungerlo, è fondamentale superare la barriera rappresentata dalla lingua. Ecco perché cerchiamo persone disponibili ad effettuare la traduzione delle tesi pubblicate nel nostro sito.
Scopri come funziona

DUBBI? Contattaci

Contatta la redazione a
[email protected]

Ci trovi su Skype (redazione_tesi)
dalle 9:00 alle 13:00

Oppure vieni a trovarci su

Parole chiave

teoria dei giochi
teoria dei grafi
giochi di ricerca
algoritmi di ricerca

Non hai trovato quello che cercavi?


Abbiamo più di 45.000 Tesi di Laurea: cerca nel nostro database

Oppure consulta la sezione dedicata ad appunti universitari selezionati e pubblicati dalla nostra redazione

Ottimizza la tua ricerca:

  • individua con precisione le parole chiave specifiche della tua ricerca
  • elimina i termini non significativi (aggettivi, articoli, avverbi...)
  • se non hai risultati amplia la ricerca con termini via via più generici (ad esempio da "anziano oncologico" a "paziente oncologico")
  • utilizza la ricerca avanzata
  • utilizza gli operatori booleani (and, or, "")

Idee per la tesi?

Scopri le migliori tesi scelte da noi sugli argomenti recenti


Come si scrive una tesi di laurea?


A quale cattedra chiedere la tesi? Quale sarà il docente più disponibile? Quale l'argomento più interessante per me? ...e quale quello più interessante per il mondo del lavoro?

Scarica gratuitamente la nostra guida "Come si scrive una tesi di laurea" e iscriviti alla newsletter per ricevere consigli e materiale utile.


La tesi l'ho già scritta,
ora cosa ne faccio?


La tua tesi ti ha aiutato ad ottenere quel sudato titolo di studio, ma può darti molto di più: ti differenzia dai tuoi colleghi universitari, mostra i tuoi interessi ed è un lavoro di ricerca unico, che può essere utile anche ad altri.

Il nostro consiglio è di non sprecare tutto questo lavoro:

È ora di pubblicare la tesi