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₁x₂..... x_nkur izmaksas c_ijapzīmē ceļojuma izmaksas no pilsētas x_iuz x_j. Ceļojošā pārdevēja problēma ir atrast maršrutu, kas sākas un beidzas ar x₁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ā:

tīmekļa draiveris

Risinājums: Grafika G izmaksu-blakusuma matrica ir šāda:

izmaksas_ij=

Ekskursija sākas no H apgabala₁un pēc tam atlasiet minimālo izmaksu apgabalu, kas sasniedzams no H₁.

imessage spēles Android ierīcēs

Atzīmējiet apgabalu H₆jo tā ir minimālo izmaksu zona, kas sasniedzama no H₁un pēc tam atlasiet minimālo izmaksu apgabalu, kas sasniedzams no H₆.

Atzīmējiet apgabalu H₇jo tā ir minimālo izmaksu zona, kas sasniedzama no H₆un pēc tam atlasiet minimālo izmaksu apgabalu, kas sasniedzams no H₇.

netīrs baļķis

Atzīmējiet apgabalu H₈jo tā ir minimālo izmaksu zona, kas sasniedzama no H₈.

Atzīmējiet apgabalu H₅jo tā ir minimālo izmaksu zona, kas sasniedzama no H₅.

Atzīmējiet apgabalu H₂jo tā ir minimālo izmaksu zona, kas sasniedzama no H₂.

Atzīmējiet apgabalu H₃jo tā ir minimālo izmaksu zona, kas sasniedzama no H₃.

Atzīmējiet apgabalu H₄un pēc tam atlasiet minimālo izmaksu apgabalu, kas sasniedzams no H₄tas ir H₁.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> &#x2192; H<sub>6</sub> &#x2192; H<sub>7</sub> &#x2192; H<sub>8</sub> &#x2192; H<sub>5</sub> &#x2192; H<sub>2</sub> &#x2192; H<sub>3</sub> &#x2192; H<sub>4</sub> &#x2192; <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:

jpa pavasarī

1. S ir ierobežota kopa.
2. 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.
3. 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) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

jebkuram A ∈ S.