Avrupa Haritası - Minimum Renkle Boyama

Avrupa ülkelerinin komşuluk grafiğini en az sayıda renkle boyamak için geri izlemeli arama (backtracking) ve kısıt yayılımı tekniklerini izleyin. MRV / LCV sezgileri ve domain budama (node pruning) istatistikleriyle kararların nasıl değiştiğini gözlemleyin.

Heuristik

Gecikme (ms)

Arama Stratejisi

Algoritma 3 renkle başlamayı dener ve gerekirse paleti genişleterek minimum renk sayısını bulur.

Harita

İstatistikler

Deneme Renk Sayısı-

Atama-

Geri İzleme-

Domain Budama-

Çözüm-

Hazır

İzleme İpuçları

MRV (Minimum Remaining Values), en dar domain'e sahip ülkeyi seçerek arama ağacını küçültür.
LCV (Least Constraining Value), komşuların domain'ini en az daraltan rengi tercih eder.
Domain budama değeri, bir renk denemesinde kaç potansiyel seçeneğin elendiğini gösterir.
Minimum renk sayısının 4 olduğunu gözlemleyin; algoritma önce 3 renge izin verip başarısız olursa palete yeni renk ekler.