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 19                                                                                                        

 

--  --  en kısa yollar.    Bu son dersimiz. Umarım beklenmeye değer bir son olur. Kısa bir süre sonra bir Quiz  olacağını hatırlatırım, buna çalışıyor olmanız gerekir. Bu nedenle Quiz ile birlikte verilecek bir problem seti yok. Quiz evinize götürebileceğiniz bir sınav olacak. Ancak bunun için  Pazartesi  derse gelmeniz gerekli. Elbette ki, hepiniz geleceksiniz. Dersleri evlerinden izleyenler de, Quiz ‘ i almak için önümüzdeki  Pazartesi gelmeliler. Bu katılımı gerekli bir ders. Böylece, bugüne kadar olan üçleme konusunda  bir özet yapmaya gerek var. Böylece son iki ders, ilk iki bölüm, tek-kaynaklı-en-kısa-yollar üzerineydi.

Kaynak bir köşeden diğer köşelerin her birine en kısa yolu bulmak istiyorduk. Ve bu amaçla birkaç algoritma gördük. İşte kısa bir özetleme. Ağırlıksız durumda, ki bu hepsinin arasında bir çeşit en kolayı idi ve o örnekte bütün kenar ağırlıkları bir’di. O zaman “breadth first research” yani enine aramayı uygulayabildik. Ve bu, köşelerin sayıları ile kenarların sayılarının toplamından oluşan, grafik dünyasındaki adıyla, doğrusal –zaman’a mal oluyordu. İkinci en kolay hal, belki negatif olmayan kenar ağırlıkları‘dır. Böyle bir halde hangi algoritmayı kullanıyoruz?  Dijkstra, iyi,  herkes uyanık.

Aynı anda birkaç doğru cevap, muhteşem. Böylece bu, eğer iyi bir “heap structure” yani yığın yapısı kullanıyorsanız, yaklaşık doğrusal zamana mal oluyor, yani V log V artı E. Ve genellikle genel ağırlıklarda görmüş olduğunuz  Bellman-Ford ‘u kullanıyorduk. O da V, E‘ye mal oluyor, güzel.. Pekala, bu biraz daha kötü. Bu log faktörlerini hesaba almamak oluyor. Dijkstra temelde, doğrusal zamanlı, Bellman-Ford, eğer bağlantılı bir grafik varsa en az  karesel. Böylece E’nin V düzeyinde olduğu, seyrek halde bu doğrusal gibi. Bu karesel gibi. Yoğun durumda yani, E yaklaşık  olduğunda, bu karesel, bu da kübik.

Gördüğünüz gibi, Dijkstra ve Bellman-Ford, birbirlerinden bir V faktörü kadar farklıdırlar ve bu da oldukça kötüdür.  Ancak, tek kaynaklı en kısa yollarda, negatif kenar ağırlıklarının olduğu durumlarda bildiklerimizin en iyisi Bellman-Ford’ dur. Bu bağlamda etütte, DAG örneğini de görmüştük. Ve orada, ne yapıyordunuz? Topolojik sıralama, evet. Demek oluyor ki, köşeler açısından bir düzenleme elde etmek için topolojik bir sıralama yapabilirsiniz. Sonra Belllman-Ford’u bir tur çalıştırırsınız. Ne olup bittiği konusunda bir düşünme tarzı bu. Bellman-Ford’ u, topolojik sıralamanın verdiği düzen içersinde bir kere çalıştırarak bir doğrusal zamanlı algoritma elde edersiniz.

Yani DAG, ağırlıklarla dahi iyi bir uygulamanın nasıl yapılacağını bildiğimiz bir durum. Ağırlıksız halde de doğrusal zamanda yapabiliriz. Ancak çoğunlukla bu şekilde olur. Bu nedenle, Quiz için bunları aklınızda tutun. Quizde bir en kısa yol problemi gelirse veya sonunda karar verdiğiniz şey en-kısa-yol olduğu zaman, kullanacağınız en iyi algoritmanın hangisi olduğunu düşünün. Tamam, bunlar tek-kaynaklı-en-kısa-yol’lardır. Ölü Yıldız evrimimizde, başlangıçta sadece negatif olmayan kenar ağırlıkları vardı. Sonra, negatif kenar ağırlıklarımız oldu.

.                                                                                                                                          Bugün, Ölüm Yıldızı, “tüm-ikili-en-kısa-yollar” ile karşımıza çıkıyor ve biz her iki köşe arasındaki en kısa yolun ağırlığını bilmeyi istiyoruz. Pekala bazı çabuk sonuçlar elde edelim. Bu durum karşısında ne yapabiliriz? Yani mesela ağırlıksız bir grafiğim olduğunu farz edin. “Tüm-ikili-en-kısa-yolları” nasıl hesaplamalıyım?  Önerisi olan var mı? Her iki köşe arasında en kısa yol ağırlığını bilmek istiyorum. BFS, bir kaç çift söz daha.  

Efendim? Doğru.BFS kere V.. Pekala, ben V çarpı BFS diyeceğim,tamam mı? Böylece, koşma süresi,  artı V çarpı E olacak. Tabiatıyla bu grafiğinizin bağlantılı olduğunu varsayıyor. V çarpı E. Pekala, iyi. Bu,ağırlıksız grafikler için muhtemelen bildiğimiz en  iyi algoritmadır. Bunların pek çoğu bariz yanıtlar olacak.Tek kaynak algoritmanızı alıyorsunuz, V kere çalıştırıyorsunuz; yapabileceğiniz en iyi şey bu.—veya yapılışını en iyi bildiğimiz. Bu çok kötü değil. Bellman-Ford’un bir tur tekrarı gibi—karşılaştırma açısından.. En kısa yol ağırlığını hesaplayabilmemiz için kesinlikle, en az   gibi bir süreye ihtiyacımız var, çünkü çıkışın boyutu ; yani hesaplamanız gereken en kısa yol ağırlığı..

Demek ki bu mükemmel değil ama yine de iyi. Onun için daha da iyileştirmeye çalışmayacağız. Böylece negatif olmayan kenar ağırlıkları durumunda, --  yapılacak doğal şey, Dijkstra’yı V defa uygulamak; pekala, büyük bir sürpriz değil. Ve bunun koşma süresi de, gene V çarpı E, artı  log V, ki bu da çok fena değil. Bu BFS’yi  uygulamak ile aynı. Ve sonra bu log faktörü var. Eğer log faktörünü dikkate almazsanız, ağırlıklı terim budur. Demek istediğim, bunun bir de  ilave ’si var. Dolayısıyla, bunların her ikisi de bayağı iyi; yani düzgün. Aslında bunu çalıştırmanız, bir Bellman-Ford artı bir log faktörü zaman alıyor, ki eğer negatif olmayan kenar ağırlıklarınız varsa, bu sürede “tüm-ikili-en-kısa-yollar”ın hepsini hesaplayabilirsiniz.

Yani, tüm-ikilileri  tek-kaynak ile kıyaslarsak, sadece negatif olmayan kenar ağırlıklarını hesaplayabileceğimiz hususu hariç,  tüm-ikililer,  çok daha iyi demek istiyorum. Bu tamam, şimdi genel durum üzerinde düşünelim. Bugün tüm dikkatimizi üzerinde toplayacağımız konu bu ve gerçekten iyileştirme yapabileceğimiz yer de burası. Bildiğimiz tartışmasız şey, V çarpı Bellman- Ford’un,   çarpı E’ ye mal olduğu. Ve bu da çok üzücü bir değer, bu nedenle bu değeri, negatif olmayan kenar ağırlığı sınırına daha yakın bir değere iyileştirmeye çalışacağız. Burada gerçekten bir iyileştirme yapabileceğimiz anlaşılıyor, halbuki bu tip özel durumlarda çok daha iyisini yapamayız. Pekala, pek iyi bir öngörüm yok ama gerçek durum bu. Bu amaçla bu problemin çözümü için bugün üç algoritma göreceğiz.

Sonuncusu en iyisi olacak, ama yol boyunca en kısa yollar ve dinamik programlama arasındaki henüz görmediğimiz bazı güzel bağlantıları da göreceğiz.  En kısa yolları gördük ve hırslı algoritmaların uygulanmalarını yaptık, ama bugün fiilen dinamik programlama yapacağız. Sezgisel olarak tüm-ikili-en-kısa-yollar ‘da, alt-problemlerin tekrar kullanımları bağlamında daha fazla potansiyel var. Gerçekten, x’den y’ye en kısa yolu tüm x ve y değerleri için hesaplamak gerekiyor..Belki, o en kısa yolları başka en kısa yolları hesaplarken tekrar kullanabiliriz.                                                                                                                

Demek ki biraz daha fazla tekrar kullanım olacak, diyelim. Şimdi süratle tüm-ikili-en kısa yolları  resmen tanımlamak istiyorum, çünkü simgelemimizi biraz değiştireceğiz.  Bunu, tüm-ikililere önem verdiğimiz için yapıyoruz. Böylece giriş her zamanki gibi, yönlendirilmiş grafik oluyor, yani köşeler ve kenarlar var. Köşelerin kolaylık olsun diye “1’den n’ye ” şeklinde etiketlendirilmiş olduklarını söyleyeceğiz, çünkü tüm-ikililer durumunda bir anlamda daha iyi, “n x n” matris yapısını düşüneceğiz, çünkü artık komşuluk listeleri bağlamında düşünmenin bir faydası olmayacağından kenarların da önemi azalıyor.  Ve  hala  kenar ağırlıkları var. İlginç yönü de bu...

Bazıları negatif olacak. w kenarı bir gerçek sayıya eşlemliyor.  Ve hedef çıkış, en kısa yol matrisi oluyor. Böylece bu artık, “n x n” bir matris. Dolayısıyla n, en kısa ağırlıklı yollardaki köşelerin sayısıdır. Yani, Delta( i,  j ), i’den j’ye tüm ikililerin en kısa yol ağırlığıdır. Ve bunu da, n’ye n bir matrisle temsil edebilirsiniz.  Şimdi artık algoritma yapmaya başlayalım.

Elimizde, bu çok basit algoritma, V çarpı Bellman-Ford,  çarpı E var, sadece kıyaslama amacıyla,-- tekrar yazayım, V çarpı Bellman-Ford,  bize bu E koşma süresini veriyor; Şimdi grafiğin yoğun olduğu durumu düşüneceğim, yani köşelere giden kenarların sayısı karesel. O takdirde bu  süresini alacak ki, ki bu çok yavaş. Biz daha iyisini yapmak istiyoruz. Yani birinci hedefimiz  ’den daha iyi olmak.. V hiperküp yapmak, sanırım. Pekala bunu yapmak için dinamik programlama kullanacağız. Bu en azından motivasyonu sağlayacak. ’ni aşabilmemiz bir süre alacak, belki bir parça gereksiz de, ancak bazı zekice öngörüleri getirecek, diyelim.

Böylece şimdi bu grafik için biraz daha simgelem tanımlayacağım:  Önce ağırlıklı komşuluk matrisini düşünmeye başlayacağım. EK’te olmakla birlikte, bunu daha önce bir derste gördüğümüzü zannetmiyorum. Tanıma dönersek, normalde komşuluk matrisinde, eğer kenar varsa bir; yok ise sıfır görünür. Bu, bir digraph yani yönlendirilmiş grafik olduğundan, biraz dikkatli olmanız lazım. Buradaki bu değerler, matristeki girişler, kenarların ağırlıkları olacak.Tabiatıyla, bu da, “eğer ij bir kenar ise”,--

Yani, eğer ij, grafikteki bir kenar ise; --- ve eğer kenar yok ise sonsuz olacaktır. En kısa yolları açıklamakta bu grafik daha faydalı bir yoldur. Demek ki bu, buradan ihtiyacımız olan her şeyi içeriyor. Ve şimdi, onu sadece bir matris olarak düşünmeliyiz. Matrisler birazdan yararlı bir alet olacaklar. Pekala, şimdi bazı alt-problemleri tanımlayacağım. En kısa yol problemlerinde, ne olup bittiğini anlayabileceğiniz birbirinden farklı yollar vardır.

Pekala, doğal olarak, i köşesinden, j köşesine gitmek istiyorum.bEn kısa yol nedir? Fakat alt-problemleri bundan da daha iyi hale sokmanız gerekir. Hayret verici değil. Eğer benim Bellman-Ford’da yaptığım benzetmeyi düşünürseniz, Bellman-Ford’un yaptığı,  gittikçe daha uzun en-kısa-yollar kurmaktır. Ancak buradaki uzunluk, kenarların sayısı cinsinden.. Böylece önce bir 1 uzunluğunda en kısa yol yapıyor. Birinci turda bunu yaptığını kanıtladık.

İkinci turda tüm en kısa yolları bu kez 2uzunluğunda sağlıyor ve bu böyle devam ediyor. Şimdi biz de benzer yolla, yaklaşık aynı şeyleri, ancak, biraz daha fazla yeniden kullanarak yapmayı deneyeceğiz. Böylece,  üstsimge(m)’nin,  m ile ilgili belli bir kısıtlama koşulunda, en kısa yolun i’den j’ye olan ağırlığı olduğunu söyleyeceğim. Yani, i’den j’ye en kısa yol ama en çok m sayıda kenar kullanılacak.  Örneğin eğer m sıfır ise, uzunluğu sıfır olan en kısa yolları bulmak için çok fazla düşünmemiz gerekmeyecek. Onlar sıfır kenar kullanıyorlar demektir. Bellman-Ford, bize bir anlamda  m’den m artı bire nasıl gidileceğini söylüyor. Bu yolu hesaplayalım.

Bellman-Ford çözümlemesinden bildiğimiz bir şey, eğer  ‘e bakarsak, negatif ağırlık çevrimi olmadığı sürece, anlamlı en uzun  en-kısa-yol’ un, m’ nin, n eksi bire eşit olduğu zaman çıktığını bir bakıma biliyor olmamız; çünkü, elde edebileceğiniz en uzun basit yol odur. Yani, bu i‘den  j’ye en kısa yol ağırlığı oluyor ve üst simgeye daha büyük bir değer koymuş olsanız da bu durumu değiştirmiyor.  .

Eğer negatif ağırlık çevrimleri yoksa bunun Delta (i,  j) olması lazım. Bu dinamik programlamaya yatkın. Eğer, bütün m’ ler için bunu hesaplayabilirsek, bu bize yanıtı verecek. Sonra da özellikle en kısa yol ağırlıklarını elde edeceğiz. Bu arada negatif ağırlık çevrimlerini belirleme yoluna da ihtiyacımız var, ancak şimdilik bu konuda çok fazla endişelenmeyelim. Negatif ağırlıklar var ama şimdilik sadece negatif ağırlık çevrimleri olmadığını varsayalım.

Pekala, bir yineleme elde ediyoruz. Ve taban şıkkı da m eşit sıfır olduğu zaman. Bu çok kolay.  Aynı köşeler var, ağırlık sıfır ve aksi halde ağırlık sonsuz. Sonra  m için bir yineleme. Eğer doğru yazdıysam bu, için çok kolay sezinlenebilecek bir özyineleme;  n eksi bir cinsinden küçük şeylerin minimumu. Sadece resmini çizeceğim ve o zaman iddianın ispatı hemen anlaşılacak.. Bu resimle ispat. Demek ki, bir tarafta burada i var ve burada j var.  i’den j’ye en kısa yolu öğrenmek istiyoruz. Ve en çok m sayıda kenar kullanmak istiyoruz. 

Burada temel fikir, bir yere varabilmek için m eksi bir kenar kullanabileceğiniz olur. Öyleyse bu, en çok  m eksi bir kenardır, başka bir yerde buna k diyeceğiz. Böylece bu, şimdilik k’ye aday. Sonra da kenarı, doğrudan k’den j’ye kadar alabilirsiniz. Böylece bu, ’ye mal olur, bu da