Vraag Wat is het dynamisch programmeeralgoritme voor het vinden van een Hamiltoniaanse cyclus in een grafiek?


Wat is een dynamisch programmeeralgoritme voor het vinden van een Hamiltoniaanse cyclus in een niet-gerichte grafiek? Ik heb ergens gezien dat er een algoritme bij is O(n.2^n) tijd complexiteit.


17
2017-09-07 05:50


oorsprong


antwoorden:


Er is inderdaad een O (n2n) dynamisch-programmeeralgoritme voor het vinden van Hamiltoniaanse cycli. Het idee, dat een algemeen idee is dat vele O (n!) Backtracking-benaderingen van O (n22n) of O (n2n) (ten koste van het gebruik van meer geheugen), is het overwegen van subproblemen die dat wel zijn sets met gespecificeerde "eindpunten".

Hier, omdat u een cyclus wilt, kunt u beginnen bij elke hoekpunt. Dus maak een oplossing, noem het maar x. De subproblemen zouden zijn: "Voor een bepaalde set S en een top v in S, is er een pad dat begint bij x en door alle hoekpunten van S, eindigend op v? "Noem dit, zeg maar, poss[S][v].

Zoals met de meeste dynamische programmeerproblemen, is de rest duidelijk als je de subproblemen definieert: Loop over alle 2n stelt S van hoekpunten in elke "toenemende" volgorde in, en voor elke v in elke dergelijke S, kunt u berekenen poss[S][v] als:

poss [S] [v] = (er bestaat wat u in S zodanig dat poss [S- {v}] [u] Waar is en een voordeel u->v bestaat)

Ten slotte is er een Hamiltoniaanse cyclus als er een hoekpunt is v zodanig dat een rand v->x bestaat en poss[S][v] waar is, waar S is de verzameling van alle hoekpunten (anders dan x, afhankelijk van hoe je het hebt gedefinieerd).

Als je de werkelijke Hamiltoniaanse cyclus wilt in plaats van alleen maar te beslissen of er al dan niet een bestaat, maak dan poss[S][v] bewaar de feitelijke u dat maakte het mogelijk in plaats van alleen waar of onwaar; op die manier kun je aan het einde een pad terug traceren.


30
2017-09-07 06:28



Ik kan dat specifieke algoritme niet uitzoeken, maar er is meer over Hamiltonian Cycles De Hamiltoniaanse pagina dan je waarschijnlijk ooit nodig zult hebben. :)

Deze pagina is van plan een   uitgebreide lijst van papieren,   broncode, preprints, technisch   rapporten, enz. beschikbaar op de   Internet over de Hamiltoniaanse cyclus   en Hamiltonian Path-problemen ook   als sommige bijbehorende problemen.

(originele URL, momenteel 404), (Internetarchief)


3
2017-09-07 06:12