Probleem met reizende verkopers
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 zijn 1 X 2 ..... X N waar kosten c ij geeft de kosten aan van reizen vanuit stad x i naar x J . Het handelsreizigersprobleem is het vinden van een route die begint en eindigt bij x 1 dat 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:
kosten ij =
De tour start vanuit gebied H 1 en selecteer vervolgens het gebied met minimale kosten dat bereikbaar is vanaf H 1 .
Markeer gebied H 6 omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H 1 en selecteer vervolgens het gebied met minimale kosten dat bereikbaar is vanaf H 6 .
Markeer gebied H 7 omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H 6 en selecteer vervolgens het gebied met minimale kosten dat bereikbaar is vanaf H 7 .
Markeer gebied H 8 omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H 8 .
Markeer gebied H 5 omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H 5 .
Markeer gebied H 2 omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H 2 .
Markeer gebied H 3 omdat dit het gebied met minimale kosten is dat bereikbaar is vanaf H 3 .
Markeer gebied H 4 en selecteer vervolgens het gebied met minimale kosten dat bereikbaar is vanaf H 4 het is H 1 Dus 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.
