[Algortimico] Calcolare tragitto

[Neptune]

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,
Neptune.

[ramy89]

Allora se ho capito bene stai usando un grafo.
L' algoritmo di Dijkstra calcola direttamente il cammino minimo tra due nodi del grafo.

[Neptune]

Originariamente inviato da ramy89
Allora se ho capito bene stai usando un grafo.
L' algoritmo di Dijkstra calcola direttamente il cammino minimo tra due nodi del grafo.

In realtà non è un grafo vero e proprio ma diciamo che l'algoritmo applicabile ad il un grafo potrebbe applicarsi tranquillamente anche qui.
Il problema pero è più complesso, non mi serve il cammino minimo mi serve il cammino di lunghezza minore di lmax e maggiore del 95% di lmax.

[D4rkAng3l]

Originariamente inviato da Neptune
In realtà non è un grafo vero e proprio ma diciamo che l'algoritmo applicabile ad il un grafo potrebbe applicarsi tranquillamente anche qui.
Il problema pero è più complesso, non mi serve il cammino minimo mi serve il cammino di lunghezza minore di lmax e maggiore del 95% di lmax.

mmm non farmi fare ironia sul tuo esame di algoritmi và che è meglio (ora capisco perchè sostenevi che per te era un esamuccio facile...lol)

Comunque sia la questione è questa:

1) Quando ti chiedi non il cammino minimo ma un cammino lungo al più lMax si tratta della versione decisionale del problema shortest path e questo non è un grosso problema, di fatto devi applicare una versione lievemente revisitata dell'algoritmo shortest path passandogli un parametro per la lunghezza massima che deve avere...cerca su Google e troverai

2) Quando invece vuoi trovare un cammino lungo ALMENO lMin il problema è fottutamente più difficile in quanto trattasi di qualcosa più complesso della versione decisionale del problema longest path (cammino più lungo).
Il problema longest path vuole trovare il cammino più lungo su un grafo. La sua versione decisionale risponde appunto alla domanda: esiste un cammino lungo ALMENO lMin?

Ecco ti dico subito che tale versione decisionale è un problema appartenente alla classe dei problemi NP-COMPLETI, quindi a maggior ragione il tuo problema è NP-COMPLETO, quindi non ammette algoritmi polinomiali quindi è un tantinello ingestibile (almeno così si pensa, se trovi un algoritmo (polinomiale) decente per tale problema in pratica dimostreresti che tramite riduzione polinomiale puoi risolvere TUTTI i problemi appartenenti alla classe dei problemi NP-COMPLETI in tempo polinomiale, quindi hai dimostrato che P = NP, quindi vinci un milione di dollari e la medaglia Fields...)