[Java - Algoritmico] Calcolare tragitto

[guylmaster]

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"

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.

[PGI-Bis]

Una soluzione è certamente questa:

trovi il percorso più breve e se è troppo breve elimini dalla mappa una delle celle di quel percorso e lo ricalcoli.

E' meno facile da scrivere che da descrivere perchè quello che devi fare più passaggi: elimina una cella, ricacoli, se non va bene riattivi la cella eliminata e ne scegli un'altra, ricacoli e via così. Se arrivi ad aver testato tutte le celle senza aver trovato il percorso corretto allora dovrai rifare il tutto eliminandone due, poi tre poi quattro e via dicendo.

Funziona di certo perchè la condizione che determina l'eccessiva "brevità" del percorso è l'attraversamento di una o più celle: impediscilo e avrai la possibilità di calcolare un percorso più lungo.

Richiede però un sacco di conti. Un modo per mitigare questa richiesta è calcolare una distanza media tra le celle. Se sei in grado di stimare il numero di celle che dovrai attraversare per raggiungere la destinazione allora puoi decidere di accettare o meno un attraversamento durante la costruzione del percorso in base allo scostamento che la distanza tra la cella da scegliere e quella precedente ha rispetto alla distanza media.

Vale a dire che se la distanza ottimale è di 1 km e sai che le celle da attraversare saranno circa 10 allora la distanza tra le singole celle del percorso dovrebbe essere di 100 metri.

Io parto dalla cella P e tra le opzioni possibili per raggiungere la destinazione scelgo quella cella C adiacente a P la cui distanza da P più si avvicina a quei cento metri. Ricalcolo la distanza media tra le celle tenendo conto che PC è 90 o 100 o magari anche 50 e so il prossimo passo potrà essere di 105 o 150 o 75 metri.

E' solo un'euristica (la possibilità che ci azzecchi sempre dipende dalla distribuzione dello spazio tra le celle) ma potrebbe aiutare.