Math
La via più economica
Un terreno dove un passo costa il prezzo della cella in cui entri, e l'onda dei vertici chiusi si allarga per PREZZO e non per distanza. Un cursore posa un arco negativo sulla mappa e ha tre regimi misurati.
Cosa succede
Qui un passo costa il prezzo della cella in cui entri, quindi l'onda dei vertici chiusi non si allarga in cerchi: corre lontano in una conca economica e si ferma contro una dorsale cara. Quell'immagine è tutta la differenza fra una visita in ampiezza e questa. Finché i pesi non sono negativi la risposta è dimostrabilmente minima, e qui si verifica contro Bellman-Ford rilassato fino al punto fisso - mai contro una seconda esecuzione dello stesso algoritmo - e sulle griglie piccole contro l'enumerazione completa dei cammini semplici. Su terreno piatto il costo ha forma chiusa, w(i + j), perché ogni via monotona costa uguale. Anche i contatori sono identità: ogni vertice si chiude esattamente una volta e ogni arco si rilassa esattamente una volta, 4m(m−1) archi. Poi il cursore posa un solo arco diretto negativo, e ha tre regimi, tutti misurati e non descritti. Fino a −15 non si rompe nulla: un arco negativo da solo non è un problema. Da −16 a −50 Dijkstra risponde 93 dove la verità è 92, poi 78, poi 58 - sempre TROPPO ALTO, perché un vertice chiuso non si riapre - e accanto alla via gialla compare quella vera, perché l'errore si veda invece di essere dichiarato. A −51 nasce un ciclo negativo: non esiste alcun cammino minimo, Bellman-Ford lo dice, e Dijkstra stampa gli stessi 93 impassibile.
Equazioni del modulo
Equazioni terreno su una griglia m x m, ogni cella con un prezzo 1..9, un passo costa il prezzo della cella in cui si entra; partenza in alto a sinistra, meta in basso a destra con pesi non negativi Dijkstra è corretto - verificato con Bellman-Ford rilassato fino a un punto fisso e, su 3x3 e 4x4, con l'enumerazione COMPLETA dei cammini semplici il terreno piatto ha una forma chiusa: costo fino a (i, j) = w(i + j), quindi la meta costa w·2(m−1) - 120 per w = 5, m = 13 vertici fissati = m² (ognuno chiuso esattamente una volta); rilassamenti = archi = 4m(m−1) = 624 a m = 13; inserimenti nella coda di priorità 169 sul terreno predefinito 13x13 predefinito, sconto disattivato: percorso più economico verso la meta 93, lo stesso 93 da Bellman-Ford, 25 celle nel percorso, 0 celle in cui i due non concordano un arco orientato di sconto da (0,7) a (5,0), e il cursore ha TRE regimi, tutti misurati: fino a −15: nessun errore - un arco negativo non è di per sé un problema da −16 a −50: Dijkstra restituisce 93 mentre il valore vero è 92, 78, 58 - sempre TROPPO GRANDE, e le risposte non concordano su 65, 122, 159 delle 169 celle da −51 in giù: un ciclo negativo - non esiste un cammino minimo, lo dice Bellman-Ford, e Dijkstra stampa comunque 93 gli estremi dell'arco di sconto sono stati scelti enumerando tutte le coppie: l'intervallo utile richiede d(lontano) − d(vicino) < k < cost(vicino a lontano), ed è vuoto quando il percorso economico verso la cella lontana passa per quella vicina
