MIT Açık Ders malzemeleri

http://ocw.mit.edu

 

6.046J Algoritmalara Giriş, Güz 2005

 

Bu materyallerden alıntı yapmak veya kullanım şartları hakkında bilgi almak için:

 

Erik Demaine ve Charles Leiserson, 6.046J IntroductiontoAlgorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi:  08, 01, 2010).                                                      Lisans: Creative CommonsAttribution-Noncommercial-ShareAlike.

Not: Lütfen atıf taparken bilgilere eriştiğiniz gerçek tarihi kullanınız.

Atıflar ve Kullanım Koşulları konusunda daha fazla bilgi için:

http://ocw.mit.edu/terms ve http://www.acikders.org.tr sitesini ziyaret ediniz.

DERS 18

                                                                                                                                                                                 Hepinize Günaydın. Erken ve aydınlık bir saatte hepinizi burada görmekten mutluyum. Araştırma Görevlilerinin sayısının öğrencilerinkini geçeceği günleri sayıyorum. Bir gün bu olacak. Tanıdık bir hikayeye geri  dönüyoruz. Bu Yıldız Savaşları / İkinci Bölüm Empire Strikes Back. Son defa, rakibimiz, “grafik” bir problem ile karşımıza çıkmıştı. Bir kaynağımız vardı, yönlendirilmiş bir grafiğimiz ve kenarların üzerinde ağırlıklar vardı ve hiçbiri de negatif değillerdi. Ve mutluluk hüküm sürüyordu. Ve Dijkstra’nın algoritmasını tasarımlayarak, tek kaynaklı enkısa yollarda, s ‘ den diğer her köşeye enkısa yol ağırlığını en etkin şekilde bularak, İmparatorluğa karşı galip gelmiştik.

Bugün ise, Ölüm Yıldızı arşivinden bize yeni bir şaşırtıcı oyun çıkarıyor: Potensiyel olarak, negatif ağırlıklarımız var. Ve özellikle negatif ağırlık çevrimleri ile bir şekilde uğraşmak zorunda kalacağız. Ve bir negatif ağırlık çevrimimiz olduğunda, ortalıkta tekrar, tekrar ve tekrar dolaşabildiğimizi ve zaman içinde de gittikçe daha gerilere gidebildiğimizi görmüştük. Ve geçmişte canımızın istediği kadar geri gidebiliyoruz. Ve bu nedenle enkısa yol diye birşey olmuyor, çünkü hangi yolu alırsanız ondan daha kısasını elde edebiliyorsunuz. Böylece bugün bu konuyu işlerken, Dijkstra kadar hızlı olmayan ama ondan daha basit olan, Bellman – Ford adlı yeni bir algoritmayı göreceğiz.

Bu yeni algoritma, negatif ağırlıklara izin veriyor ve ümit ettiğiniz kadar çok sayıda olmamakla birlikte, bir anlamda negatif ağırlık çevrimlerine de yer veriyor. Bu nedenle şüphesiz devamı için de yer ayırmamız gerekiyor. Pekala, tahmin edeceğiniz gibi, Bellman-Ford algoritması iki kişi tarafından keşfedilmiş bir algoritma olup, enkısa yol ağırlıklarını hesaplıyor. Ama ağırlıklar hakkında herhangi varsayımda bulunmuyor. Ağırlıklar tamamen rastgele ve enkısa yol ağırlıklarını hesaplıyor. Şu simgelemi unutmayın:  Delta (s, v),  s’den v’ye enkısa yol ağırlığıdır. s’ye kaynak köşesi deniliyordu.

Ve böylece, küçük v olarak adlandıracağımız tüm köşeler için ağırlıkları hesaplamak istiyoruz. Buradaki iddiaya göre, s’den heryere hesaplama yapmak, s’den belli bir yere  hesaplamaktan daha  güç değildir. Öyleyse, hesaplamayı hepsi için yapacağız. Durum burada da aynı  olacak. Ve negatif ağırlıklara izin veriyor. Ve bu da iyi bir durum ama bir alternatif de var, o da Bellman-Ford, “Dikkat!  bir negatif ağırlık çevrimi var” diyebilir.

Öyle bir durumda bunu söyleyecektir. Demek ki negatif ağırlık çevrimi var denilebiliyor. Bu sebeple bu deltalardan bazıları eksi sonsuz’dur. Ve bu biraz garip görünüyor. Böylece, bugün tanıtacağımız Bellman-Ford bu durum için, ama negatif ağırlık çevrimleri yok; dolayısıyla daha fazla sezgisel. Onlara izin veriyor gibi görünmekle birlikte onları rapor ediyor. Bu durumda size delta değerleri vermeyecek. Delta değerleri almak için algoritmayı değiştirebilirsiniz ama, biz burada bunu görmeyeceğiz. Böylece algoritmayı gördükten sonra, egzersizde, “bu deltaları bütün durumlar için  hesaplayın.” denilecek. Aslında yapılması güç değil. Ancak onun için burada zamanımız yok. 

Algoritma şu.  Anlaşılması bayağı kolay.. Söylediğim gibi, Dijksrtra’dan daha kolay. Bir gevşetme algoritması. Yaptığı ana şey Dijkstra gibi kenarları gevşetmek. Bu nedenle, Dijkstra’dan çıkan birçok önkuramı burada kullanabileceğiz. Doğruluğunun ispalanmasına gelince, üç kez daha kısa, çünkü üçte ikisini zaten Dijkstra’dan biliyoruz. Korkarım, biraz fazla ileriye atlıyorum. Böylece, birinci kısım ilklendirme. Gene, d[v], s’den v’ye tahmin edilen uzaklığı temsil edecek.

Algoritma yol alırken biz de bu tahminleri güncelleyeceğiz. Ve başlangıçta, d[s]  sıfır; ancak muhtemelen ileride bu doğru cevap olmayabilir. Bunun dışında her şey sonsuz ve tabii ki bu bir üst sınırdır. Bunların her ikisi de gerçek uzaklık üzerinde üst sınırlardır. Buraya kadar iyi.. Bu önceden yaptığımız gibi ilklendirme.. Ve şimdi  v eksi bir kez tekrarlayan bir ana döngümüz var. i dizinini  kullanmayacağız. O sadece bir sayaç.

Ve her kenara bakacağız ve onları gevşeteceğiz. Çok basit bir fikir. Eğer gevşetmeyi öğrenirseniz deneyebileceğiniz ilk şey bu olur. Soru ne zaman duracağımız. Yani şöyle birşey: Bir arkadaşım vardı, altı yaşındayken, durmadan “banana  kelimesini nasıl  heceleyeceğimi biliyorum ama ne zaman duracağımı bir türlü bilmiyorum.” derdi.  Aynı durum gevşetmede söz konusu.  Önceki gibi gevşetme adımımız bu. Kenara bakıyoruz; bilinen tahminlerimize göre üçgen eşitsizliğini ihlal edip etmediğini görüyoruz; s‘ den v‘ ye uzaklığın, azami s’den u’ya, artı o kenarın u‘ dan v’ ye olan ağırlığı kadar olduğunu biliyoruz. Eğer eşit değilse, eşitliyoruz. Bunun her zaman yapılabilecek bir işlem olduğunu kanıtlamıştık.

Biz asla ihlal etmiyoruz, yani eğer birçok dengeye dönme işlemi yapsak bile, şu d[v]’ler hiç küçülmez. Böylece temel fikir olarak her kenarı alırsınız, gevşetip dengeye döndürürsünüz. Hangi düzende olduğuna aldırmıyorum. Sadece gevşetin,her kenarı ve her defasında sadece bir tanesini. Bunu V eksi bir kere  yaparsınız. Bunun anlamı, eğer negatif  ağırlık çevrimleriniz yoksa bu miktar yeterlidir. Yani eğer negatif ağırlıklı çevrim varsa, bunu hesaplamamız gerekir. Bunu oldukça doğrudan bir yolla yapacağız, yani tamamen aynı şeyi yapacağız. Böylece bu, buradaki döngünün dışında. Grafiğimizde her kenar için benzer dört döngümüz olacak.Gevşetmeye çalışacağız. Gevşetebilirseniz bu sava göre bir negatif ağırlık çevrimi var demektir.

Böylece ispat gerektiren ana şey bu. Pekala, algoritma bu. Sava göre, uçlarda d[v] olması lazım – Bakalım buraya “else” yazmamız gerek.. d[v] eşittir Delta (s, v),  tüm v köşeleri için.. Eğer bu kurala göre bir negatif ağırlık çevrimi bulamıyorsak, tüm enkısa yol ağırlıklarımızı elde etmiş olmamız gerekir.. Sav yada iddia bu. Şimdi ilk soru, buradaki koşma süresinin çözümlemesi çok kolay. Öyleyse, koşma süresi ile başlayalım. Şuradaki Dijkstra ile karşılaştırabiliriz.

Bu algoritmanın koşma süresi nedir?  V çarpı E, kesinlikle. Mantıklı olacağı için, V ile E nin her ikisinin de pozitif olduklarını varsayacağım. Böylece bu V çarpı E dir. Yani bu Dijkstra’dan biraz daha yavaş, hatta oldukça yavaştır. İşte orada. E artı V log V, aslında log’ları unutursak bayağı doğrusal zamanlı olur. Grafiğin bağlantılı olduğunu varsayarsak,  burada en azından V’de karesel  bir şeyimiz var. Yani daha yavaş ama bu negatif ağırlıkları da işleyecek. Dijkstra ise negatif ağırlıklarla hiçbir şekilde işlem yapamaz. Böylece, bu algoritmanın çalışacağını neden bekleyebileceğimizi göstermek için bir örnek yapalım.

Ondan sonra da tabii ki çalıştığını ispatlayacağız. Ancak ispatı çok kolay olacak. Buraya negatif ağırlıkları olan, ama negatif ağırlık çevrimleri olmayan ve ilginç bir yanıt elde edeceğim bir grafik çizeceğim. İyi. Bu algoritmanın çıkışını iyi tanımlanmış kılmak için  gerek duyduğum diğer şey, bunun kenarlarını ziyaret ettiğim düzendir. Bu nedenle  bu kenarlara tamamen keyfime göre rastgele bir düzen vereceğim. Sizlerden bir düzen isteyebilirdim ancak, notlarımla uyumlu olması için düzenlemeleri ben yapacağım. Şuna dört sayısını verip, ziyaret edeceğim dördüncü kenar diyelim. Fark etmez. Ama belli bir grafik için algoritma sırasında ne olacağını etkileyecektir.

Hepsini yazdım mı? Bir, iki, üç, dört, beş, altı, yedi, sekiz, tamam. Ve benim kaynağım A olacak. Ve işte bu. Şimdi bu algoritmayı çalıştırmak istıyorum. Herşeyi ilklendirmeye başlayacağım.Tahminleri  s için sıfır, diğer tüm şeyler için de sonsuz olarak saptıyorum. Ve bir zaman kavramı oluşturmak için, algoritma ilerledikçe ağırlıkların yani “d” değerlerinin ne olduklarını buraya çizeceğim veya yazacağım; çünkü arada iptal edeceğim ve tekrar yeniden yazacağım için biraz karışık hale gelecekler.  Ancak, izini burada takip edebileceğiz. Başlangıçta sıfır ve sonsuzlar. Evet?

Fark etmez. Böylece algoritmada kenarlara her defasında isterseniz değişik bir sıra içinde gidebilirsiniz. Bunu ispatlayacağız ama ben, her seferinde aynı düzen ve sıra içinde gideceğim. İyi soruydu. Ama burada önemli olmayacak. Pekala işte burası başlangıç noktası.  Şimdi her kenarı gevşeteceğim. Bunun sonucu burada hiçbirşey yapmayan bir sürü kenar olacak.  Eksi bir kenarını gevşetmeye çalışıyorum. Kendi kendime, “s den B ye, sonsuz ağırlıkla nasıl varıldığını biliyorum.” diyorum.

Sonsuz artı iki ile, s’den E ye varabiliyorum. Sonsuz artı iki sonsuzdan çok daha iyi değil. Tamam bu nedenle herhangi birşey yapmıyorum, bunu sonsuza güncellemiyorum.  Demek istediğim, sonsuz artı iki kulağa daha da kötü geliyor. Ama sonsuz artı iki, sonsuzdur.   Böylece bu kenar bir oluyor. Ve bu gevşetme yapılmamış  kenar iki;  aynı uğraş, kenar üç;  aynı uğraş kenar dört;  yavaş yavaş enteresan birşey elde etmeye başlıyoruz. Burada A dan B ye, toplam ağırlık olan eksi biri kullanarak varabileceğim sınırlı bir değer var.

Bu iyi haber. Buraya eksi bir yazacağım ve B yi eksi bire güncelleyeceğim.  Gerisi aynı kalacak. Böylece bunu tekrar tekrar yapacağım. O dördüncü kenardı. Beşinci kenarda da bir gevşetme elde ediyoruz. Dört sonsuzdan iyidir.  Böylece C  dört sayısını alıyor.  Sonra  kenar altıya varıyoruz. O sonsuz artı beş, dörtten kötüdür. Pekala orada gevşetme yok.  Kenar yedi, enteresan çünkü, burada da saptanmış sonsuz olmayan bir değer var:  eksi bir artı bu kenarın ağırlığı yani üç. Bu toplamda iki ediyor, ki bu da aslında dörtten iyi. Böylece buradaki yol, A – B - C, gerçekte bir saniye evvel bulduğum yoldan daha iyi. Böylece buna iki sayısını veriyorum. Bütün bunlar ana döngünün birinci turunda oluyor.

Aslında C’ye iki yol bulduk.  Biri diğerinden daha iyi.. Tamam, o yedi sayılı kenar idi. Sekiz sayılı kenar burada. O fark etmez. Bu döngünün ilk turu bu idi, yani i’nin ilk değeri. i eşit 1.  Pekala şimdi devam ediyoruz; ve devam edelim. Böylece bir sayılı kenar ile başlıyoruz.  Şimdi, eksi bir artı iki bir olur. Bu da sonsuzdan iyi.  Hızlanmaya başlayacak. Aynı zamanda tekrarlayan nitelikte. Bitirmemiz  fazla sürmeyecek. Numara iki, bu sonsuz onun için birşey yapmıyoruz. Numara üç, eksi bir artı iki, bir eder ve bu sonsuzdan iyidir. Bu D köşesi ve sayısı üç. Numara dört, onu zaten yaptık.

Hiçbir şey değişmedi. Beş numara:  burada tekrar dört sayılı yolu görüyoruz, fakat ikiden kötü.  Bu sebeple, herhangi bir şeyi  güncellemiyoruz.  Numara altı: bir artı beş, altı eder, bu ikiden büyük, yani iyi değil. Bu taraftan gidelim. Numara yedi: aynı durum. Numara sekiz: bu ilginç. Böylece burada birin ağırlığı ve eksi üçün ağırlığı var. Toplam eksi iki yapıyor ki bu birden iyi. Bu D idi. Ve-- sanırım hepsi bu kadar. Bu da o turun sonu oluyor. Bu i eşit 2, çünkü sekizinci kenara demin bakmıştık.. Burada hile yapacağım ve kontrol edeceğim. Gerçekten o sonuncu şeydi..

D’den dışarı çıkan kenarlardan birkaçını kontrol edebiliriz, çünkü sadece D’ nin değeri değişti ve başka gevşetme yada dengeye dönme işlemi mümkün değil. Demek ki iki turda, en kısa yol ağırlıklarının hepsini elde ettiğimizi iddia edebiliriz. Algoritma doğruluğu garanti etmek için pratikte dört döngü yapacak, çünkü burada beş köşemiz var ve bundan bir eksiğini yapmalı. Yani aslında uygulama aşamasında, burada alt kısımda iki tane daha boş tur var. Orada hiçbir şey olmaz, ama boş verin yapsın.

Özetle Bellman–Ford bu. Demek istediğim, şüphesiz yanlış bir şey yapmıyor. Buradaki soru, negatif ağırlık çevrimler olmadığı sürece, V eksi bir adımda yakınsama neden garanti ediliyor? Bir soru mu var? Doğru, öyleyse bu bir eniyileme, yani optimizasyondur. Eğer bir tam tur keşfederseniz ve hiçbir şey olmazsa, onun izini algoritmanın içinde takip eder ve durabilirsiniz. En kötü ihtimalle bir değişiklik yapmayacaktır. Fakat pratikte belki onu yapmak isteyeceksiniz. İyi sualdi. Tamam, bazı basit gözlemler yani sadece gevşetme yapıyoruz demek istiyorum. Öyle ise, daha önceki çözümlemelerimizin çoğunu kullanabiliriz. Özellikle d değerleri monoton bir şekilde sadece azalıyor. Burada, değerleri iptal ederken, onları daima daha küçültüyoruz ki, bu iyi bir şey. Bu algoritmanın hoş taraflarından bir diğeri de, onu dağıtımlı bir sistemde bile uygulayabilirsiniz.

Eğer bu gerçek bir ağ, belli sayıda bilgisayar içeren bir ağ ise ve bunlar makineler,  bu hatlar ile haberleşiyorlarsa, tamamen yerel bir şey demek istiyorum.--Gevşetme yerel bir şeydir. Her hangi bir global stratejiye ihtiyacınız olmaz ve siz, “her adımda farklı bir düzen yapabilir miyiz?” diye sorarsınız.  Evet, kenarları gevşetmeye, tekrar gevşetmeye devam edebilir ve bunu ağın ömrü süresince sürdürebilirsiniz. Ve en sonunda en kısa yolları bulursunuz. Böylece bu algoritma dağıtımlı bir sistemde, V turda işi bitirmeyi garanti ediyor. Daha fazla asenkron olabilir ve o takdirde çözümlemesi de daha güçtür.

Ama sonunda gene çalışacaktır. Yakınsama için garantilidir. Bu nedenle Bellman-Ford, internette en kısa yolları bulmak için çok kullanılmaktadır. Pekala, şimdi son olarak çalıştığını ispatlayalım. Bu sadece birkaç tahta dolduracaktır. Demek ki, bir grafiğimiz olduğunu ve negatif ağırlık çevrimleri olmayan belli kenar ağırlıkları olduğunu farz ediyoruz. Sonra iddiaya göre, doğru yanıt ile bitiriyoruz. Öyle ise Bellman-Ford,  her bir köşe için delta değerlerine ayarlanmış tüm bu d[v] değerlerini sona erdiriyor.

Kanıtlaması çok hızlı olacak -- eğer daha önceki önkuramları kullanmak yoluyla yapmayı hatırlıyorsanız.. Burada her köşeye ayrı ayrı bakacağız.  Buna köşe v adını veriyorum. İddiaya göre, bu algoritmanın sonunda da geçerli olacak. Unutmayın, ispat etmemiz gereken şey, belli bir noktada d[v] eşittir Delta (s, v) olduğu; çünkü monoton bir şekilde azaldığını, ama asla doğru değerinden daha küçük olmadığını biliyoruz, çünkü gevşetmeler, daima güvenlidirler.

Öyleyse, göstermemiz gereken belli bir noktada bunun geçerli olduğu ve en sonunda da geçerli olacağı. Yani, d değerlerin monotonluğu ve Doğruluk bir’i kullanarak -- ki bu  d[v]’lerin daima Deltalara büyük – eşit olduğuydu, göstermemiz gereken bir noktada bir eşitliğin olduğu. Hedefimiz bu. Böylece yapacağımız sadece v’ye bakmak ve v’ye gelen en kısa yola bakmak ve algoritmada bu yolun üstünde neler olduğunu görmek.                                                                                 

Bu amaçla, yola bir isim vereceğim. Küçük p diyelim. Köşe  da başlıyor ve , ’ye gidiyor ve ’da sona eriyor. Ayrıca, bu herhangi bir en kısa yol değil, s’de başlayan bir yol. Yani  yani s’de başlıyor ve v’de son buluyor. Bu yüzden, s ile v ye, daha belirgin bir biçimde  konuşabilmem için birkaç isim daha vereceğim. Böylece bu s’den v’ye bir en kısa yol. Şimdi sadece s’den v’ye herhangi bir en kısa yol olmasını istemiyorum – s’den v’ye olan en kısa yollar arasında, olabilecek en az kenarı olan bir en kısa yol olmasını da istiyorum.

Burada kullandığım  ‘’en kısa’’ kelimesi, yolun toplam ağırlığı cinsinden bir anlam taşır. Ağırlık açısından en kısa olmak yanında, kenar sayısı açısından da en kısa olmasını istedim. Bunun sebebi, p nin basit bir yol olmasını, başka bir deyimle aynı köşeden bir defadan fazla geçmeyen bir yol olmasını istemem. Şimdi, içinizde küçük p nin basit bir yol olmasını garantilemek için, neden kenar sayılarının da olabilecek en az sayıda olmasını varsaymaya ihtiyaç duyduğumu söyleyebilecek kimse var mı? 

İddiaya göre, en kısa yolların hepsi mutlaka basit değildir. Efendim?  Doğru. Bir sıfır ağırlık çevrimim olabilir. Bu nedenle teoremde, burada hiç negatif ağırlık çevrimi olmadığını umut ediyoruz. Ancak gene de sıfır ağırlık çevrimi olabilir. Sıfır ağırlık çevrimini, herhangi bir en kısa yolun ortasında bir yere koyabilir, böylece kendi arzunuza göre uzatabilir ve köşeleri defalarca tekrarlayabilirsiniz. O yol sıkıcı olur. O nedenle,  p basit olsun istiyorum.

Aslında kestirmeden giderek onu garanti edebilirim. Herhangi şekilde bir sıfır ağırlık çevrimi alırsam, onu atarım. Bu, bunun matematik yoldan yapılma şekillerinden bir tanesidir. Pekala, bu en kısa yol hakkında daha başka neler biliyoruz?   En kısa yolların içindeki alt-yolların da en kısa yollar olduklarını biliyoruz.  Bu en iyi alt-yapı. Başka, s’den ’ye olan en kısa yolun ne olduğunu tümevarımsal olarak biliyoruz. Demek istediğim, en kısa yol o yolun ağırlığı ki, özellikle, s’den V eksi bire, artı son kenarın ağırlığı, o da en iyi alt yapıda v eksi bir’den ’ye olan yol.

Bu, son olarak ispat etmiş olduğumuz en iyi alt-yapı nedeniyle oluyor. Pekala, bu kadarı ısınmak için fazla bile. Böylece, bir çeşit tümevarım ile bunu  i  içinde,  ile başlayıp, ’ye kadar giderek yapmak istiyorum. Bu durumda birinci soru, d[] , ki bu s’dir, Kaynağın d’si, nedir?  Doğal olarak algoritmanın başında bu sıfırdır. Başka bir anlatımla başlangıçta sıfıra eşittir, çünkü bu şekilde saptadık. Ve oradan sadece küçülür. Yani tabii ki azami sıfırdır.

Gerçek soru,  Delta (s virgül ) nedir?   s’den s’ye en kısa yol ağırlığı nedir?  Sıfır olması gerek, aksi takdirde bir negatif ağırlık çevriminiz olur -- kesinlikle. Benim en çok sevdiğim yanıt, sıfır. Böylece, eğer s’den s’ye bir yolumuz daha olsaydı, o bir çevrim olacaktı demek istiyorum.  Bu nedenledir ki mutlaka sıfır olması lazım. Buradan çıkan sonuç, demek ki bunlar algoritmanın başında gerçekten eşitler, ki bu da çok iyi bir sonuç.  Çünkü burada yukarda tartıştık, azalıyor ama asla çok fazla küçülemiyor. Bu nedenle, d[]’ı, doğru saptamış oluyoruz. Şahane:  tümevarımın taban şıkkı için iyi. Şüphesiz asıl ilgilendiğimiz v’lerden  olanı.. Yani tümevarımsal olarak hakkında  konuşalım ve sonra bir sonuç olarak ’yi elde edelim.

Evet, tümevarım ile yapalım. O daha eğlenceli.  d[]’nin algoritmanın “i’ninci” turundan sonra  Delta (s, )’ye eşit olduğunu söyleyelim.  Böylece bu gerçekte, burada algoritmanın içinde olan i ‘ye atıf yapıyor. Bunlar turlar. Böylece bir tur, tüm kenarların uygulanması, tüm kenarların gevşetilmesidir. Böylece bu, elbette i eşit sıfır için doğrudur. Sıfır  turdan sonra  algoritmanın başında, d[]  eşit, Delta (s, ) dır.

Pekala, bu tam benim istediğim değil ama, kabul edilebilir. Şimdi bunu d[