guylmaster
10-03-2012, 15:15
Salve a tutti,
ormai sapete già che mi sto barcamenando su un algoritmo per la ricostruzione di rotte navali avendo delle rilevazioni sulla mappa.
Le rilevazioni che ho sono un punto sulla mappa (latitudine e longitudine), l'orario della rilevazioni e la velocità. Prendendo due rilevazioni, basandomi anche sulla velocità nei due punti so stimarmi una lunghezza massima che bisogna percorrere per andare da una rilevazione all'altra.
Il problema è qui, fino ad ora cercavo il primo percorso che arrivasse a destinazione non superando questa lunghezza massima (lmax) . Perfarlo facevo una visita in ampiezza, ogni cella che visitavo decremento lmax ed inserivo cella ed lmax in una lista di nodi visitati in modo da non ripassare sempre sugli stessi nodi. Se arrivavo a lmax < 0 senza raggiungere la destinazione facevo un backtrack, altrimenti se raggiungevo la destinazione (anche se non nel percorso minimo, ma comunque con una lunghezza < lmax) mi andava bene e l'algoritmo terminava.
Questa lista dei nodi visitati la utilizzavo a questa maniera: Immaginatevi una mappa, ogni cella ha 8 vicini (tranne quelle sui bordi), da questi 8 vicini prendo solo quelli che o non risultano nella lista dei vicini visitati o se risultano sono stato inseriti con un lmax minor di quello attuale e quindi sono stati visitati prima di un backtrack e quindi sono ancora disponibili.
Fin qui tutto bene, adesso ci è stato detto di aggiungere un'altra clausola, ovvero non devo semplicemente raggiungere la destinazione entro una determinata lmax, quindi con un percorso non troppo lungo, ma devo raggiungerla con una distanza che si avvicina di molto a questa lmax (tipo non più piccola del 5%), e quindi bisogna evitare di fare percorsi troppo lunghi.
A questo punto non so più come fare. Se faccio un backtrack anche quando sono arrivato troppo velocemente alla fine tutto il meccanismo della lista dei vicini non funziona più.
In breve: Come posso fare avendo una mappa di celle, ogni cella con 8 vicini (di cui non tutti navigabili perché magari alcuni sono zone di terra), a costruirmi una traiettoria tra due celle che non sia ne più lunga di una data lmax ne più corta di un tot% ?
Perché di algoritmi in rete riesco a trovare tutte cose riguardanti ai percorsi minimi, ma non mi risulta (magari esistono ma mi sfuggono) che qualcuno si sia posto il problema dei percorsi "non troppo corti" :D
P.S: Il mio attuale algoritmo è una variante dell'A*, che ovviamente non prevede minimamente la possibilità di non arrivare troppo presto a destinazione
http://it.wikipedia.org/wiki/A*
Vi ringrazio in anticipo,
guylmaster.
ormai sapete già che mi sto barcamenando su un algoritmo per la ricostruzione di rotte navali avendo delle rilevazioni sulla mappa.
Le rilevazioni che ho sono un punto sulla mappa (latitudine e longitudine), l'orario della rilevazioni e la velocità. Prendendo due rilevazioni, basandomi anche sulla velocità nei due punti so stimarmi una lunghezza massima che bisogna percorrere per andare da una rilevazione all'altra.
Il problema è qui, fino ad ora cercavo il primo percorso che arrivasse a destinazione non superando questa lunghezza massima (lmax) . Perfarlo facevo una visita in ampiezza, ogni cella che visitavo decremento lmax ed inserivo cella ed lmax in una lista di nodi visitati in modo da non ripassare sempre sugli stessi nodi. Se arrivavo a lmax < 0 senza raggiungere la destinazione facevo un backtrack, altrimenti se raggiungevo la destinazione (anche se non nel percorso minimo, ma comunque con una lunghezza < lmax) mi andava bene e l'algoritmo terminava.
Questa lista dei nodi visitati la utilizzavo a questa maniera: Immaginatevi una mappa, ogni cella ha 8 vicini (tranne quelle sui bordi), da questi 8 vicini prendo solo quelli che o non risultano nella lista dei vicini visitati o se risultano sono stato inseriti con un lmax minor di quello attuale e quindi sono stati visitati prima di un backtrack e quindi sono ancora disponibili.
Fin qui tutto bene, adesso ci è stato detto di aggiungere un'altra clausola, ovvero non devo semplicemente raggiungere la destinazione entro una determinata lmax, quindi con un percorso non troppo lungo, ma devo raggiungerla con una distanza che si avvicina di molto a questa lmax (tipo non più piccola del 5%), e quindi bisogna evitare di fare percorsi troppo lunghi.
A questo punto non so più come fare. Se faccio un backtrack anche quando sono arrivato troppo velocemente alla fine tutto il meccanismo della lista dei vicini non funziona più.
In breve: Come posso fare avendo una mappa di celle, ogni cella con 8 vicini (di cui non tutti navigabili perché magari alcuni sono zone di terra), a costruirmi una traiettoria tra due celle che non sia ne più lunga di una data lmax ne più corta di un tot% ?
Perché di algoritmi in rete riesco a trovare tutte cose riguardanti ai percorsi minimi, ma non mi risulta (magari esistono ma mi sfuggono) che qualcuno si sia posto il problema dei percorsi "non troppo corti" :D
P.S: Il mio attuale algoritmo è una variante dell'A*, che ovviamente non prevede minimamente la possibilità di non arrivare troppo presto a destinazione
http://it.wikipedia.org/wiki/A*
Vi ringrazio in anticipo,
guylmaster.