Problem potujočega komercialista
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 x 1 x 2 ..... x n kjer stane c ij označuje stroške potovanja iz mesta x jaz do x j . Težava potujočega prodajalca je najti pot, ki se začne in konča pri x 1 ki 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ški ij =
Tura se začne iz območja H 1 in nato izberite območje najnižjih stroškov, ki je dosegljivo iz H 1 .
Označite območje H 6 ker je to območje najnižjih stroškov, ki je dosegljivo iz H 1 in nato izberite območje najnižjih stroškov, ki je dosegljivo iz H 6 .
Označite območje H 7 ker je to območje najnižjih stroškov, ki je dosegljivo iz H 6 in nato izberite območje najnižjih stroškov, ki je dosegljivo iz H 7 .
Označite območje H 8 ker je to območje najnižjih stroškov, ki je dosegljivo iz H 8 .
Označite območje H 5 ker je to območje najnižjih stroškov, ki je dosegljivo iz H 5 .
Označite območje H 2 ker je to območje najnižjih stroškov, ki je dosegljivo iz H 2 .
Označite območje H 3 ker je to območje najnižjih stroškov, ki je dosegljivo iz H 3 .
Označite območje H 4 in nato izberite območje najnižjih stroškov, ki je dosegljivo iz H 4 je H 1 .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:
- 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.
