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
editovatUvedená 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
editovatJen 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)
editovatObrá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)