• G
    User Attivo •

    Calcolo del percorso più breve

    Buonasera,

    ho un problema nello sviluppo di un algoritmo che mi permetta di fare una cosa del genere:
    ho, diciamo, un labirinto su griglia a quadri (liberi->bianchi, chiusi->neri)

    Manualmente posso fare un percorso e determinare al termine il numero di passi eseguiti.
    Dovrei ora restituire accanto al numero di passi fatti, il minor numero di passi possibile che si può compiere in quel labirinto.

    Per capirci, un veloce esempio da paint ( 😮 😞

    i.imgur.com/Z9UMq44.png

    Si va dal giallo al verde, non si va in diagonale.
    Nel primo caso nessun ostacolo, ci potrebbero essere altri percorsi con 8 passi ma andando dritti a meta non ha senso calcolarli.
    Nel secondo caso stessa cosa, avendo un percorso rettilineo (in basso) potrei anche ignorare gli altri, ma in ogni caso ciò che importa è conoscere il numero di passi necessari e non tutti i percorsi possibili (utili solo per comparare vie differenti in percorsi più complessi, se serve...).
    Nel terzo abbiamo già dei percorsi più strani.
    Ultima cosa: è possibile che il percorso sia impossibile (nessun percorso libero fino alla meta) e in quel caso lo devo segnalare.

    Questi sono piccolissimi esempi ma lo script dovrebbe funzionare anche con molte più caselle.
    Ipotizziamo un campo 100x100. Le zone di campo libere e occupate le prelevo dal database. In che modo posso procedere?

    Negli esempi piccoli potrei ciclare tutti i percorsi possibili, e memorizzare il numero di passi minore. Mi sembra improponibile se fatto in larga scala.

    In questo momento non trovo soluzione meno barbara :?, qualsiasi input sarebbe gradito.

    Grazie!

    0
  • M
    User Attivo •

    Il tuo problema non mi sembra completamente chiaro, ma penso che per prima cosa dovresti ricondurti ad un grafo equivalente e poi la soluzione al problema la puoi trovare con l'algoritmo di Dijkstra. Nella pagina oltre ad illustrarlo c'è anche un pseudocodice già fatto. È un algoritmo presente in diversi documenti che troverai con una semplice ricerca in Rete.

    0
  • G
    User Attivo •

    Grazie MenteLibera, credo sia quello che mi serviva.

    Ho cercato di approfondire in questi giorni, mi preoccupa solo l'eventuale sovraccarico dei calcoli, che si potrebbe però in parte alleviare con un sistema cache. Anche se è prevista la variazione del "campo" abbastanza spesso, con conseguente ricalcolo.

    Ho letto per il web, non so se sia affidabile, che il numero di calcoli equivale al numero di nodi elevato alla seconda. Io ne utilizzerò 2-3000 massimo.

    Un utente con 1700 nodi segnalava 0.5/1 secondi per ogni calcolo, ma prelevava tutti i dati (con relativi nodi successivi) dal database.

    Io dovrei avere una griglia fissa con IDnodi e IDnodivicini prestabiliti. Dovrò inviare richiesta al database solo per capire quali nodi non considerare (perché bloccati, quelli in precedenza segnati in nero).

    Ho trovato questo codice:
    *rosettacode.org/wiki/Dijkstra's_algorithm#PHP
    e:
    algolist.com/code/php/Dijkstra's_algorithm

    Li invio solo per completare questo post, per tenerli come promemoria e aggiornarvi su come procede.
    Se qualcuno lo ha già utilizzato e riesce a darmi qualche consiglio su quale sia il migliore o se è possibile ottimizzarli, io comunque farò delle prove e vi farò sapere. Ancora non ci ho messo su mani, definita la struttura dei dati li provo.

    Come ottimizzazione ho già preso a mente il caching anche se per ogni minima modifica della griglia, che dipende dall'utente e sarà abbastanza frequente, devo praticamente eliminare tutto e ricalcolare.

    Grazie ancora!

    0
  • M
    User Attivo •

    Ciao Gigi991,
    l'algoritmo di Dijkstra avevo avuto modo di studiarlo con altri linguaggi di programmazione molti anni fa per poi lasciarlo.

    Ho dato una veloce visita ai link proposti e mi sembrano interessanti. La logica implementativa ricorda quello che avevo fatto.
    Forse ho trovato anche il post in cui si trattava dei 1700 nodi in 0.5/1 secondi, e sia l'OP che coloro che partecipavano a quella discussione dimenticavano che il ciclo for() non è pienamente consigliato per lavorare con gli array che invece è il foreach(). Tra l'altro non mi sembra che vi siano modifiche al grafo per esplicitarne la chiave scalare.

    Trovo positiva l'idea di cache se fosse di possibile implementazione almeno per i percorsi comuni più richiesti.

    Un suggerimento che mi sento di dare è quello di cercare di preferire l'esecuzione di un programma in C/C++ richiamato da PHP perché più performante rispetto all'esecuzione di quest'ultimo.

    Se hai la possibilità limita il numero di richieste servibili contemporaneamente proprio per non mandare in crisi la RAM del server a causa delle ingenti risorse consumante dall'algoritmo in presenza di un grafo particolarmente complesso, oppure utilizza delle policy per favorire un certo tipo di utenza (per esempio quella pagante).

    Probabilmente per questo specifico caso il top sarebbe quello di eseguirlo con un'applicazione tipo J2EE.

    Buon lavoro e tienici informati sull'evoluzione.

    0
Effettua l'accesso per rispondere