Perché lo chiamiamo "Relax" un vantaggio?

Nell'algoritmo del percorso più breve di Dijkstra e altri, esaminare un bordo per vedere se offre un percorso migliore per un nodo è indicato come rilassante al limite. Perché si chiama rilassante?Perché lo chiamiamo "Relax" un vantaggio?

fonte

2012-05-24 Eric G

In generale matematicamente, rilassamento sta apportando una modifica che riduce i vincoli. Quando l'algoritmo Dijkstra esamina un bordo, rimuove un bordo dal pool, riducendo in tal modo il numero di vincoli.

Non è una terminologia orribilmente utile, ma pensa a quanto sei bravo a dirlo.

fonte

2012-05-24 23:58:51

Potrebbe chiarire come i bordi della piscina possono essere visti come vincoli? –

Pensa a un vertice con un sacco di bordi in arrivo. Quando si avvia, la soluzione deve includere il peso dal primo bordo, dal secondo bordo e così via. In effetti, per i bordi a, b, c, d ed e, inizi a dire "il percorso più breve deve includere a, b, c, d, e". Quindi elimini e, e ora sai che deve includere solo "a, b, c, d". Ogni passaggio è un * rilassamento * perché in ogni fase viene rimossa una condizione che la soluzione corrente impone. –

Suppongo che non sia "entrarci" ma "lasciarlo"? –

Perché lo chiamiamo "Relax" un vantaggio?

risposta

Problemi correlati