Implementazione ricerca nei grafi e sentiero minimo non pesato


#1

Ciao a tutti, ripropongo il topic perché ho notato che il precedente ha avuto poca visibilità(ipotizzo sia per la categoria in cui l’ho inserito). Spero non sia un problema, in caso cancello tutto

Ciao a tutti. Volevo chiedervi se questi due programmi sono implementazioni corrette delle ricerche DFS BFS

https://pastebin.com/DQg3tiis
https://pastebin.com/wmKSYsdr

E se questo programma sia una buona implementazione della ricerca del sentiero minimo in un grafo non pesato tra due nodi:
https://pastebin.com/ABAJ8una


#2

Quale sarebbe lo scopo della variabile r?
Comunque una miglioria che puoi fare in termini di efficienza è:
Tu al momento controlli se il nodo è gia stato visitato, se non lo è lo inserisci nella coda ma lo setti visitato solamente quando ci arriverai, invece puoi settarlo a visitato appena lo inserisci.

Ti faccio un esempio per spiegarmi meglio:
graph%20(6)

Tramite il tuo algoritmo inserisci inizialmente nella coda il nodo 0, poi l’1, il 2 il 3 ed il 4 e fino a questo punto è tutto ok. Poi andrai a prendere l’1 dalla lista e considerato che il nodo 5 non è visitato lo inserisci nella cosa, poi vai al 2 e considerato che il nodo 5 non è visitato lo inserisci nella coda e così anche per il nodo 3 e 4, andando ad inserire così 4 volte il nodo 5, anche se effettivamente le ultime 3 non è necessario.


#3

Allora, per quanto riguarda la variabile r, mi serve per capire quando ho controllato tutti i nodi di un certo “livello” ovvero, prendendo ad esempio il tuo grafo, mi serve per capire quando ho controllato tutti i nodi al “livello 1”(quelli con distanza di un lato dal nodo di partenza: 1,2,3,4) per poi continuare col livello 2 e via via finché non ho visitato il grafo intero. Questo era l’unico modo che mi è venuto in mente per un algoritmo in grado di restituirmi il sentiero minimo tra due nodi in un grafo non pesato. In locale sembra funzionare, per te la logica sotto il programma è ok?

Invece, per quanto riguarda la miglioria, ti riferisci al terzo programma che ho inviato o a tutti e tre? Comunque, non credo di aver capito bene cosa intendi


#4

Effettuando una semplice bfs riesci a calcolare il percorso minimo in un grafo non pesato.
Basta utilizzare una coda e due vettori.
Un vettore per la distanza e uno per verificare se hai già visitato un nodo.
Volendo puoi usarne anche uno solo.
Se ti vuoi esercitare con il percorso minimo in un grafo non pesato prova spesa lampo, è molto carino come esercizio.
Ti consiglio di leggere questo post dove ho scritto un bel po’ di cose sui grafi con le implentazioni delle due ricerche.


#5

Grazie mille per i link, ma non ho ancora capito se il mio metodo sia un buon metodo :frowning_face:


#6

Fin quando risolve il problema correttamente tutto è un buon metodo XD
Se poi cerchi una soluzione più elegante, veloce e facile da scrivere è un’altro discorso.


#7

Capisco, chiedevo perché in locale funzionerebbe ma ho sempre paura che siano casi specifici e che non sia perfetto come metodo. A te sembra funzionare?


#8

Il ragionamento mi sembra corretto.
Aumentare la distanza solo dopo aver esaminato tutti i nodi della distanza attuale.
Se riesci a implementare le migliorie consigliate sopra è anche meglio.
Se hai paura che non sia corretto il codice un buon metodo è creare dei test case che mettono a dura prova l’algoritmo oppure provarlo direttamente su un problema.
Fai una ricerca per tag graphs e trova un esercizio in cui è richiesta questa tecnica.
Uno tra questi è spesa lampo.


#9

Grazie mille. Un’altra cosa: cosa intendeva frakkiobello? Che non dovrei aggiungere i nodi già visitati per rendere più efficiente il programma?


#10

Esatto.
É inutile inserire nodi nella coda se sono già visitati.
Quando controlli che il nodo non è stato visistato lo inserisci nella coda e lo imposti come visistato.
In questo modo non verrà inserito di nuovo da altre sue adiacenze.


#11

Cerco di spiegarmi meglio:
Partiamo utilizzando l’algoritmo che avevi scritto tu sul grafo che ho postato io:

Nodo di partenza il nodo 0, quello di arrivo il nodo 5.
coda:0, visitati:
Togli lo 0 , coda: e lo visiti visitati:0 Iteri sui vicini dello 0:
Nodo 1, non è stato visitato allora lo inserisci nella coda coda:1
Nodo 2, non è stato visitato allora lo inserisci nella coda coda:1,2
Nodo 3, non è stato visitato allora lo inserisci nella coda coda:1,2,3
Nodo 4, non è stato visitato allora lo inserisci nella coda coda:1,2,3,4

Togli l’1 e lo visiti coda:2,3,4, visitati:0,1 Iteri sul vicini dell’1
Nodo 0, è stato visitato, quindi non fai nulla.
Nodo 5, non è stato visitato quindi lo inserisci in coda coda:2,3,4,5

Togli il 2 e lo visiti coda:3,4,5,, visitati:0,1,2 Iteri sul vicini dell’2
Nodo 0, è stato visitato, quindi non fai nulla.
Nodo 5, non è stato visitato quindi lo inserisci in coda coda: 3,4,5,5

Togli il 3 e lo visiti coda:4,5,5, visitati:0,1,2,5 Iteri sul vicini dell’3
Nodo 0, è stato visitato, quindi non fai nulla.
Nodo 5, non è stato visitato quindi lo inserisci in coda coda: 4,5,5,5

Togli il 4 e lo visiti coda:5,5,5,, visitati:0,1,2,3,4 Iteri sul vicini dell’4
Nodo 0, è stato visitato, quindi non fai nulla.
Nodo 5, non è stato visitato quindi lo inserisci in coda coda: 5,5,5,5

Già qui ti accorgi che nella coda hai 4 volte lo stesso nodo ed è sicuramente uno speco di tempo, considerando che in questo piccolo esempio sono 4 le occorrenze ma aumentando il numero di nodi collegati tra 0 e 5 aumenterebbero anche le occorrenze del 5 nella coda.

La miglioria che ti avevo proposto consiste nel settare il nodo 5(ovviamente anche gli altri nodi) visitati nel momento in cui li inserisci nella coda.
In questo modo quando arrivavi al nodo 2 e trovavi come vicino il 5, vedendo che è già stato visitato eviti di inserirlo nuovamente.

Spero di essermi spiegato meglio.

Fabio.


#12

An capito, in effetti è più efficiente. Grazie mille


#13

A proposito, stavo provando il problema “spesa lampo” ma mi sorge un dubbio: nell’esempio 2 danno un arco che unisce il nodo 6 e il nodo 5 ma nell’esempio in figura più sotto i due nodi non sono collegati, non capisco


#14

In effetti manca ma non cambia il risultato.