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ım1X2..... XNmaliyet c neredebenx şehrinden seyahatin maliyetini gösterirBenx'eJ. Gezgin satıcı problemi x noktasında başlayıp biten bir rota bulmaktır.1minimum 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:
maliyetben=
Tur H alanından başlıyor1ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin1.
H alanını işaretle6çünkü H'den ulaşılabilecek minimum maliyet alanıdır1ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin6.
H alanını işaretle7çünkü H'den ulaşılabilecek minimum maliyet alanıdır6ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin7.
H alanını işaretle8çünkü H'den ulaşılabilecek minimum maliyet alanıdır8.
H alanını işaretle5çünkü H'den ulaşılabilecek minimum maliyet alanıdır5.
H alanını işaretle2çünkü H'den ulaşılabilecek minimum maliyet alanıdır2.
H alanını işaretle3çünkü H'den ulaşılabilecek minimum maliyet alanıdır3.
H alanını işaretle4ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin4bu H1.Yani açgözlü stratejiyi kullanarak aşağıdakileri elde ederiz.
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>.
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:
- S sonlu bir kümedir.
- 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.
- 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) = ∑<sub>x∈A</sub> w(x)
herhangi bir A ∈ S için.