Sto passando da un manuale di algoritmi amigliorare le mie capacità algoritmiche ma sono completamente bloccato su questa domanda e mi sta infastidendo. Penso che la struttura dei dati sottostanti sia un grafico, ma non so nemmeno da dove cominciare questo problema. Qualcuno può dare qualche idea?
Ti viene fornita una mappa topografica che forniscel'altitudine massima lungo la strada diretta tra due città vicine e due città a e b. Venire con un algoritmo tempo lineare che trova un percorso da s a t che riduce al minimo l'altitudine massima. Le strade possono essere attraversato in entrambe le direzioni.
risposte:
2 per risposta № 1Questa è una domanda complicata. Suppongo che ci siano alcuni suggerimenti nel capitolo che dovrebbero guidarti verso la soluzione.
Il problema che stai descrivendo è un'istanza del problema del percorso minimax, o il problema del percorso più ampio. http://en.wikipedia.org/wiki/Widest_path_problem
Secondo wikipedia, c'è un tempo linearealgoritmo, ma è piuttosto complicato, quindi dubito che il libro si aspetti che tu lo capisca. Il modo più semplice per risolvere questo problema è trovare un albero spanning minimo. A causa della proprietà "min cut" di un albero di spanning minimo, il percorso che collega a e b lungo un albero di spanning minimo avrà la proprietà minimax, il che significa che l'altitudine massima lungo questo percorso sarà il minimo di qualsiasi percorso che connette a a b .
Tuttavia, non esiste un tempo lineare minimo di spanningalgoritmo albero. D'altra parte, se possiamo supporre che il grafico sia planare - che probabilmente possiamo poiché è una mappa stradale - allora è possibile trovare un albero di copertura minimo in tempo lineare. Quindi penso che questo sia quello che potrebbero essere dopo. Il capitolo che contiene questo problema parla di spanning tree minimi e / o di grafici planari?