Cercavo di risolvere il problema “Sentieri bollenti” usando Dijkstra, riesco a risolvere i due casi di esempio con l’algoritmo che ho scritto ma quando lo invio ricevo solo 20/100 e gli altri casi danno “Execution killed with signal 11”
Sono abbastanza sicuro che non sia perché usa troppa memoria, ma non riesco a capire dove potrebbe essere l’errore.
Non ho capito come inserire il codice e l’ho messo qui:
http://pastebin.com/vuzBewEC
Grazie.
L’errore Execution killed with signal 11 (could be triggered by violating memory limits) non è sempre indice di eccessivo utilizzo della memoria. Tra le altre cose, viene generato anche quando il programma tenta di accedere a memoria non allocata, per esempio un classico out of bound su un vettore.
Considera il seguente frammento di codice:
int a[10];
a[-1] = 5;
a[10] = 5;
Sia la seconda che la terza riga sono istruzioni pericolose, perché accedono a un’area di memoria che precede (segue) l’array a. Si ha quindi un undefined behavior.
Nel tuo sorgente questo accade alla riga 62, dove accedi a solved[chosen] con, a volte, chosen = -1. Questo accade quando il vettore to_resolve è vuoto. Lascio a te il compito di determinare perché questo accade, non avendo analizzado la strategia risolutiva che adotti.
Lucach, grazie per la risposta.
Ho modificato così la riga e provato a inviare nuovamente la sottoposizione, però ottengo gli stessi risultati di prima.
if (chosen >= 0 && chosen < n)
solved[chosen] = true;
EDIT:
Ho modificato così:
if (chosen >= 0 && chosen < n) {
solved[chosen] = true;
current_node = chosen;
} else {
break;
}
ed ho risolto il problema del killed with signal 11.
Adesso il problema è che l’output non è corretto.
Ennesima modifica. Ho riscritto l’algoritmo e sono arrivato a 70/100.
3 volte su 10 da output isn’t correct.
Questo è il codice:
http://pastebin.com/NLATUNwF
Qualcuno che riesca a capire cosa non va?
Poiché ora il problema non è più strettamente legato al codice, quanto più all’algoritmo risolutivo che hai pensato, è opportuno spiegare la tua idea di soluzione “a parole”.
Per chi vede il tuo programma da fuori è difficile capire esattamente cosa fai nella funzione dijkstra, visto che mi pare essere ben lontana dall’algoritmo di Dijkstra standard.
Come mai ti sembra essere ben lontana?
Il ragionamento è quello ed il codice è commentato.
In generale anche io penso sia una buona idea descrivere a parole l’algoritmo, perché il codice (anche se commentato) non sempre comunica esattamente le intenzioni di chi lo ha scritto.
Spesso, descrivendo l’algoritmo a parole, può addirittura succedere che il programmatore si renda conto autonomamente dell’errore nel codice: sì, il solo “spiegare” cosa fa il codice può avere questo effetto 
in gergo questa cosa viene chiamata rubber duck debugging 
Comunque stavo dando un’occhiata al codice ed effettivamente l’implementazione di Dijkstra è un po’ inusuale. Innanzitutto mi sembra che il grafo venga rappresentato tramite matrice di adiacenza, usando però i vector (che solitamente si usano nella rappresentazione mediante liste di adiacenza) invece che una matrice vera e propria del tipo int adj[MAXN][MAXN]. Inoltre vengono menzionati i parent e non è molto ovvio perché servano (io ad esempio li userei solo se dovessi stampare il cammino completo, ma questo task chiede solo il costo) né come vengano usati nella logica dell’algoritmo (dato che ci sono degli if che usano i parent).
Magari prova a spiegare a parole come hai implementato Dijkstra
P.S. c’è un task che si chiama dijkstra sul correttore, magari prova a risolvere anche quello
P.P.S. nota che per risolvere il task sentieri non è necessario implementare Dijkstra, basta una BFS modificata (hint: puoi usare due code invece che una).
Questo è l’algoritmo:
Ho il vettore costs[N] che contiene il costo minimo per arrivare al nodo i
Il vettore permanent[N] che indica se il nodo i è stato risolto
Il vettore parent[N] che indica qual è il nodo precedente al nodo i per arrivarci col costo minore
Il vettore working che contiene i nodi con cui stiamo lavorando, cioè calcolando le distanze.
costs è inizializzato a zero
il nodo di partenza è marcato come risolto
finché il nodo corrente non è quello di destinazione:
aggiungi tutti i nodi adiacenti e non risolti a working (saltando quelli già presenti)
per ogni nodo in working:
cost = il costo dell'arco che va dal nodo corrente a quello del nodo in working
se non c'è alcun percorso dal nodo corrente a quello del nodo in working (per esempio nel caso in cui il nodo sia adiacente a un nodo risolto ma non a quello corrente), cerca il suo parente in parent[nodo in working] e ricalcola cost
se cost è minore di costs[nodo in working] salva il costo minore e il parent con cui l'abbiamo trovato
se il costo per arrivare a questo nodo è la minore (o non abbiamo ancora scelto il nodo) salviamolo come nodo a cui spostarci
spostiamoci al nodo scelto e marchiamo il nodo corrente come risolto
ritorna costs[destinazione]
L’algoritmo è questo, riguardo al fatto del vector<vector> invece della matrice di int, l’ho fatto per poter usare le funzioni con vector.size(), alla fine si accede alla stessa maniera.
Ah, per risolvere il problema ai sentieri bollenti assegno un peso 1 e agli altri 0, in modo da avere come risultato il numero di sentieri bollenti percorsi.
Non capisco come usi il vettore working… praticamente è la coda?
Ma se usi i vector allora tanto vale usare le liste di adiacenza (un vector per ogni nodo, possibilmente di grandezze diverse) invece della matrice di adiacenza: nel caso di Dijkstra è più naturale usare le liste di adiacenza (e si ottiene una performance migliore) perché ad ogni step ti basta iterare sui vicini del nodo corrente, invece che dover iterare su tutti e N i nodi controllando quali sono adiacenti.
Si, working è la coda.
Appena posso proverò a modificare usando le liste di adiacenza piuttosto che la matrice.
A parte questo credo che l’algoritmo non sia errato logicamente, o sbaglio?
Se working è la coda però come mai quando aggiungi i nodi adiacenti salti quelli già presenti nella coda? Non potrebbe succedere che sono stati aggiunti in precedenza ma con un peso peggiore?
Infatti ogni volta che itero per il vettore working, controllo anche il costo e se minore, salvo quello minore, qua:
"se cost è minore di costs[nodo in working] salva il costo minore e il parent con cui l'abbiamo trovato"Però quel punto non viene raggiunto con i nodi che sono stati “saltati” perché non vengono aggiunti proprio, o no?
Dal vettore working i nodi non vengono mai rimossi, vengono solamente saltati se sono stati risolti.
Altrimenti vengono effettuati tutti i calcoli.
Comunque sto vedendo di provare un BFS modificata come hai detto tu.