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


Yanıt Açıklaması:

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