Yönsüz Çinli Postacı Problem İçin Enküçük Kusursuz Eşleşme Algoritması
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.