De problemen van de handelsreiziger houden zich bezig met een verkoper en een reeks steden. De verkoper moet alle steden bezoeken, beginnend bij een bepaalde stad (bijvoorbeeld de geboorteplaats) en terugkeren naar dezelfde stad. De uitdaging van het probleem is dat de handelsreiziger de totale lengte van de reis moet minimaliseren.
Stel dat de steden x zijn1X2..... XNwaar kosten cijgeeft de kosten aan van reizen vanuit stad xinaar xJ. Het handelsreizigersprobleem is het vinden van een route die begint en eindigt bij x1dat zal in alle steden plaatsvinden met de minimale kosten.
Voorbeeld: Een krantenagent brengt dagelijks de krant naar het toegewezen gebied, op een zodanige manier dat hij alle huizen in het betreffende gebied met minimale reiskosten moet bestrijken. Bereken de minimale reiskosten.
Het gebied dat aan de agent is toegewezen waar hij de krant moet afgeven, wordt weergegeven in figuur:
Oplossing: De kosten-aangrenzende matrix van grafiek G is als volgt:
kostenij=
De tour start vanuit gebied H1en selecteer vervolgens het gebied met minimale kosten dat bereikbaar is vanaf H1.
Markeer gebied H6omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H1en selecteer vervolgens het gebied met minimale kosten dat bereikbaar is vanaf H6.
Markeer gebied H7omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H6en selecteer vervolgens het gebied met minimale kosten dat bereikbaar is vanaf H7.
Markeer gebied H8omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H8.
Markeer gebied H5omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H5.
Markeer gebied H2omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H2.
Markeer gebied H3omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H3.
Markeer gebied H4en selecteer vervolgens het gebied met minimale kosten dat bereikbaar is vanaf H4het is H1Dus als we de hebzuchtige strategie gebruiken, krijgen we het volgende.
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>.
Dus de minimale reiskosten = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroïden:
Een matroid is een geordend paar M(S, I) dat aan de volgende voorwaarden voldoet:
- S is een eindige verzameling.
- I is een niet-lege familie van deelverzamelingen van S, de onafhankelijke deelverzamelingen van S genoemd, zodat als B ∈ I en A ∈ I. We zeggen dat I erfelijk is als het aan deze eigenschap voldoet. Merk op dat de lege verzameling ∅ noodzakelijkerwijs lid is van I.
- Als A ∈ I, B ∈ I en |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>
We zeggen dat een matroïde M (S, I) wordt gewogen als er een bijbehorende gewichtsfunctie w is die een strikt positief gewicht w (x) toekent aan elk element x ∈ S. De gewichtsfunctie w strekt zich uit tot een subset van S door optelling :
w (A) = ∑<sub>x∈A</sub> w(x)
voor elke A ∈ S.