Diskuse:Problém obchodního cestujícího

Příklad nedává smysl, protože uvedené vzdálenosti nelze vůbec vynést - nejde zobrazit. 89.190.64.53 20. 11. 2008, 14:45 (UTC)

Musíte si představit, že ty silnice nejsou vždy rovné, ale mohou být - tak jako v reálu - i všelijak klikaté. Pak to zobrazíte snadno.--Ioannes Pragensis 20. 11. 2008, 14:53 (UTC)

Složitost

Uvedená verze problému není NP-úplná ale NP-těžká. Úplná je jeho rozhodovací (ANO/NE) verze. viz en:Travelling_salesman_problem#Computational_complexity. Jary 30. 6. 2009, 18:47 (UTC)

Příklad

Jen pro přesnost: cesta A → D → C → B → A je stejně krátká jako cesta A - B - C - D - A, není tudíž nejkratší, protože existuje alespoň jedna další cesta, která je stejně dlouhá.

Ne oboje jsou nejkratší, neboť není žádná kratší. Nebo jste někde viděl požadavek na jedinečnost nejkratší cesty v grafu? Zagothal 29. 4. 2011, 09:34 (UTC)

Obrázek není názorný (neodpovídají poměry velikostí hran)

Obrázek vypadá jako obdélník. Ale zjevně jím není - u obdélníku jsou protilehlé strany stejně dlouhé, tady hrana AB má jinou velikost než CD. Taktéž uhlopříčky mají zkreslující velikosti. Takže obrázek výrazně mate, hrany, které jsou opticky delší, jsou dle popisu kratší. U grafu se čtyřmi vrcholy by se určitě dal vytvořit obrázek, který by poměrově odpovídal, aby to bylo názorné.

S přátelským pozdravem Rwiener (diskuse) 19. 9. 2018, 14:36 (CEST)