Complessità Dijkstra (Footing)

Algoritmi
1

Ciao a tutti, sto risolvendo il problema Footing, e tutto sembra funzionare, se non per gli ultimi due testcase nei quali supero il limite di tempo.
La domanda è quindi come posso ridurre la complessità dell’algoritmo?
In pratica, ho implementato un algoritmo di Dijkstra modificato, in modo che cerchi un cammino minimo rimuovendo un arco, in modo che poi, aggiungendo l’arco tolto formo un ciclo per trovare il minimo ciclo semplice. Tutto sembra funzionare, a livello di correttezza.

La coda di priorità me la sono implementata da solo (da amante del C quale sono (e anche per familiarizzare con le implementazioni dei concetti che ho appreso)), e l’ho modellata come un Min-Heap binario, in modo che tutte le operazioni costino al massimo O(log n).
Nel codice principale, eseguo Dijkstra partendo da ogni arco, saltando l’arco corrente. Purtroppo non mi viene in mente nessun modo per ridurre la complessità, se non usare una coda più efficiente. Voi avete qualche idea?

Il codice è il seguente, spezzato in tre file (ma poi chiaramente sottomesso come unico file) per leggerlo meglio. Del file principale riporto solo il cuore della questione. Il grafo è implementato con liste di adiacenza (che si trovano nell’array vertici), e il tipo node è un alias per il tipo type definito nel .h.

Minqueue.h: http://pastebin.com/52haZ7WR
Minqueue.c: http://pastebin.com/5kTMm5zV
Core: http://pastebin.com/2r7zDcZQ

Grazie per la pazienza.

2

Ciao,
il problema, con relativa complessità computazionale, è già stato discusso in questo intervento sul forum, che ti consiglio di leggere.

Inoltre anche il booklet della selezione territoriale 2015 descrive la soluzione del problema, a cui sei già arrivato, accennando possibili migliorie.

1 Mi Piace
3

Allora, il booklet lo avevo letto già prima di iniziare l’esercizio, per avere un’idea della soluzione, ma non volevo copiare troppo. Comunque funzionava ma ci stava troppo tempo negli ultimi due testcase. Da qui un’odissea di 3 giorni per cercare di migliorare il tutto, anche leggendo il thread che mi hai linkato, ma niente. O non funzionava o ci stava comunque troppo tempo. Alla fine ho quindi ripiegato su una copia spudorata della soluzione che è su GitHub, trascrivendola in C. Ma anche qui niente, ora il risultato che mi dà è 6 anziché 8, problema già ritrovato nel tuo link, ma avendo praticamente copiato la vostra soluzione non riesco proprio a capire dove si nasconda il problema.
Lascio il codice, consapevole che poi l’errore sarà una cavolata e mi mangerò le mani per una settimana.

http://pastebin.com/CmNeXnc7

Grazie per la pazienza, ma davvero: non so più dove mettere le mani. :sweat_smile:

4

Questa volta il problema è più sottile e risiede interamente nella tua implementazione della coda con priorità.
In particolare mi ha destato preoccupazione questa parte:

bool enqueue(type elem) {
    int i;
    for(i=0;i<length;i++) {
	if(heap[i].nodo == elem.nodo) {
	    change_priority(elem, i);
	    return true;
	}
    }
    [...] // Esegue l'enqueue
}

Significa che non accodi mai due elementi con lo stesso nodo (che nel caso specifico è il “nodo destinazione”), perché se così fosse, anziché inserire il secondo, cambi la priorità di quello già esistente.

Il punto è che questo approccio non può funzionare per il problema in questione. Considera il caso in cui volessi accodare le seguenti due triple (dove i valori sono rispettivamente il nodo, il peso e il predecessore): (2,8,1) e (2, 6, 5). Con la tua implementazione della coda risulterebbe presente una sola tripla (2, 6, 1) che peraltro è un miscuglio tra il nuovo peso e il vecchio predecessore.

Una correzione veloce consiste nel rimuovere le righe di codice indicate sopra; ciò ripristina la correttezza della soluzione.