Domanda su task footing

Ho un dubbio per quanto riguarda l’esercizio 3. In pratica si aveva un grafo pesato e bidirezionale, e N nodi. Bisognava trovare il percorso chiuso più breve (di almeno tre nodi e passando solo una volta per uno stesso nodo). Io l’ho risolto facendo partire una dfs da ogni nodo, e poi entravo in un determinato nodo solo se la distanza dal nodo di partenza era minore, di quella memorizzata. Se tornavo al nodo di partenza dopo essere passata per almeno 3 nodi, la confrontavo la soluzione globale, con la soluzione temporanea. Secondo voi va bene? (i limiti erano N \le 1000 e numero strade \le 10000). C’era un modo più semplice per risolverlo?

Altra cosa, secondo voi quanti punti servono per essere ripescati dalla classifica nazionale?

1 Mi Piace

Ho spostato 3 messaggi in un argomento esistente: Testi problemi territoriali

1 Mi Piace

Dovrebbe dare il risultato corretto (alla fine le provi tutte), però la complessità mi sembra esponenziale dato che alla peggio visiti tutti i possibili cicli e in un grafo completo hai O(2^n) cicli :stuck_out_tongue:

1 Mi Piace

Avevo aggiunto anche un uscita, nel caso in cui la distanza corrente fosse maggiore della soluzione migliore trovata fino a quel momento. ma la complessità non dovrebbe essere N*M (*N perchè lo devi ripetere per tutti i nodi, quindi alla fine N^2*M)?

1 Mi Piace

Quello che fai è semplicemente un pruning, ma resta comunque esponenziale nel caso peggiore.

1 Mi Piace