Problémy cestujícího obchodníka dodržuje obchodník a soubor měst. Prodejce musí navštívit každé z měst počínaje určitým (např. rodné město) a vrátit se do stejného města. Problémem je, že obchodní cestující musí minimalizovat celkovou délku cesty.
Předpokládejme, že města jsou x1X2..... Xnkde stojí cijoznačuje náklady na cestu z města xido xj. Problémem cestujícího prodejce je najít trasu začínající a končící v x1která zabere všechna města s minimálními náklady.
Příklad: Novinový agent denně hází noviny do přidělené oblasti tak, že musí pokrýt všechny domy v příslušné oblasti s minimálními cestovními náklady. Vypočítejte minimální cestovní náklady.
Oblast přidělená agentovi, kam má odhodit noviny, je znázorněna na obr.
Řešení: Matice cenové přilehlosti grafu G je následující:
nákladyij=
Prohlídka začíná z oblasti H1a poté vyberte minimální nákladovou oblast dosažitelnou z H1.
Označte oblast H6protože je to oblast s minimálními náklady dosažitelná z H1a poté vyberte minimální nákladovou oblast dosažitelnou z H6.
Označte oblast H7protože je to oblast s minimálními náklady dosažitelná z H6a poté vyberte minimální nákladovou oblast dosažitelnou z H7.
Označte oblast H8protože je to oblast s minimálními náklady dosažitelná z H8.
Označte oblast H5protože je to oblast s minimálními náklady dosažitelná z H5.
Označte oblast H2protože je to oblast s minimálními náklady dosažitelná z H2.
Označte oblast H3protože je to oblast s minimálními náklady dosažitelná z H3.
Označte oblast H4a poté vyberte minimální nákladovou oblast dosažitelnou z H4je to H1.Takže pomocí chamtivé strategie dostaneme následující.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
Tedy minimální cestovní náklady = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroidy:
Matroid je uspořádaný pár M(S, I) splňující následující podmínky:
- S je konečná množina.
- I je neprázdná rodina podmnožin S, nazývaná nezávislé podmnožiny S, taková, že pokud B ∈ I a A ∈ I. Říkáme, že I je dědičné, pokud splňuje tuto vlastnost. Všimněte si, že prázdná množina ∅ je nutně členem I.
- Jestliže A ∈ I, B ∈ I a |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>
Říkáme, že matroid M (S, I) je vážený, pokud existuje asociovaná váhová funkce w, která přiřazuje striktně kladnou váhu w (x) každému prvku x ∈ S. Váhová funkce w se součtem rozšiřuje na podmnožinu S :
w (A) = ∑<sub>x∈A</sub> w(x)
pro jakékoli A ∈ S.