Lojistik Planlama Ve Modelleme Deneme Sınavı Sorusu #969117
Yönsüz Çinli Postacı Problem İçin Enküçük Kusursuz Eşleşme Algoritmasının ilk adımı aşığıdakilerden hangisidir?
Serimin genişletilmiş hali için Euler turunu belirlemek |
Toplamda en az maliyet artışını verecek ayrıtları serime eklemek |
Serimdeki tek ve çift dereceli düğümleri belirlemek |
Tek dereceli düğümleri listeleyerek bunların arasından hangilerinde git gel yapılabileceğini incelemek. |
Fonksiyonu değerini belirlemek |
Bu algoritma temel olarak serimde bir Euler turu oluşturmak için hangi düğümler arasında git-gel yapılması gerektiğini belirlemeye çalışır. Bunu için de tek dereceli düğümler arasındaki olası geçişleri inceler ve toplamda en az mesafe artırımına neden olacak seçeneği benimser. Algoritmanın adımları şöyle verilmektedir:
1. Adım: Serimdeki tek ve çift dereceli düğümleri belirle. Bütün düğüm dereceleri çift ise Euler turu vardır, devam etmeye gerek olmaz, dur. Tek dereceli düğümler varsa 2. adıma geç.
2. Adım: Tek dereceli düğümleri listeleyerek bunların arasından hangilerinde git gel yapılabileceğini incele. Toplamda en az maliyet artışını verecek ayrıtları serime ekle.
3. Adım: Serimin genişletilmiş hâli için Euler turunu belirle. Toplam maliyet, bütün ayrıtların maliyetleri ve 2. adımda serime yeni eklenen ayrıtların maliyetleri toplamıdır.
Yorumlar
- 0 Yorum