Wat betekent relaxation of an edgein de context van grafentheorie? Ik kwam dit tegen tijdens het bestuderen van Dijkstra’s algoritme voor het kortste pad met één bron.
Antwoord 1, autoriteit 100%
Hier iseen mooie beschrijving van het algoritme dat ook de begrip ontspanning.
Het begrip ‘ontspanning’ komt voort uit een analogie tussen de schatting
van de kortste weg en de lengte van een spiraalvormige trekveer, die
is niet ontworpen voor compressie. Aanvankelijk, de kosten van de kortste
pad is een overschatting, vergeleken met een uitgestrekte bron. als korter
paden worden gevonden, de geschatte kosten worden verlaagd en de veer is
ontspannen. Uiteindelijk wordt het kortste pad, als dat bestaat, gevonden en
de veer is ontspannen tot zijn rustlengte.
Antwoord 2, autoriteit 57%
Het relaxatieproces in Dijkstra’s algoritme verwijst naar het bijwerken van de kosten van alle hoekpunten die zijn verbonden met een hoekpunt v, als die kosten zouden worden verbeterd door het pad via v op te nemen.
Antwoord 3, autoriteit 20%
Door een rand te ontspannen (een concept dat je ook in andere algoritmen met de kortste weg kunt vinden) probeert men de kosten om naar een hoekpunt te gaan te verlagen door een ander hoekpunt te gebruiken.
Je berekent de afstanden vanaf een beginnend hoekpunt, zeg S, tot alle andere hoekpunten. Op een gegeven moment heb je tussenresultaten – huidige schattingen. De versoepeling is het proces waarbij je voor sommige hoekpunten uen vcontroleert:
if directly_connected(v, u)
if est(S, v) > est(S, u) + dist(u,v)
est(S, v) = est(S, u) + dist(u, v)
waarbij est(S,a)de huidige schatting van de afstand is, en dist(a,b)de afstand is tussen twee hoekpunten die buren zijn in de grafiek.
Wat u in feite controleert tijdens het ontspanningsproces is of uw huidige schatting van atot bkan worden verbeterd door het pad door c(deze “omleiding” zou de lengte zijn van een pad van anaar cen van cnaar b).
Antwoord 4, autoriteit 2%
Randontspanningsproces
Initialisatie
In algoritmen met het kortste pad wijst u eerst een padkosten van nul toe aan een startknooppunt (bijv. S) en een padkosten van oneindig aan elk ander knooppunt (bijv. A, E).
S := new Node()
A := new Node()
E := new Node()
// To go from S to S is zero
S.path_cost = 0
// high cost
A.path_cost = 1000 // "infinity"
E.path_cost = 1000 // "infinity"
Randrelaxatie
Oneindigheid is de hoogste prijs die we zouden kunnen hebben, dus we willen ‘ontspannen’, indien mogelijk, terugbrengen tot lagere kosten. Om dat te doen berekenen we de kosten van een pad (bijv. aof ab) tussen het startknooppunt en een ander knooppunt, en werken de padkosten voor het knooppunt bij, als dat padkosten zijn lager.
a := 3
b := 5
SS := S.path_cost + 0
if (S.path_cost > SS) {
// 0 !> 0 + 0
S.path_cost = SS
}
Sa := S.path_cost + a
if (A.path_cost > Sa) {
// 1000 > 0 + 3
A.path_cost = Sa
// A = 0 + 3
}
ab := A.path_cost + b
if (E.path_cost > ab) {
// 1000 > 3 + 5
E.path_cost = ab
// E = 3 + 5
}
Randrelaxatie herhaald
c := 1
Sc := S.path_cost + c
if (E.path_cost > Sc) {
// 8 > 0 + 1
E.path_cost = Sc
// E = 0 + 1
}
Antwoord 5
Laten we veronderstellen in de grafiek als we (u, v) ∈ e hebben waar w (u, v) = 10
Als het dan door het toevoegen van een derde vertex tussen hen als w (u, y) = 1 en w (y, v) = 3 nu vinden we een pad tussen u en v met gewicht 1 + 3 = 4 & lt; 10. Nu zullen we het tweede pad als kortste beschouwen dat (u, y, v) is en de eerste zal negeren, dit is ontspanning.
Antwoord 6
Edge ontspanning.
om een rand V – & GT te ontspannen; W betekent te testen of de bekendste weg van
S tot W is van S tot V en neem dan de rand van V naar W en, zo ja,
Werk onze gegevensstructuren bij.
Java-code:
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to;
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
Er is ook vertex ontspanning. Dat betekent om alle randen te ontspannen die van een gegeven hoekpunt wijzen.
private void relax(EdgeWeightedGraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
relax(e);
}
}