Christofides-algoritmi (käsin)
On helmikuu 1, 2021 by adminSeuraan tätä algoritmiesimerkkiä: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [kirjoita kuvan kuvaus tähän] [1]] [1]
Calculate minimum spanning tree T:
[! [Kirjoita kuvan kuvaus tähän] [2]] [2]
Calculate the set of vertices O with odd degree in T
Sama kuin ” pienin ulottuva puu T ”, koska kaikkien huippujen aste on pariton.
Form the subgraph of G using only the vertices of O
(kuten kaikki olivat parittomia, tämän pitäisi antaa meille alkuperäinen kaavio) [! [ kirjoita kuvan kuvaus tähän] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( en ole varma teki tämän oikein ) [! [kirjoita kuvan kuvaus tähän] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [kirjoita kuvan kuvaus tähän] [4]] [4]
Tämä ei todellakaan ole oikein.
Mikä meni pieleen?
kommentit
- Huomaa: Kaikki viestin kuvat näyttävät kadonneen. Onko tekijällä satunnaisesti alkuperäisiä?
Vastaa
Itse asiassa olet ollut oikeassa koko ajan . Et kuitenkaan ole vielä valmis Christofides-algoritmiin.
Seuraava vaihe on ”Laske Euler-kiertue”.
viimeinen kuva , olet saanut monikuvan, jonka kaikki kärjet ovat tasaisia. Joten sillä on oltava Eulerin polku. Valitse esimerkiksi Eulerin polku A -> F -> A -> C -> B -> D -> E -> D -> A.
Viimeinen vaihe on ”Poista toistuvat pisteet , antamalla algoritmin ”ulostulon”.
Poistamalla toisen A ja toisen D tältä yllä olevalta polulta saadaan haluttu lähtö A -> F -> C -> B -> D -> E -> A . Valmis.
Huomaa, että Christofides-algoritmin soveltaminen annettuun kaavioon ei ole kovin järkevää.
”Christofides-algoritmi on algoritmi likimääräisten ratkaisujen löytämiseen ryhmään matkustavan myyjän ongelma , tapauksissa, joissa etäisyydet muodostavat metrisen avaruuden (ne ovat symmetrisiä ja noudattavat kolmion eriarvoisuutta ”. Annetut etäisyydet eivät noudata kolmion eriarvoisuutta, koska d (B, D) + d (D, E) = 1 + 4 < 6 = d (B Lisäksi A: n ja B: n välistä (suoraa) etäisyyttä ei anneta, mikä herättää epäilyksiä siitä, onko kyseessä ollenkaan myyntimyyjän ongelma.
Kommentit
- Olen tässä uusi, joten kiitos sivuhuomautuksista! Sain joitain kysymyksiä: 1. Pitääkö jokaisen kärjen olla yhteydessä toisiinsa, jotta se olisi kelvollinen TSP? Tarkoitan, että silti on mahdollista luoda " TSP-reitti ", vaikka reitti puuttuisi, joten sanoisin sen olevan kelvollinen – mutta Olen ollut väärässä aiemmin. 2. Luuletko (tai tiedätkö), onko mahdollista lisätä kaavioni joidenkin pisteiden painoja siten, että ne tottelevat kolmion eriarvoisuutta ? Mielestäni epäselvämmän näköiset kaaviot edustavat paremmin todellisen maailmankartan skenaarioita, joten ' siksi loin sen sellaisenaan.
- 1. Voit kohdella kuin TSP: tä, jos oletat esimerkiksi, että kaikki puuttuvat suorat etäisyydet kaupunkien välillä ovat riittävän suuria tai yksinkertaisesti äärettömiä. Tällä tavalla puuttuvat etäisyydet eivät vaikuta ratkaisuun. Se ei kuitenkaan ole metrinen avaruus. 2. Jos haluat noudattaa kolmion epätasa-arvoa, voit lisätä 10 jokaiselle määrittämäsi etäisyydelle ja antaa kaikkien puuttuvien etäisyyksien olla 20.
- Tämä ei ole totta: " Viimeisessä -kuvassa olet hankkinut monikuvan, jonka kaikilla kärjillä on tasainen aste. " – Pisteillä E, D, A ja F on pariton aste.
- " Olet saanut monikuvaaja ", kaavio, jolla saa olla useita reunoja, eli reunat, joilla on samat loppusolmut. D: n ja E: n välillä on kaksi reunaa. A: n ja F: n välillä on kaksi reunaa.
- Voit myös tarkistaa esimerkin Wikipediassa . " Se ei ole Eulerin polku, kun vierailet kärjessä useammin kuin kerran tällä polulla ". Eulerin polku tarkoittaa vierailua jokaisessa reunassa täsmälleen kerran. Puhut Hamiltonin polusta.
Vastaa