Pomoc s příkladem - Obchodní cestující

[Ellrohir]

Zadání :

Na zaciatku vytvoríme cyklus z jednoho lub. bodu.
V jednotlivých krokoch postupne hladáme vrchol u, ktorý
nie je v cykle a je najbližšie k cyklu, k nejakému vrcholu
v. Rozšírime cyklus pridaním u za v a opakujeme, kým
v cykle nie sú všetky vrcholy. Ukážte, že táto heuristika
vracia cyklus, ktorý je najviac dvaktát dlhší než optimálna
cesta (pri platnosti trojuholnikovej nerovnosti).

[Ellrohir]

tak mi bylo porazeno, že důkaz má co dělat s důkazem správnosti Algoritmu obchodního cestujícího...což dává rozhodně větší smysl než ten můj "původní" návrh (který nezohlednil, že půjde o graf s ohodnocenými hranami)

nicméně ani to mi zatím moc nepomohlo, protože Mareš ve svých skriptech má ten agloritmus popsaný podle mého jinak než vypadá tahle Hricova heuristika (aspoň mi to tak přijde - "udělat minimální kostru, tu obejít sledem a pak ten sled postupně "předělávat" až to bude cyklus" se mi nezdá shodný s tímhle "udělat cylkus 3 vrcholů a přidávat další" ), takže z toho pořád nejsem moudrej fakt nikdo tohle neví? prej jsme to "určitě dělali na přednášce"...

[Osiris]

...

Nedala by se využít nějak myšlenka ze stavění MINIMÁLNÍ kostry? Pokud stavíš minimální kostru, tak to můžeš udělat tak, že začneš s pseudokostrou, která obsahuje jeden vrchol a přidáváš ty hrany, které jsou nejmenší, až posléze dostaneš kostru (spotřebuješ všechny vrcholy). Tohle je stejné, akorát s cyklem, mělo by to jít nějak modifikovat, nebo ne?

[Ellrohir]

no kdybych věděl, jak to udělat, tak se tu neptám...

když podle tý heuristiky přidávám vrchol do už existujícího cyklu, tak se délka cyklu zmenší o délku jedné hrany a prodlouží o délku 2 nově vzniklých hran...ale o těch vzniklejch hranách neumím podle mého říct nic než to, že budou dohromady delší, než ta zmizelá, což mi ale není celkem k ničemu...no a ještě taky vím, že délka jedné z těch dvou hran je nejmenší možná - přidávám vrchol "nejblíže k cyklu"...ale co z toho? furt mi nic v hlavě nesecvakává...

[hippies]

,,Nejblize k cyklu" - nejblize k vrcholu v cyklu = hledani minimalni kostry. Pokud to nebude k vrcholum, ale budes uvazovat i hrany, tak si muzes jen polepsit (vrchol je konec hrany) .. jeste musis ukazat, ze si muzes jen polepsit, nad tim se mi nechce ted dumat.

[Ellrohir]

možná planej poplach, ale myslím, že se myšlenka objevila a už to dohromady dám každopádně díky za "nakopnutí"