Bölüm 9: Geri İzleme Algoritmaları

9.1Zor problemler: P, NP ve NP-zor

Dersin bu noktasına kadar görülen algoritmaların çoğu hızlıdır. Bir diziyi birleştirmeli sıralama O(n log n) sürede sıralar. Dijkstra algoritması en kısa yolları, Kruskal algoritması en küçük kapsayan ağacı polinom sürede bulur. Ama her problem bu kadar uysal değildir. Bir çizgenin her düğümünden tam bir kez geçen bir yol var mı? Bir haritanın ülkeleri, komşu ülkeler farklı renkte olacak biçimde üç renkle boyanabilir mi? Bu soruların ikisi için de bugüne kadar polinom süreli bir algoritma bulunamamıştır. Bulunamayacağı da kanıtlanamamıştır. Geri izleme bu türden problemler için geliştirilmiş bir arama yöntemidir. Yöntemin neden gerektiğini görmek için önce problemlerin zorluk sınıflarına kısaca bakmak yararlıdır.

9.1.1Karar problemleri ve polinom zaman

Zorluk sınıfları çoğunlukla karar problemleri (decision problems) üzerinden tanımlanır. Karar probleminin cevabı yalnız “evet” ya da “hayır”dır. “Bu çizgede Hamilton yolu var mı?” bir karar problemidir. “Bu çizgedeki en kısa Hamilton turunun uzunluğu nedir?” ise bir en iyileme problemidir (optimization problem). En iyileme problemi çoğu zaman bir karar problemine çevrilebilir: “Uzunluğu en çok 100 olan bir tur var mı?” Karar sürümü hızlı çözülebilseydi, eşik değeri ikili aramayla daraltılarak en iyi değer de bulunabilirdi. Bu yüzden karar sürümünün zorluğu, en iyileme sürümünün zorluğu hakkında da bilgi verir.

Bir algoritmanın süresi bir k sabiti için O(n^k) ise algoritma polinom zamanlıdır (polynomial time). n burada girdinin boyudur. O(n), O(n log n) ve O(n³) polinom sürelerdir. O(2ⁿ) ve O(n!) ise değildir. Fark küçük girdilerde göze çarpmaz, ama girdi büyüdükçe uçurum açılır. n = 60 için n³ = 216 000 işlem bir bilgisayar için bir an sürer. 2⁶⁰ ≈ 1,15 · 10¹⁸ işlem ise saniyede bir milyar işlem yapan bir makinede otuz yılı aşar. Polinom süre bu yüzden “pratikte çözülebilir” anlamında kullanılır.

9.1.2P ve NP

P sınıfına iki örnek iki ağırlıklı çizge sorusudur: “s'den t'ye uzunluğu en çok 50 olan bir yol var mı?” ve “ağırlığı en çok 30 olan bir kapsayan ağaç var mı?” Birinci soruyu Dijkstra, ikincisini Kruskal algoritması polinom sürede cevaplar.

NP'nin tanımı çözmekle değil, denetlemekle ilgilidir. Hamilton yolu problemi buna iyi bir örnektir. Bir çizgede Hamilton yolu bulmak zordur. Ama biri bir düğüm sırası önerirse, sıranın her düğümü bir kez içerip içermediği ve ardışık düğümlerin komşu olup olmadığı O(n) adımda denetlenir. Sudoku da aynı türdendir. Doldurulmuş bir tabloyu denetlemek kolaydır: her satır, sütun ve kutu bir kez taranır. Boş bir tabloyu doldurmak ise arama gerektirir.

Polinom sürede çözülebilen bir problemin çözümü polinom sürede doğrulanabilir de. Doğrulayıcı, önerilen tanığı yok sayıp problemi baştan çözebilir. Bu yüzden P, NP'nin içindedir. Asıl soru ters yöndedir: doğrulaması kolay her problemin çözümü de kolay mıdır? Bu soru P = NP sorusu olarak anılır ve bilgisayar biliminin en önemli açık problemidir. Araştırmacıların çoğu P ≠ NP olduğuna inanır, ama bu henüz kanıtlanmamıştır.

9.1.3İndirgeme, NP-zor ve NP-tam

İki problemin zorluğunu karşılaştırmanın aracı indirgemedir (reduction). A probleminin her örneği polinom sürede B probleminin bir örneğine dönüştürülebiliyorsa ve iki örneğin cevabı aynıysa, A, B'ye indirgenir. Bu durumda B'yi çözen hızlı bir algoritma A'yı da hızlıca çözer: önce dönüştürülür, sonra B'nin algoritması çalıştırılır. Yani B en az A kadar zordur.

NP-tam problemler NP'nin “en zor” üyeleridir. İçlerinden biri polinom sürede çözülebilseydi, indirgemeler sayesinde NP'deki her problem polinom sürede çözülürdü ve P = NP olurdu. İlk NP-tam problem mantıksal doyurulabilirliktir (satisfiability, SAT): mantıksal değişkenlerden kurulmuş bir formülü doğru yapan bir değer ataması var mı? SAT'ın kısıtlı bir biçimi olan 3-SAT da NP-tamdır. Hamilton yolu ve Hamilton döngüsü, çizge 3-boyama ve alt küme toplamının karar sürümü de NP-tam problemler arasındadır.

Gezgin satıcı problemi (traveling salesman problem, TSP) ve sırt çantası probleminin en iyileme sürümleri ise NP-zordur. Bu sürümler karar problemi değildir; bir sayı ya da bir tur döndürürler. Önerilen bir turun en kısa tur olduğunu denetlemek de kolay değildir. Bu yüzden NP içinde sayılmazlar, ama karar sürümleri NP-tam olduğu için en az o kadar zordurlar.

Şekil 9.1'deki çizim bir varsayıma dayanır. P = NP olsaydı P, NP ve NP-tam bölgeleri (önemsiz birkaç istisnayla) çakışırdı. Çizimin gösterdiği ayrım, bugünkü bilgimizin değil, yaygın kanaatin resmidir.

9.1.4Kesin çözüm için ne yapılabilir?

P ≠ NP ise NP-tam ve NP-zor problemler için polinom zamanlı kesin algoritma yoktur. Bu durumda üç yol kalır.

• Üstel ama akıllı arama. Kesin çözüm şartsa olası çözümler aranır. Arama uzayı üsteldir, ama çoğu zaman uzayın küçük bir kısmını gezmek yeter. Amaç, işe yaramayacağı anlaşılan bölümleri erkenden atmaktır. Bu işleme budama (pruning) denir. Geri izleme ve dal sınır yöntemleri bu yolu izler.
• Yaklaşık çözüm. Polinom süre şartsa en iyi çözümden vazgeçilir. Yaklaşım algoritmaları en iyiye kanıtlı bir oranla yakın bir çözüm üretir.
• Sezgisel arama. Hiçbir garanti vermeyen ama pratikte çoğu zaman iyi çalışan yöntemler kullanılır. En az çakışma sezgiseli bu türdendir.

Bu notun konusu birinci yoldur. Geri izleme en kötü durumda üstel süre harcar. Ama iyi bir budamayla, pratikte karşılaşılan örneklerin çoğunu makul sürede çözer. N vezir problemi bu farkı sayılarla gösterir: 8 vezir için 16,7 milyon tam yerleşimi tek tek denemek yerine yalnız 2056 kısmi yerleşim üretmek yeter.

9.2Geri izlemenin temel fikri

9.2.1Geri dönüp denemek

Bir problemi çözmek için bazen farklı yollar denemek ve yanlış yollardan geri dönmek gerekir. Kilitli bir çantanın üç haneli şifresini unutan biri bütün kombinasyonları sırayla dener. Bir bulmaca çözen kişi bir hücreye bir rakam yazar, birkaç adım sonra çelişkiye düşünce silip başka rakam dener. Geri izleme (backtracking) bu sezgisel davranışı sistemli bir algoritmaya dönüştürür.

Tanımdaki dört terim notun her yerinde geçer. Kısmi çözüm o ana kadar yapılan seçimlerdir: N vezir probleminde ilk birkaç satıra konmuş vezirler, Sudoku'da doldurulmuş hücreler. Aday bir sonraki adımda yapılabilecek seçimdir: sıradaki satırın sütunlarından biri, boş hücreye yazılabilecek 1–9 rakamlarından biri. Kısıt, geçerli bir çözümün uyması gereken kuraldır: iki vezir birbirini tehdit etmez, bir satırda aynı rakam iki kez geçmez. Geri alma ise son eklenen adayı çıkarıp durumu bir önceki hâline getirmektir.

Geri izlemeyi kaba kuvvetten (brute force) ayıran budur. Kaba kuvvet bütün tam aday çözümleri üretir ve her birini sonradan test eder. Geri izleme ise kısmi çözüm geçersiz olur olmaz durur. Geçersiz bir kısmi çözümün devamı hiç üretilmez. İlk iki vezir birbirini tehdit ediyorsa, kalan altı vezirin hiçbir yerleşimi bu hatayı düzeltemez. Kaba kuvvet bu altı vezirin 8⁶ = 262 144 yerleşimini tek tek dener; geri izleme hiçbirini denemez.

9.2.2Labirentteki yolcu

Geri izleme algoritması bir labirentte yol arayan bir yolcuya benzetilebilir. Yolcu her kavşakta bir karar verir ve bir koridora girer. Koridor çıkışa götürüyorsa iş biter. Çıkmaza girerse son kavşağa geri döner ve henüz denemediği bir koridoru dener. O kavşaktaki bütün koridorlar çıkmazsa bir önceki kavşağa döner. Bu deneme-yanılma süreci çıkış bulunana ya da bütün seçenekler tükenene kadar sürer.

Benzetme algoritmanın en önemli gereksinimini de gösterir. Geri dönebilmek için nereden gelindiğini hatırlamak gerekir. Yolcu her kavşakta yere bir işaret bırakır ya da girdiği kavşakları bir listeye yazar. Geri izleme algoritmalarında bu listeyi özyineleme kendiliğinden sağlar. Her özyinelemeli çağrı bir kavşaktır. Çağrı yığınında üst üste duran çerçeveler, girilmiş ama henüz bitirilmemiş kavşakların listesidir. Bir çağrı return ile bittiğinde denetim bir önceki çerçeveye döner. Bu da yolcunun bir önceki kavşağa geri dönmesidir.

Labirent örneği yapay zekâ ve bulmaca problemlerinin ortak yapısını taşır. Sudoku'da her boş hücre bir kavşaktır, yazılabilecek rakamlar koridorlardır. Satrançta her hamle bir kavşaktır. Hepsinde aynı soru sorulur: bu kararla devam etmek mümkün mü, değilse hangi karara geri dönülmeli?

9.2.3Labirentte geri dönüş adım adım

Labirent 5 × 5'lik bir ızgaradır. Hücreler (satır, sütun) çiftiyle gösterilir; giriş (0, 0), çıkış (4, 4) hücresidir. Gri hücreler duvardır: (1, 1), (1, 2), (1, 3), (2, 3), (3, 0), (3, 1), (3, 3) ve (4, 3). Algoritma her hücrede dört yönü sabit bir sırayla dener: aşağı, sağ, yukarı, sol. Ziyaret edilen her hücre işaretlenir, böylece aynı hücreye ikinci kez girilmez. İşaret olmasaydı yolcu iki hücre arasında sonsuza kadar gidip gelebilirdi.

Arama şöyle ilerler. Girişten aşağı iki adım atılır: (1, 0), (2, 0). (3, 0) duvar olduğu için aşağı yön kapalıdır; sıradaki yön olan sağ denenir. Sağa iki adımla (2, 1) ve (2, 2)'ye varılır. (2, 2) bir kavşaktır: aşağısı açık, sağı (2, 3) ve yukarısı (1, 2) duvardır. Önce aşağı denenir: (3, 2), (4, 2). (4, 2)'nin aşağısı ızgaranın dışı, sağı (4, 3) duvardır; sola dönülür: (4, 1), (4, 0). (4, 0) hücresinde dört yön de kapalıdır: aşağısı ve solu sınır, yukarısı duvar, sağı ziyaret edilmiş. Bu bir çıkmazdır.

Şimdi geri dönüş başlar. (4, 0), (4, 1), (4, 2) ve (3, 2) yoldan çıkarılır, çünkü bu hücrelerin denenmemiş açık yönü yoktur. (2, 2) kavşağına geri gelinir. Bu kavşağın kalan yönleri de kapalıdır: sağı ve yukarısı duvar, solu ziyaret edilmiş. Geri dönüş sürer: (2, 2), (2, 1), (2, 0) ve (1, 0) da çıkmaz olarak bırakılır. Sonunda girişe dönülür. Girişte aşağı yön tükenmiştir; sıradaki yön olan sağ denenir.

Üst koridor boyunca sağa gidilir: (0, 1), (0, 2), (0, 3), (0, 4). Bu hücrelerin hiçbirinin aşağısı açık değildir, ta ki (0, 4)'e kadar. (0, 4)'ün aşağısı açıktır. (1, 4), (2, 4), (3, 4) üzerinden çıkışa, (4, 4)'e varılır.

9.2.4Durum uzayı ağacı

Geri izlemenin yaptığı aramayı bir ağaç üzerinde düşünmek yararlıdır. Kökte henüz hiçbir seçim yapılmamıştır. Kökün çocukları birinci seçimin seçenekleridir. Her çocuğun çocukları ikinci seçimin seçenekleridir ve bu böyle sürer. Bu ağaca durum uzayı ağacı (state-space tree) denir.

Şekil 9.8 tanımdaki terimleri bir arada gösterir. Kısmi çözüm kökten bir düğüme giden yoldur: x₁ = b, x₂ = c düğümü (b, c) kısmi çözümüdür. Adaylar düğümün çocuklarıdır. Kısıt bozulursa düğümün alt ağacı budanır: (a, a) kısmi çözümü geçersizdir ve altındaki hiçbir düğüm üretilmez. Hedef testi tam ve geçerli bir çözüme ulaşılıp ulaşılmadığını sorar; bu ağaçta (b, c, a) bir yapraktır ve çözümdür.

Ağacın iki özelliği önemlidir. Birincisi, ağaç önceden kurulmaz. Algoritma yalnız o an bulunduğu düğümü ve köke giden yolu bellekte tutar. Ağaç gezilirken üretilir ve gezilen dallar unutulur. İkincisi, gezinme sırası derinlik önceliklidir (depth-first search, DFS). Algoritma bir dalda dibe kadar iner. Dal biterse ya da budanırsa bir üst düğüme çıkar ve sıradaki çocuğa geçer. Geri izleme, durum uzayı ağacında yapılan bir derinlik öncelikli aramadır. Fark yalnız şudur: geçersiz düğümlerin alt ağaçları hiç üretilmez.

9.2.5Genel şablon: seç, keşfet, geri al

Geri izleme algoritmalarının hemen hepsi aynı iskeletle yazılır. İskelet bir özyinelemeli metottur. Metot bir kısmi çözüm alır, tam bir çözüm olup olmadığına bakar, değilse her adayı sırayla dener.

void geriDon(Durum kismi) {
  if (cozumMu(kismi)) {
    kaydet(kismi);
    return;
  }
  for (Aday a : adaylar(kismi)) {
    if (gecerliMi(kismi, a)) {
      ekle(kismi, a);    // seç
      geriDon(kismi);    // keşfet
      cikar(kismi, a);   // geri al
    }
  }
}

Kodun dört parçası vardır.

1. Hedef testi. cozumMu(kismi) kısmi çözümün tamamlanıp tamamlanmadığına bakar. Tamamlanmışsa çözüm kaydedilir ve metot döner. Tek bir çözüm yetiyorsa burada arama tamamen durdurulabilir.
2. Seç. adaylar(kismi) bir sonraki adımın seçeneklerini verir. Geçerli bir aday ekle(kismi, a) ile kısmi çözüme eklenir.
3. Keşfet. geriDon(kismi) özyinelemeyle bir seviye derine iner. Bu çağrı, eklenen adayın altındaki bütün alt ağacı gezer.
4. Geri al. Çağrı döndüğünde cikar(kismi, a) adayı kısmi çözümden çıkarır. Durum çağrıdan önceki hâline döner ve döngü sıradaki adayla sürer.

Budama gecerliMi içinde olur. Geçersiz bir aday için özyinelemeli çağrı hiç yapılmaz. Böylece o adayın altındaki bütün alt ağaç tek bir if ile atlanır. Budamanın gücü buradan gelir: bir denetim, belki binlerce düğümlük bir alt ağacı ortadan kaldırır.

Geri alma adımının neden şart olduğunu görmek için kısmi çözümün nasıl saklandığına bakmak gerekir. kismi bütün çağrıların paylaştığı tek bir nesnedir: bir tahta, bir dizi ya da bir liste. Her çağrı bu nesneyi değiştirir. Bir çağrı döndüğünde nesne, çağrının bıraktığı hâlde kalır. Sıradaki aday denenmeden önce bu değişiklik silinmezse yeni aday eskisinin kalıntılarıyla birlikte sınanır. Yalnız değerle geçirilen ilkel parametreler, örneğin bir int toplam ya da bir indis, kendiliğinden eski hâline döner. Her çağrının kendi kopyası vardır.

Tek bir çözüm yetiyorsa şablon küçük bir değişiklikle boolean döndürür. Hedef testinde true döndürülür. Özyinelemeli çağrı true döndürürse arayan da hemen true döndürür. Böylece ilk çözüm bulunduğunda bütün çağrılar sırayla sona erer. N vezir, Sudoku, çizge boyama ve Hamilton yolu kodları bu biçimdedir.

9.2.6Şablonun uygulaması: permütasyonlar

Şablonun en temiz uygulaması bir kümenin bütün permütasyonlarını üretmektir. 1, 2 ve 3 sayılarının her sıralaması bir permütasyondur. Kısmi çözüm, ilk k konuma yazılmış sayılardır. Aday, henüz kullanılmamış bir sayıdır. Kısıt tektir: bir sayı iki kez kullanılamaz.

void permutasyon(int[] p, boolean[] kullan, int k) {
  if (k == p.length) {               // çözüm
    System.out.println(Arrays.toString(p));
    return;
  }
  for (int a = 1; a <= p.length; a++) {
    if (!kullan[a]) {                // geçerli
      p[k] = a; kullan[a] = true;    // seç
      permutasyon(p, kullan, k + 1); // keşfet
      kullan[a] = false;             // geri al
    }
  }
}

p dizisi kısmi çözümü tutar; p[0..k−1] doludur. kullan dizisi hangi sayıların kullanıldığını gösterir. Dizinin boyu n + 1'dir, çünkü sayılar 1'den başlar ve kullan[0] boş kalır. k == p.length hedef testidir: bütün konumlar dolduysa permütasyon yazdırılır. Döngü 1'den n'ye kadar her sayıyı dener. !kullan[a] geçerlilik testidir. Sayı kullanılmamışsa p[k]'ya yazılır ve işaretlenir (seç). Özyinelemeli çağrı bir sonraki konumu doldurur (keşfet). Çağrı dönünce işaret kaldırılır (geri al).

Geri alma satırında yalnız kullan[a] = false vardır; p[k] sıfırlanmaz. Bunun nedeni, p[k]'nın bir sonraki adayda zaten üzerine yazılacak olmasıdır. Geçerlilik testi p'ye değil, kullan'a bakar. Bu yüzden p[k]'daki eski değer hiçbir kararı etkilemez. Kısıtı denetleyen yapı ise mutlaka geri alınmalıdır.

5. adımdaki p değeri dikkat çekicidir: [1, 3, 3]. p[2]'de bir önceki permütasyondan kalan 3 durur. Bu değer hiçbir şeyi bozmaz, çünkü k = 1'deyiz ve p[2] henüz kısmi çözümün parçası değildir. 6. adımda üzerine 2 yazılır. Program çıktısı şudur:

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Adaylar küçükten büyüğe denendiği için permütasyonlar sözlüksel sırada (lexicographic order) çıkar. Bu, bütün geri izleme algoritmalarında geçerli bir gözlemdir: adaylar hangi sırayla denenirse çözümler de o sırayla bulunur.

Genel olarak n öğenin permütasyon ağacında k. seviyede n · (n − 1) · … · (n − k + 1) = n!/(n − k)! düğüm vardır. Son iki seviyenin düğüm sayısı eşittir (n!) ve toplam n!'in küçük bir sabit katıdır (e · n!'e yakındır). Her yaprakta permütasyon yazdırmak O(n) sürer. Bu yüzden bütün permütasyonları üretmenin süresi O(n · n!)'dir. Burada budama işi azaltmaz, çünkü bütün yapraklar zaten çözümdür. Budamanın kazandırdığı şey, kısıtı bozan dalların hiç açılmamasıdır: aynı sayının tekrar seçilmesine izin veren budamasız ağaçta n = 4 için 4⁴ = 256 yaprak olurdu.

List<List<Integer>> sonuclar = new ArrayList<>();

void topla(List<Integer> yol, boolean[] kul, int n) {
  if (yol.size() == n) {
    sonuclar.add(new ArrayList<>(yol));   // kopyası saklanır
    return;
  }
  for (int v = 1; v <= n; v++) {
    if (!kul[v]) {
      kul[v] = true; yol.add(v);          // seç
      topla(yol, kul, n);                 // keşfet
      yol.remove(yol.size() - 1);         // geri al
      kul[v] = false;
    }
  }
}

Bu sürüm kısmi çözümü bir List içinde tutar. Seçme adımı listeye ekler, geri alma adımı son öğeyi siler. new ArrayList<>(yol) o anki içeriğin bağımsız bir kopyasıdır; sonraki değişiklikler kopyayı etkilemez. topla(new ArrayList<>(), new boolean[4], 3) çağrısının ardından sonuclar altı permütasyonu sözlüksel sırada içerir.

9.2.7Kaba kuvvet ve budama

Budamanın ne kadar iş kazandırdığı, 8 vezir problemiyle sayısal olarak gösterilebilir. Problem şudur: 8 × 8'lik satranç tahtasına birbirini tehdit etmeyen 8 vezir yerleştirilecek. Problemi çözmenin birkaç yolu vardır ve her biri farklı sayıda aday inceler.

Tablonun ilk üç satırı kaba kuvvetin giderek akıllanan sürümleridir. İlk satır en saf yaklaşımdır: 64 kareden 8'ini seçmenin C(64, 8) = 4 426 165 368 yolu vardır. İkinci satır bir gözlem kullanır: her satırda tam bir vezir bulunmalıdır, çünkü aynı satırdaki iki vezir birbirini tehdit eder. Her satırdaki vezirin 8 sütun seçeneği vardır ve 8⁸ = 16 777 216 yerleşim kalır. Üçüncü satır aynı mantığı sütunlara da uygular: sütunlar da farklı olmalıdır. Bu durumda yerleşim, sütunların bir permütasyonudur ve 8! = 40 320 aday kalır. Bu üç yaklaşımın ortak yanı, her adayın tam bir yerleşim olması ve ancak sonunda test edilmesidir.

Geri izleme ise tam yerleşimleri değil, kısmi yerleşimleri üretir. Vezirler satır satır konur. Bir vezir öncekilerden biriyle çakışıyorsa o kısmi yerleşimin devamı hiç denenmez. Sonuç çarpıcıdır: bütün 92 çözümü bulmak için yalnız 2056 güvenli yerleştirme yapılır. İlk çözüm 113 yerleştirmede bulunur. 8⁸ tam yerleşimle karşılaştırıldığında bütün çözümleri bulmak bile yaklaşık 16 777 216 / 2056 ≈ 8160 kat daha az iş gerektirir.

Budama en kötü durumu değiştirmez; geri izleme yine üstel bir algoritmadır. Ama pratikte durum uzayı ağacının çok küçük bir kısmı gezilir. Budamanın gücü kısıtın ne kadar erken denetlendiğine bağlıdır. Kısıt kısmi çözüm üzerinde, her yeni adayda denetlenmelidir. Sona bırakılan bir denetim kaba kuvvetten farksızdır.

9.2.8Güçlü ve zayıf yanlar

Geri izlemenin güçlü yanları genelliğinden gelir.

• Geniş uygulama alanı. Çözümü bir dizi seçim olarak ifade edilebilen her probleme uygulanır. Aynı şablon permütasyon üretiminden Sudoku'ya kadar değişmeden kullanılır.
• Çoğu zaman verimli. Kısıtları erkenden denetlenebilen problemlerde ağacın büyük bölümü budanır.
• Kısa ve anlaşılır kod. Algoritma birkaç satırlık bir özyinelemeli metottur.
• Tam arama. Geri izleme bütün çözümleri bulur ya da hiç çözüm olmadığını kesin olarak gösterir. Arama ağacın tamamını gezip bir şey bulamazsa çözüm yoktur. Bu özelliğe tamlık denir.

Zayıf yanları da aynı ölçüde belirgindir.

• Üstel en kötü durum. Zaman karmaşıklığı 2ⁿ, n! ya da 9^m gibi üstel fonksiyonlarla sınırlanır.
• Büyük arama uzaylarında yavaşlık. Olası çözüm sayısı çok büyük olduğunda iyi bir budama ve sezgisel gerekir.
• Yığın belleği. Derin özyineleme her seviye için bir çerçeve kullanır: O(derinlik) bellek. Çok derin aramalarda Java yığını taşabilir.
• Tekrar eden iş. Aynı alt problem farklı yollardan tekrar tekrar çözülebilir. Dinamik programlama bu sonuçları tabloda saklar; geri izleme saklamaz.

9.3N vezir problemi

9.3.1Problem

Satrançta vezir en güçlü taştır. Bulunduğu satır, sütun ve iki çapraz boyunca istediği kadar ilerleyebilir. Bu dört doğru üzerindeki her taşı tehdit eder. 8 vezir problemi (eight queens) 1848'de bir satranç dergisinde sorulmuş eski bir bulmacadır: 8 vezir, hiçbiri bir diğerini tehdit etmeyecek biçimde 8 × 8'lik tahtaya yerleştirilebilir mi?

Problemin genel biçiminde bazı küçük durumlar ilginçtir. n = 1 için tek vezir tek kareye konur; bu bir çözümdür. n = 2 ve n = 3 için çözüm yoktur. 2 × 2'lik tahtada her iki kare çifti ya aynı satırda, ya aynı sütunda ya da aynı çaprazdadır. n ≥ 4 için her zaman en az bir çözüm vardır. 8 vezir probleminin 92 çözümü bulunur. Tahtanın döndürülmesi ve yansıtılmasıyla birbirine dönüşen çözümler aynı sayılırsa 12 temel çözüm kalır.

Şekil 9.11'teki çözüm satranç gösterimiyle verilmiştir. a1, a sütununun 1. satırı, yani sol alt köşedir. Çözümün doğruluğu denetlenebilir: sekiz harf farklıdır (sütunlar farklı), sekiz sayı farklıdır (satırlar farklı). Çapraz denetimi için her çift için satır farkı ile sütun farkının mutlak değerleri karşılaştırılır; hiçbir çiftte eşit değildir. Bu denetim, problemin NP'de olmasının küçük bir örneğidir: çözümü bulmak arama ister, denetlemek ise C(8, 2) = 28 çift karşılaştırmasıyla biter.

9.3.2Satır satır yerleştirme

Geri izleme çözümü şu adımlarla ilerler.

1. Tahtanın her hücresi başlangıçta boştur.
2. İlk vezir ilk satırda bir sütuna yerleştirilir.
3. Bir sonraki satırda her sütun sırayla denenir. Vezir o sütuna konduğunda önceki vezirlerle çakışıp çakışmadığı denetlenir: aynı sütunda ya da iki çaprazdan birinde bir vezir var mı?
4. Çakışma yoksa konum geçerli kabul edilir ve bir sonraki satıra geçilir.
5. Bir satırda bütün sütunlar denenip güvenli yer bulunamazsa bir önceki satırdaki vezir kaldırılır ve o satırda sıradaki sütun denenir. Bu geri dönüştür.
6. Bütün vezirler yerleştirildiğinde çözüm bulunmuştur.

Vezirlerin satır satır konması bilinçli bir tasarım kararıdır. Her satırda tam bir vezir olmak zorundadır. Bu gözlem satır kısıtını yapının içine gömer. Vezir 0 satır 0'a, vezir 1 satır 1'e konur; iki vezirin aynı satırda olması imkânsız hâle gelir. Böylece her yerleştirmede yalnız sütun ve iki çapraz denetlenir. Arama uzayı da 64⁸'den (her vezir için 64 kare) 8⁸'e iner. Kısıtları denetlemek yerine yapıyla sağlamak, geri izlemede sık kullanılan bir tekniktir.

9.3.34 vezir: tahta ve durum uzayı ağacı

Algoritmanın işleyişi en iyi küçük bir örnekte görülür. n = 4 için vezirler satır satır yerleştirilir; her satırda sütun 0, 1, 2, 3 sırayla denenir. Durum uzayı ağacında kökün altındaki her seviye bir satırdır; bir düğüm, o satırda seçilen sütunu gösterir. Tahtadaki kırmızı hücreler, yerleşmiş vezirlerin tehdit ettiği karelerdir.

1. Satır 0: sütun 0 güvenlidir; vezir yerleştirilir ve satır 1'e inilir.
2. Satır 1: sütun 0 ve 1 tehdit altındadır; sütun 2 güvenlidir. Vezir konur, satır 2'ye inilir.
3. Satır 2: dört sütun da tehdit altındadır. Bu bir çıkmazdır. Satır 1'deki vezir (sütun 2) kaldırılır; satır 1'de sıradaki sütun denenir.

4. Satır 1: sütun 3 güvenlidir; vezir konur, satır 2'ye inilir.
5. Satır 2: sütun 0 tehdit altında, sütun 1 güvenlidir. Vezir konur, satır 3'e inilir.
6. Satır 3: dört sütun da tehdit altındadır; çıkmaz. Satır 2'deki vezir (sütun 1) kaldırılır.
7. Satır 2: kalan sütunlar 2 ve 3 de tehdit altındadır; çıkmaz. Satır 1'deki vezir (sütun 3) kaldırılır.
8. Satır 1'in denenecek sütunu kalmamıştır. Satır 0'daki vezir (sütun 0) da kaldırılır.

9. Satır 0: sütun 1 güvenlidir; vezir konur.
10. Satır 1: sütun 0, 1, 2 tehdit altında, sütun 3 güvenlidir.
11. Satır 2: sütun 0 güvenlidir.
12. Satır 3: sütun 0 ve 1 tehdit altında, sütun 2 güvenlidir. Dördüncü vezir yerleşir ve satir == n olur. Çözüm bulunmuştur: sütunlar [1, 3, 0, 2].

Ağaçtaki düğümler sayılırsa işin dökümü çıkar. Kök dışında 8 düğüm vardır: çözüm yolundaki 4 düğüm ve geri alınan 4 düğüm (0, 2, 3 ve 1). Her düğüm bir yerleştirmedir; geri alınan her düğüm bir geri dönüştür. Tehdit altındaki karelere hiç vezir konmadığı için bu kareler ağaçta düğüm olarak bile görünmez. Budamanın kazancı tam da budur.

Çözümün gösterimine dikkat edilmelidir. [1, 3, 0, 2] dizisinin i. öğesi i. satırdaki vezirin sütunudur. Satır 0'daki vezir sütun 1'de, satır 1'deki sütun 3'te, satır 2'deki sütun 0'da, satır 3'teki sütun 2'dedir. Bu gösterim, satır kısıtının yapıya gömülmesinin doğal sonucudur: her satır için tek bir sayı yeter.

9.3.4Java kodu

Algoritma iki metotla yazılır. guvenliMi, (s, k) karesine konacak bir vezirin daha önce konmuş vezirlerle çakışıp çakışmadığını denetler. coz satır satır ilerleyen geri izleme metodudur. Tahta int[][] t dizisidir; t[i][j] == 1, (i, j) karesinde vezir olduğunu gösterir. n sınıfın bir alanıdır.

boolean guvenliMi(int[][] t,
        int s, int k) {
  // aynı sütun
  for (int i = 0; i < s; i++)
    if (t[i][k] == 1) return false;
  // sol üst çapraz
  for (int i = s-1, j = k-1;
       i >= 0 && j >= 0; i--, j--)
    if (t[i][j] == 1) return false;
  // sağ üst çapraz
  for (int i = s-1, j = k+1;
       i >= 0 && j < n; i--, j++)
    if (t[i][j] == 1) return false;
  return true;
}

guvenliMi yalnız üç yöne bakar: yukarı, sol üst çapraz ve sağ üst çapraz. Aşağıdaki satırlara bakmaya gerek yoktur, çünkü vezirler satır satır konur ve s. satıra vezir konurken alt satırlar boştur. Aynı satıra da bakılmaz, çünkü her satırda en çok bir vezir vardır. İlk döngü sütundaki s hücreyi tarar. İkinci döngü (s − 1, k − 1)'den başlayıp satırı ve sütunu birlikte azaltarak sol üst köşeye doğru ilerler. Üçüncü döngü satırı azaltırken sütunu artırır. Döngü koşulları tahtanın dışına çıkılmasını engeller: j >= 0 sol kenarı, j < n sağ kenarı korur. Herhangi bir döngü bir vezir bulursa metot hemen false döndürür.

boolean coz(int[][] t, int satir) {
  if (satir == n)
    return true;
  for (int sutun = 0; sutun < n;
       sutun++) {
    if (guvenliMi(t, satir, sutun)) {
      t[satir][sutun] = 1; // yerleştir
      if (coz(t, satir + 1))
        return true;
      t[satir][sutun] = 0; // geri al
    }
  }
  return false;
}

coz şablonun doğrudan uygulamasıdır. satir == n hedef testidir: n vezir yerleşmişse çözüm bulunmuştur. Döngü satırdaki her sütunu dener. guvenliMi geçerlilik testidir ve budamayı yapar. Güvenli bir kareye vezir konur (seç), bir sonraki satır için coz çağrılır (keşfet). Çağrı true döndürürse çözüm bulunmuştur. Bu true değeri hemen yukarı iletilir; tahta olduğu gibi kalır ve çözümü içerir. Çağrı false döndürürse bu sütunla devam etmenin yolu yoktur; vezir kaldırılır (geri al) ve döngü sıradaki sütunla sürer. Döngü biterse bu satırda hiçbir sütun işe yaramamıştır ve false döndürülür. Bu false, bir üst seviyedeki coz'u kendi vezirini kaldırmaya zorlar.

Maliyet iki parçadan oluşur. guvenliMi en çok üç döngü çalıştırır; her döngü en çok n adımdır. Bu yüzden bir çağrı O(n) sürer. coz için en kötü durum, durum uzayı ağacının tamamının gezilmesidir. İlk satırda n, ikincide en çok n − 1 güvenli sütun vardır, çünkü en azından bir sütun tutulmuştur. Bu sınırla düğüm sayısı O(n!)'dir. Her düğümde n sütun için guvenliMi çağrılır. Gerçek düğüm sayısı n!'den çok daha küçüktür, ama kaba üst sınır O(n!)'dir. Bellek kullanımı tahta için O(n²), çağrı yığını için O(n)'dir.

9.3.5Kod izleme: coz(t, 0), n = 4

Kodu satır satır izlemek, ağaç izlemesinde görünmeyen bir ayrıntıyı ortaya çıkarır: her güvenlik testi bir guvenliMi çağrısıdır ve metot ilk bulduğu tehditte döner. Metot önce sütunu, sonra sol üst çaprazı, en son sağ üst çaprazı denetler. Bir kare birden çok vezirce tehdit ediliyorsa yalnız ilk denetimin bulduğu tehdit görünür. Örneğin (2, 2) karesi hem (1, 2)'deki vezirin sütunundadır hem de (0, 0)'daki vezirin çaprazındadır. Metot önce sütunu taradığı için tehdidi (1, 2)'de bulur.

Tablo kodun bütün davranışını gösterir. guvenliMi 26 kez çağrılır. Bunların 8'i true döner; bu 8 çağrı yerleştirmedir. 4 kez geri alma yapılır. Yığın derinliği, o an açık olan coz çerçevelerinin sayısıdır. Derinlik 5'e ulaştığında coz(t, 4) çerçevesi açıktır ve hedef testi true döner. Bu değer dört çerçeve boyunca yukarı taşınır. Hiçbir çerçeve kendi vezirini kaldırmaz; tahta çözümü içerir.

9.3.68 vezir: algoritmanın ilk çözümü

coz(t, 0) n = 8 için çalıştırıldığında sütunlar küçükten büyüğe denendiği için her zaman sözlüksel sıradaki ilk çözüm bulunur. Bu çözüm [0, 4, 7, 5, 2, 6, 1, 3]'tür: satır 0'daki vezir sütun 0'da, satır 1'deki sütun 4'te ve böyle sürer.

Bu çözüme ulaşana kadar guvenliMi 876 kez çağrılır, 113 vezir yerleştirilir ve 105 kez geri dönülür. Sayılar arasındaki ilişki dikkat çekicidir: 113 − 105 = 8. Her yerleştirme ya geri alınır ya da çözümde kalır; çözümde 8 vezir kaldığına göre geri kalan 105 yerleştirme geri alınmıştır. Bu eşitlik ilk çözümde duran her N vezir aramasında geçerlidir: yerleştirme − geri alma = n.

Şekil 9.11'teki a1, b7, c4, d6, e8, f2, g5, h3 yerleşimi de bir çözümdür, ama algoritmanın ilk bulduğu çözüm değildir. 92 çözümün hepsi geçerlidir; algoritma yalnız aday sırasının belirlediği ilkinde durur. Bütün çözümleri bulmak için hedef testinde çözüm kaydedilir ve false döndürülür. false, aramanın sürmesi anlamına gelir: üstteki çağrı vezirini kaldırır ve sıradaki sütunu dener.

9.3.7Çözüm ve yerleştirme sayıları

Algoritmanın n büyüdükçe nasıl davrandığını görmek için iki sayı ölçülür: bütün çözümleri bulmak için yapılan güvenli yerleştirme sayısı ve ilk çözüme kadar yapılan yerleştirme sayısı. “Yerleştirme”, güvenli bulunup tahtaya konan vezir sayısıdır; durum uzayı ağacındaki kök dışı düğüm sayısına eşittir.

Tablodan üç sonuç çıkar.

• n = 2 ve n = 3 için çözüm yoktur. Algoritma bütün ağacı gezer ve false döndürür. n = 3'te ağacın kök dışında yalnız 5 düğümü vardır; bu 5 yerleştirmenin hepsi geri alınır. Bu, “çözüm yok” cevabının kanıtıdır: arama tamdır ve hiçbir olasılığı atlamamıştır.
• Bütün çözümleri bulmanın maliyeti nⁿ'den çok küçüktür, ama yine de hızla büyür. n = 9'dan 10'a geçişte yerleştirme sayısı yaklaşık 4,2 kat artar. Büyüme kabaca n! gibidir: 10! = 3 628 800'ün yaklaşık yüzde biri.
• İlk çözüme kadar geçen iş n ile düzgün artmaz. n = 6'da 31 yerleştirme gerekirken n = 7'de yalnız 9 yeter. n = 6'nın sözlüksel ilk çözümü [1, 3, 5, 0, 2, 4] sütun 1 ile başlar; sütun 0 ile başlayan bütün dallar boşa gezilir. n = 7'nin ilk çözümü [0, 2, 4, 6, 1, 3, 5] ise neredeyse hiç geri dönüş gerektirmez: yalnız 2 geri alma yapılır.

9.3.8O(1) güvenlik testi

guvenliMi her çağrıda sütunu ve iki çaprazı tarar ve O(n) sürer. 8 vezirde ilk çözüme kadar 876 çağrı yapıldığı düşünülürse bu maliyet önemsiz değildir. Tarama yerine her sütun ve her çapraz için bir bayrak tutulursa test O(1)'e iner. Bunun için çaprazların nasıl numaralandırılacağı bilinmelidir.

Bir kare (r, c) ile gösterilsin. Sağ üstten sol alta inen ters köşegen üzerinde bir kareden ötekine geçerken satır bir artar, sütun bir azalır. Bu yüzden r + c toplamı sabit kalır. Sol üstten sağ alta inen köşegende ise satır ve sütun birlikte artar; r − c farkı sabittir. n × n tahtada r + c, 0 ile 2n − 2 arasında değer alır; 2n − 1 ters köşegen vardır. r − c ise −(n − 1) ile n − 1 arasındadır. Bu değere n − 1 eklenirse indis 0'dan başlar ve yine 2n − 1 değer çıkar.

boolean[] sut = new boolean[n];
boolean[] k1 = new boolean[2*n-1]; // r+c
boolean[] k2 = new boolean[2*n-1]; // r-c+n-1

void coz(int r) {
  if (r == n) { sayac++; return; }
  for (int c = 0; c < n; c++) {
    int a = r + c, b = r - c + n - 1;
    if (sut[c] || k1[a] || k2[b])
      continue;
    sut[c] = k1[a] = k2[b] = true;
    coz(r + 1);
    sut[c] = k1[a] = k2[b] = false;
  }
}

Kodda üç boolean dizisi vardır. sut[c], c. sütunda vezir olup olmadığını; k1[a], a = r + c numaralı ters köşegende; k2[b], b = r − c + n − 1 numaralı köşegende vezir olup olmadığını gösterir. Bir karenin güvenli olup olmadığı üç dizi erişimiyle anlaşılır. Bayraklardan biri true ise kare tehdit altındadır ve continue ile sıradaki sütuna geçilir. Değilse üç bayrak birden true yapılır (seç), bir alt satır çözülür (keşfet), sonra üç bayrak false yapılır (geri al).

Bu sürüm iki açıdan da farklıdır. Birincisi, tahta dizisine gerek kalmaz. Bayraklar çakışmayı tek başına denetler. Çözümün kendisi gerekiyorsa bir yer[satir] = sutun dizisi tutmak yeter. İkincisi, metot void'dir ve ilk çözümde durmaz. Hedef testinde sayac artırılır ve metot döner; arama sürer. Bu yüzden kod bütün çözümleri sayar. n = 8 için sayac 92 olur ve 2056 yerleştirme yapılır; bu sayılar tahta tabanlı sürümle aynıdır, çünkü iki sürüm aynı ağacı aynı sırayla gezer. Değişen yalnız her düğümdeki iştir.

9.3.9Bütün çözümleri saymak

Tahta tabanlı coz da bütün çözümleri sayacak biçimde değiştirilebilir. Değişiklik yalnız hedef testindedir.

int sayac = 0;

boolean coz(int[][] t, int satir) {
  if (satir == n) {
    sayac++;          // çözümü say
    return false;     // aramayı sürdür
  }
  for (int sutun = 0; sutun < n; sutun++) {
    if (guvenliMi(t, satir, sutun)) {
      t[satir][sutun] = 1;
      coz(t, satir + 1);
      t[satir][sutun] = 0;   // geri al
    }
  }
  return false;
}

Hedef testinde sayac artırılır ve false döndürülür. false değeri üst çağrıya “bu yol bitti, aramayı sürdür” der. Üst çağrı vezirini kaldırır ve sıradaki sütunu dener. Metot hiçbir zaman true döndürmediği için özyinelemeli çağrının sonucuna bakmaya da gerek kalmaz. Kod n = 4, 5, 6, 7, 8 için sırasıyla 2, 10, 4, 40 ve 92 çözüm sayar.

Hedef testinde true döndürmek ise yanlış olurdu. Bu durumda ilk çözümde bütün çağrılar sona erer ve sayac 1'de kalır. Aynı şekilde geri alma satırını silmek de yanlış olurdu. Tahta önceki denemelerin vezirleriyle dolar ve sonraki denemeler hatalı biçimde budanır.

Bütün çözümler aranırken tahtanın simetrisinden yararlanılabilir. Bir çözüm dikey eksene göre yansıtılırsa yine bir çözüm elde edilir. İlk satırdaki vezir sütun c'deyse yansıması n − 1 − c'dedir. Bu yüzden ilk vezir yalnız sol yarıda denenir ve bulunan her çözüm iki kez sayılır. n tekse orta sütunda başlayan çözümlerin yansıması da orta sütunda başlar; onlar bir kez sayılır. n = 8 için bu yöntem 2056 yerine 1028 yerleştirmeyle aynı 92 sonucuna ulaşır: iş tam yarıya iner. n = 9'da yerleştirme 8393'ten 4703'e düşer; orta sütun tek başına sayıldığı için kazanç biraz azdır.

9.4En az çakışma sezgiseli

9.4.1Tam yerleşimden onarıma

Geri izleme çözümü boş bir tahtadan başlayarak kurar ve her adımda geçerliliği korur. N vezir problemine bambaşka bir yoldan da yaklaşılabilir. Önce bütün vezirler tahtaya konur; her sütuna bir vezir. Bu yerleşim büyük olasılıkla geçersizdir: bazı vezirler birbirini tehdit eder. Sonra çakışmalar küçük, yerel değişikliklerle tek tek onarılır. Bu yaklaşımın adı en az çakışma sezgiselidir (min-conflicts heuristic).

N vezir için değişkenler sütunlardır ve her değişkenin değeri o sütundaki vezirin satırıdır. yer[k] = r, k. sütundaki vezirin r. satırda olduğunu gösterir. Sütun kısıtı yapıya gömülüdür; her sütunda tam bir vezir vardır. Çakışmalar satırlarda ve çaprazlarda çıkar.

enAzCakisma(n, maksAdim):
  // başlangıç: açgözlü yerleşim
  for k = 0 .. n-1:
    yer[k] = en az çakışmalı satır
  for adim = 1 .. maksAdim:
    if çakışma yok: return yer
    k = rastgele çakışan sütun
    yer[k] = argmin_r cakisma(k, r)
             // eşitlikte rastgele
  return başarısız

Sözde kodun iki evresi vardır. Başlangıç evresi vezirleri sütun sütun yerleştirir. Her sütunda, o ana kadar konmuş vezirlerle en az çakışan satır seçilir; eşitlik varsa satırlardan biri rastgele alınır. Bu, açgözlü bir başlangıçtır ve çoğu zaman yalnız birkaç çakışma bırakır. Onarım evresi her adımda çakışan vezirlerden birini rastgele seçer. Seçilen vezir kendi sütunu içinde, en az çakışma yaratan satıra taşınır. Burada da eşitlik rastgele bozulur. Çakışma kalmadığında yerleşim bir çözümdür. maksAdim adım içinde çözüm bulunamazsa arama başarısız sayılır.

9.4.2Çakışma sayısı

Algoritmanın temel hesabı şudur: k. sütundaki vezir r. satıra taşınsa kaç vezirle çakışır? Bu sayı, aynı satırdaki ve aynı çaprazlardaki öteki vezirlerin sayısıdır.

int cakisma(int[] yer, int k, int r) {
  int c = 0;
  for (int j = 0; j < yer.length; j++) {
    if (j == k) continue;                       // vezirin kendisi
    if (yer[j] == r                             // aynı satır
        || Math.abs(yer[j] - r) == Math.abs(j - k))   // çapraz
      c++;
  }
  return c;
}

Metot bütün sütunları tarar. Vezirin kendi sütunu atlanır. j. sütundaki vezir aynı satırdaysa sayaç artar. Satır farkının mutlak değeri sütun farkının mutlak değerine eşitse iki kare aynı çaprazdadır; sayaç yine artar. Hesap O(n) sürer. Bir sütunun bütün satırları için hesaplanırsa O(n²) olur. Büyük n için her satırda, her köşegende ve her ters köşegende kaç vezir olduğu sayaçlarla tutulur. Bu durumda tek bir çakışma sayısı O(1)'de okunur.

9.4.3Onarım adımları

8 vezirde algoritmanın bir çalışması şöyle ilerler. Açgözlü başlangıç yer = [7, 2, 4, 1, 4, 0, 3, 6] yerleşimini üretir. Bu yerleşimde yalnız bir çift çakışır: sütun 2 ve sütun 4'teki vezirler aynı satırdadır (4). Şekillerde vurgulu sütundaki sayılar, kırmızı vezirin o satıra taşınması hâlinde kaç vezirle çakışacağını gösterir; vezirin kendi satırı boş bırakılmıştır.

Tablo yerel aramanın iki önemli davranışını gösterir. Birincisi, her onarım çakışmayı gidermez; bazen yerini değiştirir. 1. adımda sütun 4'teki vezir satır 7'ye taşınır. Sütun 2 ile çakışma biter, ama sütun 0'daki vezir de satır 7'dedir ve yeni bir çakışma doğar. Çakışan çift sayısı 1'de kalır. Algoritma çakışma sayısını hiç artırmaz, ama azaltmayı da garanti etmez.

İkincisi, algoritma platolara takılabilir. 4. adımda sütun 5'teki vezir satır 4'tedir ve (6, 7) karesindeki vezirle aynı çaprazdadır. Satır 3, 4 ve 5'in hepsinde çakışma sayısı 1'dir. Hiçbir taşıma durumu iyileştirmez; bu bir platodur. Sezgisel eşitliği rastgele bozar ve vezir satır 5'e geçer. Orada bu kez sütun 1 ile aynı satırdadır. Sütun 5 platoda 3, 4 ve 5 arasında birkaç kez gidip gelebilir. Rastgele seçim sayesinde sonunda başka bir çakışan vezir, sütun 1, seçilir ve arama platodan çıkar. 7. adımda sütun 0 için satır 4'te 0 çakışma vardır; vezir oraya taşınır ve çözüm bulunur.

Bulunan çözüm, satır sırasıyla değil sütun sırasıyla yazılmıştır. Geri izleme algoritmasının [0, 4, 7, 5, 2, 6, 1, 3] çözümüyle karşılaştırılırken bu fark akılda tutulmalıdır. İki gösterim de bir permütasyondur; biri satırdan sütuna, öteki sütundan satıra eşlemedir.

9.4.4Yerel arama ve tamlık

En az çakışma bir yerel arama (local search) yöntemidir. Geri izlemeden üç temel farkı vardır.

• Durum. Geri izlemede durum kısmi ama her zaman geçerlidir. Yerel aramada durum tamdır, ama geçersiz olabilir.
• Bellek. Yerel aramada geri dönüş yığını yoktur. Algoritma yalnız şu anki yerleşimi tutar; geçmiş kararları hatırlamaz.
• Tamlık. Yerel arama tam değildir. Platolarda dolaşabilir ve döngüye girebilir; bu yüzden bir adım sınırı gerekir. Yalnız bir çözüm bulur ve çözüm olmadığını kanıtlayamaz. Adım sınırına ulaşmak “çözüm yok” anlamına gelmez; yalnız “bu çalışmada bulunamadı” anlamına gelir.

Buna karşılık en az çakışma büyük n için şaşırtıcı biçimde hızlıdır. Minton ve arkadaşlarının 1992'deki çalışmasına göre iyi bir açgözlü başlangıçla bir milyon vezirlik problem bile ortalama birkaç onlu onarım adımında çözülür. Geri izleme ise n büyüdükçe hızla yavaşlar. İki yöntemin güçlü yanları birbirini tamamlar. Bütün çözümleri saymak ya da çözüm olmadığını göstermek için geri izleme gerekir. Çok büyük bir örnekte tek bir çözüm hızla isteniyorsa yerel arama daha uygundur.

9.5Sudoku

9.5.1Kısıt sağlama problemi olarak Sudoku

Sudoku'nun amacı 9 × 9'luk bir tabloyu doldurmaktır. Her satırda, her sütunda ve dokuz 3 × 3'lük kutunun her birinde 1'den 9'a kadar rakamlar birer kez kullanılır. Bazı hücreler baştan verilir; bunlara ipucu denir. Kalan hücreler bu kurallara uyacak biçimde doldurulur. İyi kurulmuş bir bulmacanın tek bir çözümü vardır.

Sudoku, daha genel bir problem türünün örneğidir.

Sudoku'da değişkenler boş hücrelerdir. Her değişkenin alanı {1, …, 9}'dur. Kısıtlar “aynı birimde farklı” biçimindedir: aynı satırdaki, aynı sütundaki ve aynı kutudaki hücreler farklı rakam almalıdır. N vezir de bir kısıt sağlama problemidir: değişkenler satırlar, alanlar sütunlardır. Çizge boyamada değişkenler düğümler, alanlar renklerdir. Geri izleme kısıt sağlama problemlerinin genel çözüm yöntemidir.

9.5.2Algoritma

Geri izleme algoritması Sudoku'yu şu adımlarla çözer.

1. Boş bir hücreye bir rakam atanır.
2. Atanan rakam geçerliyse, yani aynı satırda, sütunda ve kutuda yoksa, bir sonraki boş hücreye geçilir.
3. Geçerli değilse sıradaki rakam denenir.
4. Bir hücrede bütün rakamlar denenmiş ve hiçbiri işe yaramamışsa önceki hücreye geri dönülür ve orada farklı bir rakam denenir.
5. Adımlar bütün hücreler dolana kadar tekrarlanır.

Bu, genel şablonun doğrudan uygulamasıdır. Kısmi çözüm doldurulmuş hücrelerdir. Adaylar 1–9 rakamlarıdır. Kısıt testi gecerliMi'dir. Hedef, boş hücre kalmamasıdır.

Şekildeki küçük bulmaca 2 × 2'lik kutularla oynanır ve rakamlar 1–4'tür. Bu bulmacada hiç çıkmaza girilmez: (0, 1)'e 2, (0, 2)'ye 3 yazılır ve kalan altı boş hücre de ilk geçerli rakamla dolar. Sekiz yerleştirmede çözüm bulunur. Büyük bulmacada durum çok farklıdır.

9.5.3Java kodu

boolean coz(int[][] t) {
  for (int s = 0; s < 9; s++)
    for (int k = 0; k < 9; k++)
      if (t[s][k] == 0) {
        for (int r = 1; r <= 9; r++)
          if (gecerliMi(t, s, k, r)) {
            t[s][k] = r;
            if (coz(t)) return true;
            t[s][k] = 0;   // geri al
          }
        return false;  // rakam yok
      }
  return true;  // boş hücre yok
}

coz her çağrıda tabloyu baştan tarar ve ilk boş hücreyi arar. Boş hücre (s, k) bulunca 1'den 9'a kadar her rakamı dener. Geçerli bir rakam yazılır ve coz yeniden çağrılır. Bu çağrı bir sonraki boş hücreyi bulur. Çağrı true döndürürse çözüm bulunmuştur. false döndürürse rakam silinir ve sıradaki rakam denenir. Dokuz rakamın hiçbiri işe yaramazsa return false çalışır. Bu satır geri dönüşü tetikler: üst çağrı kendi hücresindeki rakamı siler.

Kodun yapısında ince bir nokta vardır. return false iki döngünün içinde, ilk boş hücrenin işlendiği bloğun sonundadır. Metot ilk boş hücreyi işledikten sonra kalan hücrelere bakmaz. İlk boş hücre doldurulamıyorsa geri kalan hücreleri doldurmaya çalışmanın anlamı yoktur. Döngüler hiç boş hücre bulmadan biterse en alttaki return true çalışır: tablo doludur.

boolean gecerliMi(int[][] t,
    int s, int k, int r) {
  for (int i = 0; i < 9; i++)
    if (t[s][i] == r || t[i][k] == r)
      return false;
  int bs = s / 3 * 3;
  int bk = k / 3 * 3;
  for (int i = bs; i < bs + 3; i++)
    for (int j = bk; j < bk + 3; j++)
      if (t[i][j] == r)
        return false;
  return true;
}

gecerliMi, r rakamının (s, k) hücresine yazılıp yazılamayacağını denetler. İlk döngü tek geçişte hem satırı (t[s][i]) hem sütunu (t[i][k]) tarar. Ardından hücrenin kutusu taranır. Kutunun sol üst köşesi bs = s / 3 * 3 ve bk = k / 3 * 3 ile bulunur. Tam sayı bölmesi aşağı yuvarlar; 3 ile çarpmak da sonucu kutu numarasından indise çevirir. (7, 4) hücresi için 7 / 3 = 2, 2 · 3 = 6; 4 / 3 = 1, 1 · 3 = 3. Kutu 6–8. satırları ve 3–5. sütunları kapsar. Metot satır ve sütun için 18, kutu için 9 olmak üzere en çok 27 hücreye bakar; bu sabit bir iştir.

9.5.4Adım adım çözüm

Algoritma örnek bulmacada boş hücreleri satır satır, soldan sağa doldurur; her hücrede 1–9 sırayla denenir. Satır 0'da ipuçları 5, 3 ve 7'dir. İlk beş boş hücreye (0, 2), (0, 3), (0, 5), (0, 6) ve (0, 7) sırasıyla 1, 2, 4, 8 ve 9 girilir. Her biri o hücre için geçerli en küçük rakamdır. (0, 8) hücresinde hiçbir rakam geçerli değildir: satırda eksik kalan tek rakam 6'dır, o da 8. sütunda (5, 8) hücresinde vardır. Bu ilk çıkmazdır; o ana kadar 5 yerleştirme yapılmış, hiç geri alınmamıştır.

Geri dönüş başlar. (0, 7)'deki 9 silinir; o hücrede 9'dan büyük rakam yoktur ve (0, 7) de çıkmaz olur. (0, 6)'daki 8 silinir ve 9 denenir. Bu kez (0, 7)'ye hiçbir rakam uymaz; 9 da silinir. (0, 6) da çıkmazdır. Geri dönüş (0, 5)'e kadar uzanır ve orada 4 yerine 6 denenir. Bu noktada 7 yerleştirme ve 4 geri alma yapılmıştır. Ardından (0, 6)'ya 4, (0, 7)'ye 9, (0, 8)'e 8 yazılır ve satır 0 ilk kez tamamlanır: 5 3 1 2 7 6 4 9 8. Bu satır kendi içinde geçerlidir, ama çözüme götürüp götürmediği henüz bilinmez.

Gerçekten de götürmez. Satır 1'de yapılan bütün denemeler çıkmaza girer. Geri dönüş satır 0'a kadar uzanır ve (0, 8)'deki 8 silinir; o ana kadar 31 yerleştirme ve 26 geri alma yapılmıştır. Erken verilen bir karar ancak çok sonra yanlış çıkabilir. Algoritma bunu ancak o karara dayanan her şeyi denedikten sonra anlar.

Tablo aramanın düzensiz ilerleyişini gösterir. İlk üç satır 377 yerleştirmede yerine oturur. Satır 4 ile satır 5 arasında ise 2665 yerleştirme yapılır. Bu aralıkta algoritma satır 3–5'teki seçimleri defalarca değiştirir. Satır 6'dan sonra neredeyse hiç geri dönüş kalmaz: son 11 yerleştirmenin hiçbiri geri alınmaz. Sonunda 51 boş hücrenin hepsi dolar ve bütün kısıtlar sağlanır. Toplam 4208 yerleştirme ve 4157 geri alma yapılmıştır. Fark 4208 − 4157 = 51'dir: çözümde kalan rakamlar.

9.5.5Maliyet ve MRV

Kaba kuvvet 51 boş hücrenin her birine 9 rakamdan birini yazıp sonra denetleseydi 9⁵¹ ≈ 4,6 · 10⁴⁸ atama gerekirdi. Budama bu sayıyı 4208'e indirir. En kötü durum için üst sınır yine O(9^m)'dir; m boş hücre sayısıdır. Ama pratikte ağacın küçük bir kısmı gezilir.

Aynı bulmaca çok daha az işle de çözülebilir. Satır satır ilk boş hücreyi doldurmak zorunlu değildir. Hangi hücrenin önce doldurulacağı bir seçimdir ve bu seçim aramanın boyunu belirler. MRV (minimum remaining values, en az kalan değer) sezgiseli her adımda en az adayı kalan boş hücreyi doldurur.

boolean cozMRV(int[][] t) {
  int es = -1, ek = -1, enAz = 10;
  for (int s = 0; s < 9; s++)
    for (int k = 0; k < 9; k++)
      if (t[s][k] == 0) {
        int aday = 0;
        for (int r = 1; r <= 9; r++)
          if (gecerliMi(t, s, k, r)) aday++;
        if (aday < enAz) { enAz = aday; es = s; ek = k; }
      }
  if (es < 0) return true;              // boş hücre yok
  for (int r = 1; r <= 9; r++)
    if (gecerliMi(t, es, ek, r)) {
      t[es][ek] = r;
      if (cozMRV(t)) return true;
      t[es][ek] = 0;                    // geri al
    }
  return false;
}

Metot önce bütün boş hücreleri tarar ve her biri için kaç geçerli rakam kaldığını sayar. Adayı en az olan hücre (es, ek) seçilir. Boş hücre yoksa tablo doludur. Seçilen hücrede geçerli rakamlar sırayla denenir; yapı öteki geri izleme kodlarıyla aynıdır. Bir hücrede aday sayısı 0 ise döngü hiç çalışmaz ve metot hemen false döner. Bu, çelişkinin erkenden fark edilmesidir.

Bu bulmacada MRV her adımda tek adaylı bir hücre bulur. Başlangıçta 51 boş hücrenin 4'ünün tek adayı vardır. Bunlardan biri doldurulunca komşu hücrelerin adayları azalır ve yeni tek adaylı hücreler ortaya çıkar. Zincir hiç kopmaz. 51 yerleştirmenin hepsi doğrudur ve hiç geri dönüş gerekmez. Her adımdaki tarama 81 hücre ve 9 rakam için gecerliMi çağırdığı için adım başına iş artar. Ama adım sayısı 4208'den 51'e düştüğü için toplam iş yine çok azalır.

MRV her bulmacada geri dönüşü sıfırlamaz. Zor bulmacalarda bir noktada her boş hücrenin en az iki adayı kalır. O zaman MRV iki adaylı bir hücre seçer ve yanlış adayı denerse geri dönmek zorunda kalır. Yine de en az adaylı hücre ile başlamak, dallanmayı en küçük tutar ve çelişkileri olabildiğince erken ortaya çıkarır.

9.6Çizge boyama

9.6.1Problem

Bir haritada komşu ülkelerin farklı renklerle boyanması istenir. Ülkeler düğüm, ortak sınırlar kenar olarak düşünülürse bu soru bir çizge problemine dönüşür. Aynı problem başka kılıklarda da karşımıza çıkar. Sınav çizelgesinde aynı öğrencinin girdiği iki sınav aynı saate konamaz; sınavlar düğüm, çakışmalar kenar, saatler renktir. Derleyicide aynı anda canlı olan iki değişken aynı yazmacı paylaşamaz; değişkenler düğüm, yazmaçlar renktir.

Geri izleme bu probleme doğal biçimde uyar. Düğümler 0, 1, 2, … sırasıyla boyanır. Kısmi çözüm, ilk k düğümün renkleridir. Adaylar m renktir. Kısıt, bir düğümün rengi komşularından hiçbirinin rengiyle aynı olmamasıdır. 3-boyamanın karar sürümü NP-tamdır; m = 2 için ise problem polinom sürede çözülür, çünkü 2-boyanabilirlik iki parçalı olmaya denktir ve bir genişlik öncelikli aramayla sınanabilir.

9.6.2Adım adım: altı düğümlü çizge

Çizgenin altı düğümü ve dokuz kenarı vardır: 0–1, 0–2, 0–5, 1–3, 1–4, 2–3, 2–5, 3–4 ve 4–5. Üç renk kullanılır: 1 mavi, 2 yeşil, 3 turuncu. Her düğümde renkler 1, 2, 3 sırasıyla denenir.

Çıkmazın kaynağı 4. adımdaki karardır. Düğüm 3 mavi boyanınca düğüm 4 turuncu olmak zorunda kalır. Düğüm 5 ise mavi düğüm 0'a, yeşil düğüm 2'ye ve turuncu düğüm 4'e komşudur. Geri dönüş önce düğüm 4'e gider. Düğüm 4'te 3'ten büyük renk yoktur ve o da çıkmaza girer. Geri dönüş düğüm 3'e uzanır. Düğüm 3 turuncu olunca düğüm 4 mavi olabilir; düğüm 5'in komşuları mavi, yeşil ve mavi olur ve düğüm 5 turuncu boyanır. Geçerli 3-boyama [1, 2, 2, 3, 1, 3] bulunur.

9.6.3Java kodu ve kod izleme

boolean boya(int v) {
  if (v == n) return true;          // bitti
  for (int c = 1; c <= m; c++) {
    if (uygunMu(v, c)) {
      renk[v] = c;                  // seç
      if (boya(v + 1)) return true; // keşfet
      renk[v] = 0;                  // geri al
    }
  }
  return false;                     // çıkmaz
}
// uygunMu: v'nin c renkli komşusu yoksa true

boya(v), düğüm 0'dan v − 1'e kadarının boyandığını varsayar ve v. düğümden itibaren boyamayı sürdürür. v == n ise bütün düğümler boyanmıştır. Döngü renkleri 1'den m'ye kadar dener. Uygun bir renk renk[v]'ye yazılır ve bir sonraki düğüme geçilir. Alt çağrı başarısız olursa renk 0 yapılır; 0, “boyanmamış” anlamına gelir. Bütün renkler başarısız olursa false döner.

uygunMu'nun gövdesi sunumda tek satırlık bir açıklamayla verilmiştir. Komşuluk matrisiyle yazılmış bir sürümü şöyledir:

boolean uygunMu(int v, int c) {
  for (int u = 0; u < n; u++)
    if (komsu[v][u] == 1 && renk[u] == c)
      return false;   // c renkli bir komşu var
  return true;
}

Metot v'nin bütün komşularına bakar. Komşulardan biri c rengindeyse false döner. Henüz boyanmamış komşuların rengi 0'dır ve hiçbir c ile eşleşmez. Bu yüzden yalnız önceden boyanmış komşular kısıtı etkiler. Komşuluk matrisiyle bu denetim O(n), komşuluk listesiyle O(derece) sürer.

Kod izlemesi için daha küçük bir çizge kullanılsın: beş düğüm ve altı kenar, 0–1, 0–3, 1–3, 1–4, 2–4 ve 3–4. m = 3'tür.

İzlemenin ilginç noktası düğüm 2'dir. Düğüm 2'nin tek komşusu düğüm 4'tür ve 2 boyanırken düğüm 4 henüz boyanmamıştır. Bu yüzden düğüm 2 ilk denemede renk 1'i alır. Bu seçim yerel olarak doğrudur, ama düğüm 4'ün üç komşusunu (1, 2 ve 3) üç farklı renge zorlar. Hata ancak düğüm 4'e gelince anlaşılır. Geri dönüş düğüm 3'ten geçerek düğüm 2'ye kadar uzanır. Düğüm 2 yeşil olunca düğüm 4 mavi boyanabilir. Sonuç [1, 2, 2, 3, 1]'dir.

Maliyet açısından en kötü durumda her düğüm m rengin hepsini dener. Ağacın yaprak sayısı en çok mⁿ'dir. Her düğümde uygunMu O(n) sürer. Toplam süre O(n · mⁿ)'dir. Bellek renk dizisi ve çağrı yığını için O(n)'dir.

Renklerin simetrisi gereksiz işin bir kaynağıdır. Bir boyamada renklerin adları değiştirilirse yine geçerli bir boyama elde edilir: [1, 2, 2, 3, 1] ile [2, 1, 1, 3, 2] aynı yapıyı verir. Bu yüzden düğüm 0'ın rengini 1 olarak sabitlemek aramayı kabaca m kat küçültür. Bir çıkmaz bulunduğunda düğüm 0'ı başka renkle denemek anlamsızdır; renk adları değişse de aynı çıkmaza girilir.

9.6.4Tek uzunluklu döngü ve en az renk sayısı

Örnek genel bir kuralın özel hâlidir. Tek uzunluklu bir döngü iki renkle boyanamaz. Çift uzunluklu döngüler ise iki renkle boyanabilir: renkler dönüşümlü dağıtılır ve son düğüm ilk düğümden farklı renkte kalır. Daha genel olarak bir çizge ancak ve ancak tek uzunluklu döngü içermiyorsa, yani iki parçalıysa, 2-boyanabilir. Bir çizgenin renk sayısını bulmak için boya artan m değerleriyle çalıştırılabilir: 1, 2, 3, … İlk başarılı m renk sayısıdır. Başarısız her denemenin ağacın tamamını gezdiğine dikkat edilmelidir; en pahalı adım genellikle son başarısız denemedir.

9.7Hamilton yolu

9.7.1Problem ve adım adım çözüm

Hamilton yolu, her kenardan tam bir kez geçen Euler yoluna benzer görünür, ama zorluk açısından çok farklıdır. Euler yolunun varlığı düğüm derecelerine bakılarak doğrusal sürede anlaşılır. Hamilton yolu problemi ise NP-tamdır; bilinen bütün kesin algoritmalar üstel süre harcar.

Geri izlemede kısmi çözüm bir yoldur: yol[0..konum − 1]. Aday, yola eklenecek bir sonraki düğümdür. Kısıt iki parçalıdır: yeni düğüm yolun son düğümüne komşu olmalı ve yolda daha önce bulunmamalıdır. Hedef, yolun n düğüme ulaşmasıdır.

Örnek çizgenin beş düğümü ve altı kenarı vardır: 0–1, 0–2, 1–3, 1–4, 2–3 ve 3–4. Yol düğüm 0'dan başlar; yol[0] = 0. Her konumda düğümler 0, 1, 2, … sırasıyla denenir.

1. Konum 1: düğüm 1, 0'a komşudur; yol[1] = 1.
2. Konum 2: 1'in komşuları 0, 3 ve 4'tür. 0 yoldadır; ilk uygun düğüm 3'tür. yol[2] = 3.
3. Konum 3: 3'ün komşuları 1, 2 ve 4'tür. İlk uygun düğüm 2'dir. yol[3] = 2.
4. Konum 4: son düğüm 2'nin komşuları 0 ve 3'tür; ikisi de yoldadır. Çıkmaz. Düğüm 2 çıkarılır.
5. Konum 3: sıradaki uygun düğüm 4'tür. yol[3] = 4.
6. Konum 4: 4'ün komşuları 1 ve 3 yoldadır. Çıkmaz. Düğüm 4 çıkarılır.
7. Konum 3: 3'ün denenmemiş komşusu kalmadı. Düğüm 3 de çıkarılır.
8. Konum 2: 1'in sıradaki uygun komşusu 4'tür. yol[2] = 4.
9. Konum 3: 4'ün yolda olmayan komşusu 3'tür. yol[3] = 3.
10. Konum 4: 3'ün yolda olmayan komşusu 2'dir. yol[4] = 2. Yol beş düğüme ulaştı.

9.7.2Java kodu

boolean bul(int[][] graf, int[] yol, int konum) {
  if (konum == graf.length) return true;
  for (int v = 0; v < graf.length; v++) {
    if (uygunMu(v, graf, yol, konum)) {
      yol[konum] = v;
      if (bul(graf, yol, konum + 1)) return true;
      yol[konum] = -1;     // geri al
    }
  }
  return false;
}

boolean uygunMu(int v, int[][] graf,
                int[] yol, int konum) {
  if (graf[yol[konum - 1]][v] == 0) return false;
  for (int i = 0; i < konum; i++)
    if (yol[i] == v) return false;
  return true;
}

graf komşuluk matrisidir; graf[u][v] == 1, u ile v arasında kenar olduğunu gösterir. Çağıran kod yol dizisini −1 ile doldurur, yol[0] = 0 yapar ve bul(graf, yol, 1)'i çağırır. konum == graf.length hedef testidir: yolda n düğüm vardır. Döngü her düğümü aday olarak dener. uygunMu iki kısıtı denetler. İlk satır, adayın son düğüme, yani yol[konum − 1]'e komşu olup olmadığına bakar. Döngü ise adayın yolda olup olmadığını tarar. Geri alma satırı yol[konum] = -1'dir.

Burada da permütasyon kodundaki gözlem geçerlidir: geri alma satırı mantık için şart değildir. uygunMu yalnız yol[0..konum − 1]'e bakar ve yol[konum]'daki eski değer bir sonraki denemede üzerine yazılır. Yine de −1 yazmak durumu temiz tutar ve hata ayıklamayı kolaylaştırır.

Maliyet hesabı permütasyonlara benzer. Yolun her konumu kalan düğümlerden biridir; en kötü durumda (n − 1)! sıra denenir. Her düğümde n aday için uygunMu O(n) sürer. Kaba sınır O(n · n!)'dir. Yolda olup olmadığı bir boolean dizisiyle tutulursa uygunMu O(1)'e iner.

9.7.3Kod izleme: ikinci çizge

Kod ikinci bir çizgede izlensin. Beş düğüm ve altı kenar vardır: 0–1, 0–2, 1–2, 1–3, 2–3 ve 2–4. Düğüm 4'ün tek komşusu 2'dir. Bu yüzden düğüm 4 bir Hamilton yolunda ancak uçta bulunabilir.

İzlemede algoritma, düğüm 4'ün yalnız uçta olabileceğini bilmez. Önce 2'den sonra 3'ü dener, sonra 4'ü. İki deneme de çıkmaza girer. Bir insan bu çizgeye bakınca “4 son düğüm olmalı, 2 de sondan bir önceki” der ve aramayı hemen daraltır. Bu tür akıl yürütmeler budama kurallarına çevrilebilir. Örneğin yolda olmayan bir düğümün yolda olmayan komşusu kalmamışsa ve bu düğüm son düğüme de komşu değilse dal hemen kesilebilir.

9.7.4Hamilton döngüsü

Hamilton döngüsü aramak için koddaki tek değişiklik hedef testindedir. Yol n düğüme ulaştığında son düğümün başlangıç düğümüne komşu olup olmadığına da bakılır.

boolean dongu(int[][] graf, int[] yol, int konum) {
  if (konum == graf.length)
    return graf[yol[konum - 1]][yol[0]] == 1;   // son düğüm başlangıca komşu mu?
  for (int v = 0; v < graf.length; v++) {
    if (uygunMu(v, graf, yol, konum)) {
      yol[konum] = v;
      if (dongu(graf, yol, konum + 1)) return true;
      yol[konum] = -1;     // geri al
    }
  }
  return false;
}

Hedef testi false döndürürse arama sürer; bu yol bir döngüye kapanmamıştır ve başka yollar denenir. İlk örnek çizgede bulunan 0 → 1 → 4 → 3 → 2 yolunun son düğümü 2, başlangıç düğümü 0'a komşudur. Bu yüzden dongu aynı yolu bulur ve 2 → 0 kenarıyla kapanan bir Hamilton döngüsü verir. İkinci çizgede ise Hamilton döngüsü yoktur. Düğüm 4'ün tek komşusu vardır; bir döngüde her düğümün iki komşusu kullanılır. dongu bütün ağacı gezer ve false döndürür.

9.8Kelime arama

9.8.1Problem

Bir harf ızgarasında bir kelime aranır. Kelime, komşu hücrelerden geçen bir yol boyunca okunmalıdır. Komşuluk dört yönlüdür: yukarı, aşağı, sol ve sağ. Bir hücre aynı yolda en çok bir kez kullanılabilir. Soru şudur: kelimeyi oluşturan böyle bir yol var mı?

Örnek ızgaranın üç satırı vardır: ABCE, SFCS ve ADEE. Aranan kelime “SEE” olsun. Her hücre sırayla başlangıç olarak denenir. Komşu yönler yukarı, aşağı, sol, sağ sırasıyla denenir.

1. (1, 0) = 'S' kelimenin ilk harfiyle eşleşir ve ziyaret edildi olarak işaretlenir. Komşuları A, A ve F'dir; hiçbiri 'E' değildir. Geri dönülür ve işaret kaldırılır.
2. (1, 3) = 'S' eşleşir ve işaretlenir. Yukarı komşusu (0, 3) = 'E' eşleşir ve işaretlenir.
3. (0, 3)'ün komşuları: yukarısı ızgara dışı, aşağısı (1, 3) ziyaretli, solu (0, 2) = 'C', sağı ızgara dışı. Üçüncü harf bulunamaz; işaret kaldırılır.
4. (1, 3)'ün aşağı komşusu (2, 3) = 'E' eşleşir ve işaretlenir.
5. (2, 3)'ün sol komşusu (2, 2) = 'E' eşleşir. Son harf de eşleşti: “SEE” bulundu.

9.8.2Java kodu

boolean ara(char[][] iz, String kelime, int i,
            int s, int k, boolean[][] ziyaret) {
  if (i == kelime.length()) return true;
  if (s < 0 || s >= iz.length || k < 0
      || k >= iz[0].length || ziyaret[s][k]
      || iz[s][k] != kelime.charAt(i))
    return false;
  ziyaret[s][k] = true;
  for (int d = 0; d < 4; d++)
    if (ara(iz, kelime, i + 1, s + ds[d],
            k + dk[d], ziyaret))
      return true;
  ziyaret[s][k] = false;   // geri al
  return false;
}

ara, kelimenin i. harfinden sonrasının (s, k) hücresinden başlayarak bulunup bulunamayacağını söyler. i == kelime.length() hedef testidir: bütün harfler eşleşmiştir. İkinci if beş durumu birden eler: hücre ızgaranın dışındaysa, bu yolda zaten kullanılmışsa ya da harfi beklenen harf değilse false döner. Bu eleme, kısıt testinin özyinelemeli çağrının başında yapıldığı bir yazım biçimidir. N vezir kodunda ise test çağrıdan önce, guvenliMi ile yapılıyordu. İki biçim de aynı budamayı yapar.

Testlerden geçen hücre işaretlenir (seç). Dört komşu için ara bir sonraki harfle çağrılır (keşfet). ds ve dk yön dizileridir. Komşulardan biri başarılı olursa true hemen yukarı iletilir. Hiçbiri başarılı olmazsa işaret kaldırılır (geri al) ve false döner. Dışarıdan bakan kod her hücreyi başlangıç olarak dener:

int[] ds = {-1, 1, 0, 0};   // yukarı, aşağı, sol, sağ
int[] dk = {0, 0, -1, 1};

boolean varMi(char[][] iz, String kelime) {
  for (int s = 0; s < iz.length; s++)
    for (int k = 0; k < iz[0].length; k++) {
      boolean[][] ziyaret = new boolean[iz.length][iz[0].length];
      if (ara(iz, kelime, 0, s, k, ziyaret))
        return true;
    }
  return false;
}

Hedef testinin sınır denetiminden önce yapılmasının bir nedeni vardır. Kelimenin son harfi ızgaranın kenarındaki bir hücrede eşleşirse dört komşu çağrısının bazıları ızgara dışına düşer. Ama bu çağrılarda i zaten kelimenin boyuna eşittir ve ilk satır true döndürür. Sıra ters olsaydı iki sorun çıkardı. Izgara dışına düşen çağrılar false döndürürdü. Izgara içindeki çağrılar ise kelime.charAt(i) ile kelimenin dışını okumaya çalışır ve istisna fırlatırdı. Örneğin tek hücreli bir ızgarada tek harfli bir kelime hiç bulunamazdı.

“SADE” araması da bir geri dönüş içerir. (1, 0)'daki S'den önce yukarıdaki (0, 0) = 'A' denenir. Bu A'nın komşuları B, S (ziyaretli) ve ızgara dışıdır; 'D' bulunamaz. İşaret kaldırılır ve aşağıdaki (2, 0) = 'A' denenir. Oradan (2, 1) = 'D' ve (2, 2) = 'E' ile kelime tamamlanır.

9.8.3Kod izleme: “ABCB”

“ABCB” kelimesi ızgarada yoktur, ama neden olmadığını görmek için arama izlenmelidir. Arama (0, 0)'dan başlar.

1. (0, 0) = 'A' = kelime[0]. Hücre işaretlenir.
2. kelime[1] = 'B' aranır. Yukarı ızgara dışı, aşağı (1, 0) = 'S' ≠ 'B', sol ızgara dışı. Sağdaki (0, 1) = 'B' eşleşir ve işaretlenir.
3. kelime[2] = 'C' aranır. Yukarı ızgara dışı, aşağı (1, 1) = 'F' ≠ 'C', sol (0, 0) ziyaretli. Sağdaki (0, 2) = 'C' eşleşir ve işaretlenir.
4. kelime[3] = 'B' aranır. Yukarı ızgara dışı, aşağı (1, 2) = 'C' ≠ 'B', sol (0, 1) ziyaretli, sağ (0, 3) = 'E' ≠ 'B'. Dört yön de başarısızdır. Izgaradaki tek B (0, 1)'dedir ve bu yolda kullanılmıştır.
5. (0, 2) için geri alma: ziyaret[0][2] = false, false döner.
6. (0, 1)'in ve (0, 0)'ın kalan yönleri de başarısızdır. İkisinin de işareti kaldırılır. ara(…, 0, 0, 0, …) false döner.
7. Dış döngü öteki hücreleri dener. A ile başlayan tek öteki hücre (2, 0)'dır; komşuları S, D ve ızgara dışıdır, B yoktur. “ABCB” yoktur.

Maliyet için kelimenin uzunluğu L, ızgaranın boyutları R × C olsun. Her hücre bir başlangıçtır. İlk harften sonra her adımda en çok 3 yeni yön vardır, çünkü gelinen hücre ziyaretlidir. Bu yüzden bir başlangıçtan gezilen yol sayısı O(3^L) ile sınırlıdır ve toplam süre O(R · C · 3^L)'dir. Bellek ziyaret dizisi için O(R · C), yığın için O(L)'dir. Pratikte harf eşleşmesi aramayı çok erken keser; “ABCB” araması yalnız 4 hücreyi işaretler.

9.9Diğer uygulamalar

9.9.1Alt küme toplamı

Pozitif tam sayılardan oluşan bir küme ve bir hedef değer verilsin. Toplamı tam olarak hedefe eşit olan bir alt küme var mı? Bu soru alt küme toplamı (subset sum) problemidir ve karar sürümü NP-tamdır. Durum uzayı ağacı bu kez ikili bir ağaçtır. i. seviyede i. öğe için iki seçenek vardır: öğe alınır ya da alınmaz. n öğe için ağacın 2ⁿ yaprağı vardır; her yaprak bir alt kümedir.

int[] a = {3, 5, 6, 7};
int HEDEF = 15;
boolean[] secildi = new boolean[a.length];

boolean ara(int i, int toplam) {
  if (toplam == HEDEF) return true;
  if (i == a.length || toplam > HEDEF) return false;   // budama
  secildi[i] = true;                     // al
  if (ara(i + 1, toplam + a[i])) return true;
  secildi[i] = false;                    // alma
  return ara(i + 1, toplam);
}

ara(i, toplam), ilk i öğe için karar verilmiş ve seçilenlerin toplamı toplam iken çağrılır. Hedefe ulaşılmışsa true döner. Öğe kalmamışsa ya da toplam hedefi aşmışsa false döner. İkinci koşul budamadır: öğeler pozitif olduğu için toplam bir kez hedefi aştıktan sonra bir daha azalamaz. Sonra iki dal sırayla denenir. Önce i. öğe alınır; bu dal başarısız olursa öğe bırakılır ve ikinci dal denenir. Bu kodda kısmi çözümün bir parçası olan toplam değerle geçirildiği için geri almaya gerek yoktur. Yalnız secildi dizisi geri alınır.

Arama 8 çağrıda biter ve secildi = [true, true, false, true] olur: bulunan alt küme {3, 5, 7}'dir. Ağacın tamamında 2⁵ − 1 = 31 düğüm vardır. 5. çağrı budamanın işlediği yerdir: 3, 5, 6 ve 7'nin toplamı 21'dir, hedefi aşar.

Bu budama yalnız “fazla” toplamları keser. Ters yönde de bir budama yapılabilir: kalan öğelerin hepsi alınsa bile hedefe ulaşılamıyorsa dal kesilir. Bunun için kalan[i], i. öğeden sonuna kadar olan öğelerin toplamı (sonek toplamı) olarak önceden hesaplanır ve şu satır eklenir:

if (toplam + kalan[i] < HEDEF) return false;

9.9.2Geri izlemeyle çözülen öteki problemler

Şablon çok sayıda probleme uyarlanabilir. Her uyarlamada iki soru cevaplanır: her seviyede hangi seçim yapılır, ve hangi durumda dal kesilir?

Tablodaki problemlerin bir kısmı karar ya da sayma problemidir, bir kısmı ise en iyileme problemidir. Gezgin satıcı ve sırt çantasında amaç bir çözüm değil, en iyi çözümdür. Bu problemlerde kısıt budamasının yanına ikinci bir budama eklenir. Arama sırasında o ana kadar bulunan en iyi çözüm saklanır. Bir dalın varabileceği en iyi değer, bilinen en iyi çözümden kötüyse dal kesilir. Gezgin satıcıda yarım kalmış bir turun uzunluğu zaten bilinen en iyi turdan büyükse turu tamamlamaya gerek yoktur. Bu fikir dal sınır (branch and bound) yönteminin temelidir.

SAT satırı ayrıca önemlidir. Bugün kullanılan SAT çözücülerinin temeli de geri izlemedir: değişkenlere sırayla değer verilir, bir cümle yanlış olunca geri dönülür. Modern çözücüler bu iskelete birim yayılım, çelişkiden öğrenme ve akıllı değişken sıralaması ekler. Böylece milyonlarca değişkenli endüstriyel formülleri çözebilirler.

9.10Analiz

9.10.1Karmaşıklık

Bir geri izleme algoritmasının süresi iki çarpandan oluşur:

Zaman = durum uzayı ağacında gezilen düğüm sayısı × düğüm başına iş

Düğüm başına iş genellikle polinomdur: bir kısıt testi, bir kopyalama, bir yazdırma. Düğüm sayısı ise ağacın şekline bağlıdır. Her seviyede b dal ve d seviye varsa ağaçta en çok b^d yaprak olur. Seçenekler seviye ilerledikçe azalıyorsa (permütasyonlarda olduğu gibi) yaprak sayısı n! gibi büyür.

Bu sınırlar budamayı hesaba katmaz. Budama düğüm sayısını çoğu zaman büyük ölçüde küçültür, ama en kötü durumu genellikle değiştirmez. Her zaman, budamanın hiç işlemediği kötü girdiler kurulabilir. Örneğin hiçbir alt kümenin hedefe ulaşamadığı ve toplamların hedefi hiç aşmadığı bir alt küme toplamı girdisi ağacın tamamını gezdirir.

Bellek açısından geri izleme çok tutumludur. Aynı anda yalnız tek bir kısmi çözüm ve çağrı yığınındaki çerçeveler tutulur. Yığının derinliği ağacın derinliğine eşittir. N vezirde derinlik n, Sudoku'da m, kelime aramada L'dir. Bu yüzden bellek O(derinlik) artı kısmi çözümün kendi boyudur. Ağacın genişliği ne kadar büyük olursa olsun bellek değişmez. Geniş arama yapan yöntemlerle karşılaştırıldığında bu önemli bir üstünlüktür.

9.10.2Budamayı güçlendiren sezgiseller

Geri izlemenin hızı iki şeye bağlıdır: ağacın ne kadarının budandığına ve her düğümün ne kadar sürdüğüne. Notta görülen teknikler bu iki çarpanı küçültür.

• Değişken sıralaması (MRV). En az seçeneği kalan değişken önce doldurulur. Çelişkiler erken ortaya çıkar ve dallanma küçük kalır. Örnek Sudoku'da geri dönüş sayısı 4157'den 0'a iner.
• Değer sıralaması. Bir değişkenin değerleri arasında önce en az kısıtlayan değer denenir. Bu, en az çakışma fikrinin geri izlemedeki karşılığıdır. Değer sıralaması bütün çözümler arandığında işi azaltmaz, ama ilk çözüm daha erken bulunur. Labirentte yön sırasını değiştirmek çıkmaz hücre sayısını 8'den 0'a indiriyordu.
• İleri denetim (forward checking). Bir atamadan sonra komşu değişkenlerin alanlarından çelişen değerler silinir. Alanı boşalan bir değişken varsa hemen geri dönülür. Böylece bir çıkmaz, o değişkene sıra gelmeden fark edilir.
• Hızlı kısıt testi. N vezirde sütun ve köşegen bayrakları, Sudoku'da satır, sütun ve kutu için bit maskeleri kullanılır. Test O(n)'den O(1)'e iner.
• Simetri kırma. Simetrik çözümlerden yalnız biri aranır. N vezirde ilk vezir yalnız sol yarıda denenir ve bulunan çözümler yansıtılır: 8 vezirde yerleştirme sayısı 2056'dan 1028'e iner. Çizge boyamada ilk düğümün rengi sabitlenir.
• Sınır (bound). En iyilemede kısmi çözümün ulaşabileceği en iyi değer, bilinen en iyi çözümden kötüyse dal kesilir. Bu, dal sınır yöntemidir.

Bu tekniklerin ortak bir dersi vardır: bir aramanın maliyeti, aranan uzayın boyundan çok, aramanın nasıl düzenlendiğine bağlıdır. 9⁵¹ büyüklüğündeki bir uzay, doğru hücre sırasıyla 51 adımda çözülür.

9.10.3Geri izlemeyi ayıran ne?

Geri izleme dersin öteki algoritma tasarım yöntemleriyle karşılaştırıldığında yeri daha iyi anlaşılır.

Açgözlü yöntemle karşılaştırma öğreticidir. Açgözlü bir algoritma durum uzayı ağacında kökten yaprağa tek bir yol izler. Her düğümde en iyi görünen çocuğa iner ve bir daha geri dönmez. Geri izleme aynı ağaçta derinlik öncelikli bir arama yapar. Açgözlü seçim yanlışsa geri izleme bunu fark eder ve düzeltir. En az çakışmanın açgözlü başlangıcı bunu gösterir: başlangıç neredeyse doğrudur, ama tek bir çakışmayı gidermek için yine de onarım gerekir.

Dinamik programlamayla karşılaştırma da önemlidir. İki yöntem de bütün seçenekleri dener. Fark, alt problemlerin saklanıp saklanmamasındadır. Alt küme toplamında aynı (i, toplam) çifti farklı yollardan birden çok kez oluşabilir. Örneğin {1, 2, 3, 4} kümesinde ilk dört karardan sonra {1, 4} ve {2, 3} seçimleri aynı toplamı, 5'i verir. Geri izleme bu çifti her seferinde baştan çözer. Dinamik programlama ise sonucu tabloda saklar. Hedef küçükse dinamik programlama O(n · HEDEF) sürede çalışır. Ama N vezir ya da Hamilton yolu gibi problemlerde alt problemi tanımlayan durum, kullanılmış sütunların ya da ziyaret edilmiş düğümlerin kümesidir. Bu kümelerin sayısı üsteldir ve tablo pratik olmaktan çıkar.

Özetle geri izleme, durum uzayı ağacında derinlik öncelikli aramadır. Ağaç önceden kurulmaz; gezilirken üretilir. Geçersiz dallar hiç üretilmez.

9.11Sık yapılan hatalar

Geri izleme kodları kısadır, ama küçük hatalar çok farklı sonuçlar doğurur. Aşağıdaki hataların her biri notun bir yerinde ayrıntılı ele alınmıştır.

9.12Özet

• Zor problemler: P polinom sürede çözülen, NP polinom sürede doğrulanan karar problemleridir. NP-tam problemler hem NP'de hem NP-zordur. P ≠ NP ise bu problemlerin polinom zamanlı kesin algoritması yoktur; kesin çözüm için budamalı üstel arama gerekir.
• Fikir: çözüm adım adım bir kısmi çözüm olarak kurulur. Bir aday kısıtı bozarsa o dal terk edilir; bir adımda aday kalmazsa son karar geri alınır ve sıradaki aday denenir. Geçersiz kısmi çözümlerin devamı hiç üretilmez.
• Şablon: hedef testi, ardından her aday için: geçerliyse seç, özyinele, geri al. Tek çözüm için boolean döndürülür ve true yukarı iletilir; bütün çözümler için hedefte sayılıp false döndürülür.
• Durum uzayı ağacı: kısmi çözümler düğüm, seçimler kenardır. Geri izleme bu ağaçta derinlik öncelikli aramadır; ağaç gezilirken üretilir ve budama geçersiz alt ağaçları atlar.
• N vezir: vezirler satır satır konur; sütun ve iki çapraz denetlenir. 4 vezirde ilk çözüm [1, 3, 0, 2] (8 yerleştirme, 4 geri dönüş); 8 vezirde 92 çözüm, ilk çözüm [0, 4, 7, 5, 2, 6, 1, 3] (113 yerleştirme, 105 geri dönüş). Bayraklarla (r + c, r − c + n − 1) güvenlik testi O(1) olur.
• En az çakışma: tam bir yerleşimden başlanır, çakışan bir vezir en az çakışmalı satıra taşınır. Hızlıdır ama tam değildir: platolarda dolaşabilir ve çözüm olmadığını kanıtlayamaz.
• Sudoku: boş hücreye 1–9 denenir; satır, sütun ve kutu denetlenir. Satır satır sırada örnek bulmaca 4208 yerleştirme ve 4157 geri alma ister; MRV ile 51 yerleştirme, 0 geri alma.
• Öteki uygulamalar: çizge boyama (renk kısıtı, O(n · mⁿ)), Hamilton yolu ve döngüsü (komşuluk ve tekrar kısıtı, O(n · n!)), kelime arama (ziyaret işaretinin geri alınması, O(R · C · 3^L)), alt küme toplamı (al/alma ikili ağacı, fazla ve eksik toplam budaması).
• Maliyet: zaman, gezilen düğüm sayısı ile düğüm başına işin çarpımıdır; en kötü durum üsteldir (2ⁿ, n!, 9^m). Bellek yalnız O(derinlik)'tir. Değişken ve değer sıralaması, ileri denetim, hızlı kısıt testi ve simetri kırma gezilen ağacı küçültür.

9.13Kavram listesi

• geri izleme backtracking
• kısmi çözüm partial solution
• budama pruning
• durum uzayı ağacı state-space tree
• kaba kuvvet brute force
• derinlik öncelikli arama depth-first search (DFS)
• karar problemi decision problem
• polinom zaman polynomial time
• indirgeme reduction
• NP-zor NP-hard
• NP-tam NP-complete
• N vezir problemi N-queens problem
• en az çakışma sezgiseli min-conflicts heuristic
• yerel arama local search
• sezgisel heuristic
• kısıt sağlama problemi constraint satisfaction problem
• MRV minimum remaining values
• ileri denetim forward checking
• çizge boyama graph coloring
• Hamilton yolu Hamiltonian path
• alt küme toplamı subset sum
• sözlüksel sıra lexicographic order
• dal sınır branch and bound

9.14Kendini Dene

1. Permütasyon kodu permutasyon(new int[4], new boolean[5], 0) ile çağrılıyor. Yazdırılan 7. permütasyon hangisidir? Arama boyunca kaç kez “seç” yapılır?

   Cevap

   Permütasyonlar sözlüksel sırada çıkar: [1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2] ve 7. olarak [2, 1, 3, 4]. Seç sayısı ağacın kök dışı düğüm sayısıdır: 4 + 12 + 24 + 24 = 64.

2. Dört öğeli bir kümenin alt kümelerini “al / alma” kararlarıyla üreten aramanın durum uzayı ağacında kök dahil kaç düğüm ve kaç yaprak vardır?

   Cevap

   Her seviyede düğüm sayısı ikiye katlanır: 1 + 2 + 4 + 8 + 16 = 31 düğüm. Yaprak sayısı 2⁴ = 16'dır; her yaprak bir alt kümedir.

3. n = 4 için bayraklı sürümde vezirler (0, 1) ve (1, 3) karelerindedir. Hangi sut, k1 ve k2 hücreleri true'dur? (2, 0) ve (2, 2) kareleri güvenli midir?

   Cevap

   sut[1], sut[3]; k1[1], k1[4]; k2[0 − 1 + 3] = k2[2], k2[1 − 3 + 3] = k2[1]. (2, 0) için sut[0], k1[2] ve k2[5] boştur: güvenli. (2, 2) için k1[4] doludur: (1, 3) ile aynı ters köşegendedir, güvenli değildir.

4. n = 6 için coz(t, 0) ilk çözümü bulana kadar 31 vezir yerleştirir. Kaç geri alma yapılır? Neden ilk çözüm sütun 0 ile başlamaz?

   Cevap

   Her yerleştirme ya geri alınır ya da çözümde kalır; çözümde 6 vezir vardır. 31 − 6 = 25 geri alma yapılır. 6 vezir probleminin dört çözümünün hiçbiri 0. satırda sütun 0'ı kullanmaz. Sütun 0 ile başlayan bütün dallar çıkmaza girer ve sözlüksel ilk çözüm [1, 3, 5, 0, 2, 4] olur.

5. 4 × 4 tahtada yer = [1, 3, 0, 0]'dır (yer[k], k. sütundaki vezirin satırı). Onarım için sütun 2 seçiliyor. Bu vezirin satır 0–3 için çakışma sayıları nedir? En küçük değerli satıra taşınması sorunu çözer mi?

   Cevap

   Sayılar 1, 2, 1, 2'dir. Satır 0 vezirin şimdiki yeridir (sütun 3 ile aynı satır). Satır 2 de 1 çakışmalıdır: (3, 1) ile aynı çaprazdadır. Vezir satır 2'ye taşınırsa yer = [1, 3, 2, 0] olur ve bu kez sütun 1 ile sütun 2 çakışır; çakışan çift sayısı yine 1'dir. Bu bir platodur. Sütun 3 seçilseydi sayılar 1, 3, 0, 1 olurdu ve vezir satır 2'ye taşınarak çözüm [1, 3, 0, 2] bulunurdu.

6. Örnek Sudoku bulmacasında (4, 7) hücresinin kutusu hangi satır ve sütunları kapsar? Başlangıçta bu hücrenin adayları nelerdir?

   Cevap

   4 / 3 · 3 = 3, 7 / 3 · 3 = 6: kutu 3–5. satırlar ve 6–8. sütunlardır. Satır 4'te 4, 8, 3, 1; sütun 7'de 6, 8, 7; kutuda 3, 1, 6 vardır. Kullanılmayan rakamlar 2, 5 ve 9'dur. Çözümde hücreye 9 yazılır.

7. Kenarları 0–1, 1–2, 2–0 ve 2–3 olan çizge boya(0) ile m = 2 ve m = 3 renkle boyanıyor. Sonuçlar nedir?

   Cevap

   0, 1, 2 düğümleri bir üçgendir; üçü de birbirine komşudur ve iki renk yetmez. m = 2 için arama bütün ağacı gezer ve false döner. m = 3 için ilk denemede [1, 2, 3, 1] bulunur: düğüm 3'ün tek komşusu 2'dir (renk 3), bu yüzden renk 1 uygundur.

8. Düğüm 0 merkezde, 1, 2 ve 3 yalnız merkeze bağlı olan yıldız çizgede bul(graf, yol, 1) ne döndürür? Başka bir başlangıç düğümü sonucu değiştirir mi?

   Cevap

   false. 0'dan 1'e gidilince 1'in yolda olmayan komşusu kalmaz; 2 ve 3 için de aynısı olur. Başlangıç değiştirmek de işe yaramaz: bir yolda en çok iki uç düğüm vardır, ama bu çizgede derecesi 1 olan üç düğüm vardır. Hamilton yolu yoktur.

9. ABCE / SFCS / ADEE ızgarasında “ASFB” ve “ECE” kelimeleri var mıdır?

   Cevap

   “ASFB” vardır: (0, 0) A → (1, 0) S → (1, 1) F → (0, 1) B. “ECE” yoktur. C harfi (0, 2) ve (1, 2)'dedir. (0, 2)'nin E komşusu yalnız (0, 3)'tür; o da yolun başında kullanılmıştır. (1, 2)'nin E komşusu yalnız (2, 2)'dir; yol oradan başlarsa ikinci E için başka komşu kalmaz. Her iki durumda da bir E hücresi iki kez kullanılmak zorunda kalır.

10. a = {2, 4, 5, 9} ve hedef 13 için alt küme toplamı araması (önce “al” dalı) hangi alt kümeyi bulur? Kalan-toplam budaması eklenirse çağrı sayısı nasıl değişir?

    Cevap

    2 ile başlayan bütün dallar başarısız olur: 2 + 4 + 5 = 11, 9 eklenince 20; 2 + 4 + 9 = 15; 2 + 5 + 9 = 16; 2 + 9 = 11. Ardından 2 bırakılır ve 4 alınır. 4 + 5 = 9'a 9 eklenince 18 olur ve dal budanır. 5 bırakılıp 9 alınınca 4 + 9 = 13 bulunur. Sonuç {4, 9}'dur. Budamasız kod 23, kalan-toplam budamalı kod 21 çağrı yapar; kazanç küçüktür, çünkü toplamların çoğu hedefi aşarak zaten budanır.

9.15İleri okuma

• A. Levitin, Introduction to the Design and Analysis of Algorithms, 3. baskı, 12. bölüm: geri izleme ile dal sınırı aynı çerçevede anlatır. N vezir, Hamilton döngüsü ve alt küme toplamı örneklerini çözer.
• S. Russell ve P. Norvig, Artificial Intelligence: A Modern Approach, 4. baskı, 6. bölüm: kısıt sağlama problemlerini, MRV, ileri denetim ve en az çakışma sezgiselini ayrıntılı ele alır.
• D. E. Knuth, The Art of Computer Programming, Cilt 4B: geri izleme programlamasının tarihini, maliyet tahmini yöntemlerini ve “dancing links” tekniğini verir.
• S. W. Golomb ve L. D. Baumert, “Backtrack Programming” (1965): yöntemi genel bir programlama tekniği olarak tanımlayan ilk makalelerden biridir.

9.16Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. A. Levitin, Introduction to the Design and Analysis of Algorithms, 3. baskı, Pearson, 2012 (12. bölüm: Backtracking).
3. S. Russell ve P. Norvig, Artificial Intelligence: A Modern Approach, 4. baskı, 2020 (6. bölüm: kısıt sağlama, en az çakışma).
4. S. Minton, M. D. Johnston, A. B. Philips ve P. Laird, “Minimizing Conflicts: A Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems”, Artificial Intelligence 58, 1992.
5. D. E. Knuth, The Art of Computer Programming, Cilt 4B, Addison-Wesley, 2022 (Backtrack programming, Dancing Links).
6. S. W. Golomb ve L. D. Baumert, “Backtrack Programming”, Journal of the ACM 12(4), 516–524, 1965.
7. S. A. Cook, “The Complexity of Theorem-Proving Procedures”, Proceedings of the 3rd ACM Symposium on Theory of Computing (STOC), 151–158, 1971.