Utazó értékesítő személy probléma
Az utazó eladók problémáit egy eladó és egy sor város jellemzi. Az eladónak minden várost meg kell látogatnia egy bizonyos várostól (pl. a szülővárostól) kezdve, és ugyanabba a városba kell visszatérnie. A probléma kihívása az, hogy az utazó eladónak minimálisra kell csökkentenie az utazás teljes hosszát.
Tegyük fel, hogy a városok x 1 x 2 ..... x n hol költség c ij az x városból való utazás költségét jelöli én x-hez j . Az utazó értékesítő problémája az, hogy meg kell találni egy x-nél kezdődő és végződő útvonalat 1 amely az összes várost a minimális költséggel fogadja.
Példa: Az újságügynök naponta leadja az újságot a kijelölt területre oly módon, hogy az adott területen lévő összes házat minimális utazási költséggel le kell fednie. Számítsa ki a minimális utazási költséget!
ábrán látható az ügynökhöz rendelt terület, ahol le kell dobnia az újságot:
Megoldás: A G gráf költség-szomszédsági mátrixa a következő:
költség ij =
A túra a H területről indul 1 majd válassza ki a H-ból elérhető minimális költségterületet 1 .
Jelölje meg a H területet 6 mert ez a H-ból elérhető minimális költségterület 1 majd válassza ki a H-ból elérhető minimális költségterületet 6 .
Jelölje meg a H területet 7 mert ez a H-ból elérhető minimális költségterület 6 majd válassza ki a H-ból elérhető minimális költségterületet 7 .
Jelölje meg a H területet 8 mert ez a H-ból elérhető minimális költségterület 8 .
Jelölje meg a H területet 5 mert ez a H-ból elérhető minimális költségterület 5 .
Jelölje meg a H területet 2 mert ez a H-ból elérhető minimális költségterület 2 .
Jelölje meg a H területet 3 mert ez a H-ból elérhető minimális költségterület 3 .
Jelölje meg a H területet 4 majd válassza ki a H-ból elérhető minimális költségterületet 4 ez H 1 .Tehát a mohó stratégiát használva a következőket kapjuk.
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>.
Így a minimális utazási költség = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroidok:
A matroid egy rendezett M(S,I) pár, amely megfelel a következő feltételeknek:
- S véges halmaz.
- I az S részhalmazainak egy nemüres családja, amelyeket S független részhalmazainak neveznek úgy, hogy ha B ∈ I és A ∈ I. Azt mondjuk, hogy én örökletes, ha kielégíti ezt a tulajdonságot. Vegyük észre, hogy az üres ∅ halmaz szükségszerűen az I tagja.
- Ha A ∈ I, B ∈ I és |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Azt mondjuk, hogy egy M (S, I) matroid súlyozott, ha van egy w súlyfüggvény, amely szigorúan pozitív w (x) súlyt rendel minden x ∈ S elemhez. A w súlyfüggvény összegzéssel S egy részhalmazára terjed ki. :
w (A) = ∑<sub>x∈A</sub> w(x)
bármely A ∈ S esetén.
