Jak na TSP - Analytické myšlení - Uspořádání

1. Sestavení stromu (schématu) uspořádání

Velice užitečnou pomůckou při řešení těchto příkladů je nákres stromu uspořádání. Ukažme si tedy, jak se strom uspořádání vytváří, a také, jak se s ním pracuje, jelikož to nemusí být zcela intuitivní.

Nejdříve odlišný pohled na situaci - pro lepší pochopení:

Máme tedy pětici přítelkyň s různým věkem a zajímá nás jejich celkové uspořádání. Už na základě první věty si můžeme uvědomit, že lze situaci popsat výčtem všech konkrétních možností, jak mohou být tyto přítelkyně uspořádány od nejstarší po nejmladší. Takových možností, jak je vzájemně uspořádat je právě n!... (permutace n prvků do n pozic). Jelikož umisťujeme 5 přítelkyň - možných uspořádání je 5! tedy 120.

Další věty nám situaci blíže popisují - jedná se tedy o jistá omezení situace:

• A je starší než C (A>C)
• B je starší než A (B>A)
• D je starší než E (D>E)
• E je starší než C (E>C)

Každé porovnání dvojic nám z těchto 120ti možností eliminuje jisté možnosti - například, porovnání A>C nám eliminuje ty možnosti, kde C>=A (jelikož má každá z přítelkyň různý věk, stačí psát C>A). Pokud si vyškrtáme možnosti odporující všem výše zmíněným odrážkám, zůstanou nám pouze ty, odpovídají našemu zadání.

Pozn. Tento pohled na příklady je také popsán v druhé části 5. videa - od 8:06.

Nyní už k sestavování stromu:

Výše zmíněný postup je příliš zdlouhavý a těžkopádný, vzhledem k velkému množství možností, ze kterých vycházíme. Eliminovat nevyhovující možnosti lze naštěstí i rychlejším způsobem - právě pomocí sestavení stromu uspořádání.

Načrtneme si, jak lze postupovat na základě informací z odrážek: