Gezgin satıcı problemleri, bir satıcı ve bir dizi şehirden kaynaklanmaktadır. Satıcının belirli bir şehirden (mesela memleketinden) başlayarak her şehri gezmesi ve aynı şehre dönmesi gerekmektedir. Sorunun zorluğu, seyahat eden satıcının seyahatin toplam uzunluğunu en aza indirmesi gerekmesidir.

Şehirlerin x olduğunu varsayalım₁X₂..... X_Nmaliyet c nerede_benx şehrinden seyahatin maliyetini gösterir_Benx'e_J. Gezgin satıcı problemi x noktasında başlayıp biten bir rota bulmaktır.₁minimum maliyetle tüm şehirleri kapsayacak.

Örnek: Bir gazete temsilcisi, gazeteyi her gün kendisine tahsis edilen alana, o bölgedeki tüm evleri minimum yolculuk masrafı ile kapsayacak şekilde bırakıyor. Minimum seyahat maliyetini hesaplayın.

Java'da diziyi yazdır

Temsilcinin gazeteyi bırakması gereken alan, şekilde gösterilmiştir:

Çözüm: G grafiğinin maliyet-yakınlık matrisi aşağıdaki gibidir:

maliyet_ben=

Tur H alanından başlıyor₁ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin₁.

H alanını işaretle₆çünkü H'den ulaşılabilecek minimum maliyet alanıdır₁ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin₆.

H alanını işaretle₇çünkü H'den ulaşılabilecek minimum maliyet alanıdır₆ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin₇.

H alanını işaretle₈çünkü H'den ulaşılabilecek minimum maliyet alanıdır₈.

H alanını işaretle₅çünkü H'den ulaşılabilecek minimum maliyet alanıdır₅.

H alanını işaretle₂çünkü H'den ulaşılabilecek minimum maliyet alanıdır₂.

H alanını işaretle₃çünkü H'den ulaşılabilecek minimum maliyet alanıdır₃.

H alanını işaretle₄ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin₄bu H₁.Yani açgözlü stratejiyi kullanarak aşağıdakileri elde ederiz.

 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>. 

Böylece minimum seyahat maliyeti = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25

Matroidler:

Bir matroid, aşağıdaki koşulları karşılayan sıralı bir M(S, I) çiftidir:

1. S sonlu bir kümedir.
2. I, S'nin boş olmayan alt kümeleri ailesidir ve eğer B ∈ I ve A ∈ I ise S'nin bağımsız alt kümeleri olarak adlandırılır. Bu özelliği karşılıyorsa I'nin kalıtsal olduğunu söyleriz. Boş küme ∅'un zorunlu olarak I'in bir üyesi olduğuna dikkat edin.
3. Eğer A ∈ I, B ∈ I ve |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>

Her bir x ∈ S elemanına kesinlikle pozitif bir w(x) ağırlığı atayan ilişkili bir ağırlık fonksiyonu w varsa, bir matroid M (S, I)'nin ağırlıklı olduğunu söyleriz. Ağırlık fonksiyonu w, toplama yoluyla S'nin bir alt kümesine kadar uzanır. :

 w (A) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

herhangi bir A ∈ S için.