Ceļojoša pārdevēja problēma
Ceļojošā pārdevēja problēmas ir saistītas ar pārdevēju un pilsētu kopumu. Pārdevējam ir jāapmeklē katra no pilsētām, sākot no noteiktas (piemēram, dzimtās pilsētas) un jāatgriežas tajā pašā pilsētā. Problēmas izaicinājums ir tāds, ka ceļojošajam pārdevējam ir jāsamazina kopējais ceļojuma ilgums.
Pieņemsim, ka pilsētas ir x 1 x 2 ..... x n kur izmaksas c ij apzīmē ceļojuma izmaksas no pilsētas x i uz x j . Ceļojošā pārdevēja problēma ir atrast maršrutu, kas sākas un beidzas ar x 1 kas uzņems visas pilsētas ar minimālām izmaksām.
Piemērs: Avīzes aģents katru dienu nomet avīzi uz norādīto teritoriju tā, ka viņam ar minimālām ceļa izmaksām jāapsedz visas mājas attiecīgajā teritorijā. Aprēķiniet minimālās ceļojuma izmaksas.
Aģentam piešķirtā zona, kurā viņam jānomet avīze, ir parādīta attēlā:
Risinājums: Grafika G izmaksu-blakusuma matrica ir šāda:
izmaksas ij =
Ekskursija sākas no H apgabala 1 un pēc tam atlasiet minimālo izmaksu apgabalu, kas sasniedzams no H 1 .
Atzīmējiet apgabalu H 6 jo tā ir minimālo izmaksu zona, kas sasniedzama no H 1 un pēc tam atlasiet minimālo izmaksu apgabalu, kas sasniedzams no H 6 .
Atzīmējiet apgabalu H 7 jo tā ir minimālo izmaksu zona, kas sasniedzama no H 6 un pēc tam atlasiet minimālo izmaksu apgabalu, kas sasniedzams no H 7 .
Atzīmējiet apgabalu H 8 jo tā ir minimālo izmaksu zona, kas sasniedzama no H 8 .
Atzīmējiet apgabalu H 5 jo tā ir minimālo izmaksu zona, kas sasniedzama no H 5 .
Atzīmējiet apgabalu H 2 jo tā ir minimālo izmaksu zona, kas sasniedzama no H 2 .
Atzīmējiet apgabalu H 3 jo tā ir minimālo izmaksu zona, kas sasniedzama no H 3 .
Atzīmējiet apgabalu H 4 un pēc tam atlasiet minimālo izmaksu apgabalu, kas sasniedzams no H 4 tas ir H 1 .Tātad, izmantojot mantkārīgo stratēģiju, mēs iegūstam sekojošo.
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>.
Tādējādi minimālās ceļojuma izmaksas = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matoīdi:
Matroids ir sakārtots pāris M(S, I), kas atbilst šādiem nosacījumiem:
- S ir ierobežota kopa.
- I ir tukša S apakškopu saime, ko sauc par S neatkarīgajām apakškopām, ja B ∈ I un A ∈ I. Mēs sakām, ka es ir iedzimts, ja tas atbilst šai īpašībai. Ņemiet vērā, ka tukšā kopa ∅ noteikti ir I dalībnieks.
- Ja A ∈ I, B ∈ I un |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Mēs sakām, ka matroids M (S, I) ir svērts, ja ir saistīta svara funkcija w, kas katram elementam x ∈ S piešķir stingri pozitīvu svaru w (x). Svara funkcija w attiecas uz S apakškopu, summējot. :
w (A) = ∑<sub>x∈A</sub> w(x)
jebkuram A ∈ S.
