Problemi trgovskega potnika se nanašajo na trgovca in nabor mest. Prodajalec mora obiskati vsako od mest, začenši z določenim (npr. domače) in se vrniti v isto mesto. Izziv problema je v tem, da mora trgovski potnik zmanjšati skupno dolžino potovanja.
Recimo, da sta mesta x1x2..... xnkjer stane cijoznačuje stroške potovanja iz mesta xjazdo xj. Težava potujočega prodajalca je najti pot, ki se začne in konča pri x1ki bo sprejela vsa mesta z najnižjimi stroški.
primer: Časopisni agent vsak dan odloži časopis na dodeljeno območje tako, da mora pokriti vse hiše na tem območju z minimalnimi potnimi stroški. Izračunajte minimalne stroške potovanja.
Območje, dodeljeno agentu, kamor mora odložiti časopis, je prikazano na sl.
Rešitev: Matrika stroškovne sosednosti grafa G je naslednja:
stroškiij=
izjava o primeru verilog
Tura se začne iz območja H1in nato izberite območje najnižjih stroškov, ki je dosegljivo iz H1.
Označite območje H6ker je to območje najnižjih stroškov, ki je dosegljivo iz H1in nato izberite območje najnižjih stroškov, ki je dosegljivo iz H6.
Označite območje H7ker je to območje najnižjih stroškov, ki je dosegljivo iz H6in nato izberite območje najnižjih stroškov, ki je dosegljivo iz H7.
Označite območje H8ker je to območje najnižjih stroškov, ki je dosegljivo iz H8.
Označite območje H5ker je to območje najnižjih stroškov, ki je dosegljivo iz H5.
Označite območje H2ker je to območje najnižjih stroškov, ki je dosegljivo iz H2.
Označite območje H3ker je to območje najnižjih stroškov, ki je dosegljivo iz H3.
Označite območje H4in nato izberite območje najnižjih stroškov, ki je dosegljivo iz H4je H1.Torej, z uporabo pohlepne strategije dobimo naslednje.
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>.
Tako je najmanjši potni strošek = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroidi:
Matroid je urejen par M(S, I), ki izpolnjuje naslednje pogoje:
nadnapis v ilustratorju
- S je končna množica.
- I je neprazna družina podmnožic S, imenovanih neodvisne podmnožice S, tako da če je B ∈ I in A ∈ I. Pravimo, da je I dedna, če izpolnjuje to lastnost. Upoštevajte, da je prazna množica ∅ nujno član I.
- Če je A ∈ I, B ∈ I in |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>
Pravimo, da je matroid M (S, I) utežen, če obstaja povezana utežna funkcija w, ki vsakemu elementu x ∈ S dodeli strogo pozitivno utež w (x). Funkcija uteži w se razširi na podmnožico S s seštevanjem :
w (A) = ∑<sub>x∈A</sub> w(x)
za vsak A ∈ S.