Seyahat Eden Satış Elemanı Sorunu
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 1 X 2 ..... X N maliyet c nerede ben x şehrinden seyahatin maliyetini gösterir Ben x'e J . Gezgin satıcı problemi x noktasında başlayıp biten bir rota bulmaktır. 1 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.
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 1 ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin 1 .
H alanını işaretle 6 çünkü H'den ulaşılabilecek minimum maliyet alanıdır 1 ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin 6 .
H alanını işaretle 7 çünkü H'den ulaşılabilecek minimum maliyet alanıdır 6 ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin 7 .
H alanını işaretle 8 çünkü H'den ulaşılabilecek minimum maliyet alanıdır 8 .
H alanını işaretle 5 çünkü H'den ulaşılabilecek minimum maliyet alanıdır 5 .
H alanını işaretle 2 çünkü H'den ulaşılabilecek minimum maliyet alanıdır 2 .
H alanını işaretle 3 çünkü H'den ulaşılabilecek minimum maliyet alanıdır 3 .
H alanını işaretle 4 ve ardından H'den ulaşılabilecek minimum maliyet alanını seçin 4 bu H 1 .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.
