Algoritmaların Tasarımı ve Analizi #07 | Geri İzleme ve Karar Ağacı

Eğitmen: Dr. Süleyman Burak ÇELİK

Geçen derste özyineleme ağacını bütün çağrıların maliyetini toplamak için kullandık. Bugün ağaçtaki dallar, verebileceğimiz farklı kararları gösterecek. Bir kararı deneyecek, devamının çözüm getirip getirmediğine bakacak ve gerekirse geri dönerek başka kararı deneyeceğiz. Bir seçimi dene, gerekirse geri dön. Algoritmaların çalışma adımlarını gerçek konuşmayla eşleşen şemalar ve özgün örneklerle adım adım inceliyoruz. Bu derste: 1. İki dal bütün olasılıkları kapsar 2. Üç durma kuralını sırayla kontrol et 3. Önce 4 alınan dalı deneyelim 4. 7 alınmayan dal da 4 seçimini kurtaramaz 5. 4 alınmayınca çözüm yolu açılır 6. Geri dönüşte durum doğru kalmalı 7. Hiçbir geçerli çözümü atlamadık mı? 8. Aynı düşünce başka problemlerde de var 9. Siz deneyin: hedef 7 ve hedef 6 Bölümler: 0:00 Bir karar tutmazsa geri dön 0:51 Alt küme toplamı: 4, 7, 3 ile hedef 10 1:40 İki dal bütün olasılıkları kapsar 2:25 Üç durma kuralını sırayla kontrol et 3:11 Önce 4 alınan dalı deneyelim 3:56 7 alınmayan dal da 4 seçimini kurtaramaz 4:38 4 alınmayınca çözüm yolu açılır 5:20 Geri dönüşte durum doğru kalmalı 6:09 Hiçbir geçerli çözümü atlamadık mı? 7:04 Aynı düşünce başka problemlerde de var 7:56 Siz deneyin: hedef 7 ve hedef 6 8:49 Sistemli arama yine de pahalı olabilir 9:40 Seç, gerekçeyle kes, geri dön Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §2.1–2.4. Kavram ve konu sırası kaynak kitaptan izlenir; anlatım, şemalar ve sayısal örnekler özgündür. Ekrandaki sayılar açık varsayımlı öğretim modelleridir; gerçek cihaz ölçümü değildir. Kitap: https://jeffe.cs.illinois.edu/teaching/algorithms/ (yasal ve ücretsiz kaynak). Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.