A*con iterazione della profondita
Salve, durante la ricerca del percorso ottimo dopo averlo trovato applico il DFS sul nodo di partenza fino a quando trovo il nodo di arrivo, è corretto?
Risposte
In che senso? Dopo che hai trovato il nodo di arrivo perché dovresti ripartire da capo per ritrovarlo? Se provi a postare lo pseudocodice o riferimento all'algoritmo esatto di cui stai parlando forse riusciamo a capirci meglio.
"apatriarca":
In che senso? Dopo che hai trovato il nodo di arrivo perché dovresti ripartire da capo per ritrovarlo? Se provi a postare lo pseudocodice o riferimento all'algoritmo esatto di cui stai parlando forse riusciamo a capirci meglio.
No nel senso, quando trovo il nodo di arrivo devo solo colorare i vertici quelli visitati del percorso, giusto? Io volevo fare che dopo aver trovato il percorso ottimo parto dal nodo di partenza per visitare in profondità per essere più preciso per visitare i nodi.
Più preciso in che senso? Da quale punto di vista? Una volta che sei arrivato alla fine dovresti già avere il percorso ottimale* da seguire per arrivare a destinazione..
* A patto ovviamente di rispettare le condizioni richieste dall'algoritmo per un percorso ottimale. A volte queste condizioni non sono rispettate per scelta o necessità..
* A patto ovviamente di rispettare le condizioni richieste dall'algoritmo per un percorso ottimale. A volte queste condizioni non sono rispettate per scelta o necessità..
"apatriarca":
Più preciso in che senso? Da quale punto di vista? Una volta che sei arrivato alla fine dovresti già avere il percorso ottimale* da seguire per arrivare a destinazione..
* A patto ovviamente di rispettare le condizioni richieste dall'algoritmo per un percorso ottimale. A volte queste condizioni non sono rispettate per scelta o necessità..
Nel sens che da visitare tutti i possibili nodi in profondita fino al nodo di arrivo, oppure devo semplicemente solo colorare i nodi visitati del percorso con i relativi tempi?
Ho l'impressione che la tua domanda abbia nulla a che fare con l'algoritmo.. Che cosa devi fare? Perché dovresti "colorare" i nodi visitati con i relativi tempi? Per qualche ragione dovresti visitare tutti i nodi in profondità? A* può essere applicato a casi in cui il grafo abbia un numeri di nodi infinito o molto grandi per cui la visita in profondità è in generale qualcosa che non va fatto, ma forse il tuo problema specifico lo richiede.. Non posso darti una risposta senza avere idea di cosa tu stia cercando di fare (certamente non implementare l'algoritmo A* per cui è tutto finito una volta che hai trovato il percorso ottimale).
"apatriarca":
Ho l'impressione che la tua domanda abbia nulla a che fare con l'algoritmo.. Che cosa devi fare? Perché dovresti "colorare" i nodi visitati con i relativi tempi? Per qualche ragione dovresti visitare tutti i nodi in profondità? A* può essere applicato a casi in cui il grafo abbia un numeri di nodi infinito o molto grandi per cui la visita in profondità è in generale qualcosa che non va fatto, ma forse il tuo problema specifico lo richiede.. Non posso darti una risposta senza avere idea di cosa tu stia cercando di fare (certamente non implementare l'algoritmo A* per cui è tutto finito una volta che hai trovato il percorso ottimale).
Allora, il mio obiettivo è di realizzare un algoritmo con a in profondita con un numero di nodi finiti.
Io ho semplicemente trovato il percorso migliore siccome e con dfs devo colorare tutti i nodi visitati compresi quelli non inclusi nel percorso con i relativi colori e tempi, giusto?
l'algoritmo A*devo applicarlo per forza dopo aver trovato il percorso migliore perchè devo verificare le condizione per trovare il percorso ottimo compreso la disiguaglianza.
Prima trovo il percorso migliore, poi applico algoritmo A* con le condizioni e poi li devo colorare tutto questo devo fare, o no?
No, A* è un algoritmo per trovare il percorso migliore per cui non ha senso applicare l'algoritmo se già conosci tale percorso. A* come algoritmo non richiede né passaggi precedenti, né successivi alla sua esecuzione. Semplicemente visiti i nodi in base al loro costo e al valore associato al nodo dall'euristica..
"apatriarca":
No, A* è un algoritmo per trovare il percorso migliore per cui non ha senso applicare l'algoritmo se già conosci tale percorso. A* come algoritmo non richiede né passaggi precedenti, né successivi alla sua esecuzione. Semplicemente visiti i nodi in base al loro costo e al valore associato al nodo dall'euristica..
Io volevo fare di visitare i nodi nel seguente modo:
1 visita 234
234 sorgenti che visitano gli altri nodi fino a trovare la destinazone.
Cosi va bene?
Ma questo non ha nulla a che fare cone A*..
"apatriarca":
Ma questo non ha nulla a che fare cone A*..
scusi, ho sbagliato, devo solo determinare il percorso ottimo in base al costo, giusto?
Sì.. Ma continuo a non capire la tua problematica..
"apatriarca":
Ma questo non ha nulla a che fare cone A*..
Salve, per trovare il percorso ottimo con IDA* espando i nodi con una ricerca in profondità, se questa ricerca termina con un nodo obiettivo , ha trovato ovviamente un percorso a costo minimo per l'obiettivo.
Questa è la definizione, quindi basta trovare solo un percorso?
Questo è il mio problema , se è così allora il percorso ottimo lo trovato
perchè su un algoritmo che ho trovato di dijsktra opera cosi, si ferma al primo percorso
Sì, ti fermi quando hai trovato il percorso.
cancellato
Ho l'impressione che tu stia cercando di implementare qualcosa che non capisci. Il mio consiglio è di smettere di cercare di implementarlo basandoti su idee astratte e imprecise di come dovrebbe funzionare e di partire da un qualche pseudocodice o descrizione dettagliata dello stesso.
P.S. Cerca di formattare un po' meglio il codice che così è molto difficile leggerlo..
P.S. Cerca di formattare un po' meglio il codice che così è molto difficile leggerlo..
cancellato
Dipende ovviamente molto da come sono definiti il grafo e l'insieme dei nodi. La rappresentazione più comoda in questo caso sarebbe la matrice di adiacenze e un vettore di lunghezza uguale al numero di nodi per l'insieme. In questo caso sarebbe infatti sufficiente moltiplicare la matrice per il vettore e ottenere quindi il vettore delle destinazioni (e sarebbe sufficiente controllare semplicemente il valore corrispondente del vettore per sapere se la destinazione è stata raggiunta o meno).
Un po' più complicato (e computazionalmente pesante) è ottenere tutti i percorsi. L'idea principale è comunque di prendere un percorso per volta, prendere il nodo finale del percorso e quindi aggiungere un percorso per ogni nodo raggiungibile dalla destinazione. Nota che il numero di percorsi cresce abbastanza velocemente.. Non è cosi che si affronta normalmente il problema..
Un po' più complicato (e computazionalmente pesante) è ottenere tutti i percorsi. L'idea principale è comunque di prendere un percorso per volta, prendere il nodo finale del percorso e quindi aggiungere un percorso per ogni nodo raggiungibile dalla destinazione. Nota che il numero di percorsi cresce abbastanza velocemente.. Non è cosi che si affronta normalmente il problema..
"apatriarca":
Dipende ovviamente molto da come sono definiti il grafo e l'insieme dei nodi. La rappresentazione più comoda in questo caso sarebbe la matrice di adiacenze e un vettore di lunghezza uguale al numero di nodi per l'insieme. In questo caso sarebbe infatti sufficiente moltiplicare la matrice per il vettore e ottenere quindi il vettore delle destinazioni (e sarebbe sufficiente controllare semplicemente il valore corrispondente del vettore per sapere se la destinazione è stata raggiunta o meno).
Un po' più complicato (e computazionalmente pesante) è ottenere tutti i percorsi. L'idea principale è comunque di prendere un percorso per volta, prendere il nodo finale del percorso e quindi aggiungere un percorso per ogni nodo raggiungibile dalla destinazione. Nota che il numero di percorsi cresce abbastanza velocemente.. Non è cosi che si affronta normalmente il problema..
Allora il secondo punto lo svolto ma il problema e che se non trovo la destinazione ovviamente prosegue con un loop fino a quanto la raggiunge e siccome non la raggiunge come lo posso risolvere per uscirne.
Un metodo potrebbe essere quello di eliminare i cicli verificando ad ogni iterazione se il nodo di destinazione sia già comparso nel percorso corrente. Se non è possibile trovare un nuovo percorso allora semplicemente cancelli il percorso e consideri solo gli altri. Spero che l'idea sia chiara.
cancellato
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo