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 ’e mal olur. Pekala, böylece, bu, i’den j’ye, en çok m sayıda kenar kullanan bir aday yol uzunluğudur. Ve bu temelde hepsini bir arada değerlendirmek olur. Demek ki dikkate aldığımız pek çok yol var. Bunların hepsi k olmaya aday.. Hepsini ara düğümler olarak, k olabilecekmiş gibi algılıyoruz. İşte hepsi oradalar. İçlerinden en iyi bir yolu alıyoruz. Bu aldığımızın tüm en kısa yolları içermesi lazım. Bu da tamamen olmasa bile aslında Bellman-Ford un yaptığı şey.. Bu arada, “ya doğrudan m eksi bir kenar ile gidersem ne olur?”, şeklinde de düşünmek isteyebilirsiniz.

Burada, ya kullanmak istediğim hiç kenar yoksa? Daima, kenarların bulunduklarını düşünüyoruz; A’nın tanımlanış şeklinde kendine saklanan bu sıfır ağırlıklı kenar vardır. Öyle ise, daha kısa bir yolu alabilir, ’den j ‘ye gidebilirsiniz ve j, k’ nin düşünülecek özel bir değeridir; ondan sonra da en sondaki sıfır ağırlıklı kenarı, ’ den alırsınız. Tamam, böylece bu gerçekten her şeyi kapsıyor.

Bu oldukça önemsiz bir iddia; anlaşıldı mı? Şimdi böyle bir özyineleme olduğunda, dinamik bir program elde etmiş oluruz. Bir anlamda işte bu. Özyinelemeli şekilde yazılmış, siz tersten yazabilirsiniz. Ben de onu biraz tersine çevirip yazmak istiyorum, çünkü öyle gözükmüyorsa da bu bir gevşetme, yada dengeye döndürme.. Bir tane daha gevşetme algoritması. Bu yüzden size vereceğim-- bu o türden bir algoritma. Pek ilginç bir algoritma da değil.

Eğer içinizden gelmiyorsa hepsini yazmanıza gerek yok. Belki kitapta bile yok. Sadece orta adımlardan biri. Böylece bütün m’ler üzerinde döngü oluşturuyoruz. Her şeyin en dışında yapılacak şey türünden. Ben gittikçe daha uzun yollar yapmak istiyorum ve bu Bellman-Ford’un tanımladıklarına benziyor ama ondan daha kötü.. Ne yapalım.. Bu bir atlama taşı.. Sonra, bütün i ve j’ler için bu minimumu hesaplamak istiyoruz. Öyleyse, bütün k’leri döngüye sokacağız ve gevşeteceğiz.. Minimumu hesaplayacağımız yer burası. --- Ve bu bir gevşetme,önemli nokta bu..

Aslında bu iyi dostumuz, gevşetme adımı, gevşetme kenarı. Pek de değil-- evet. -- Galiba kj kenarını gevşetiyoruz, -- ancak burada aynı açık kavrama sahip değiliz. Gevşettiğimiz başka özel bir şey. Sadece bir kenar değil, çünkü artık tek bir kaynağımız yok. Şimdi i kaynağına göreceli olarak kj kenarını gevşetiyoruz,-- öyle bir şey yapıyoruz. Fakat bu açık şekilde bir gevşetme. Önceden doğru olmasa da, burada üçgen eşitsizliğini doğruluyoruz. Üçgen eşitsizliğinin tüm çiftler arasında geçerli olması gerek. Ve bu sadece bu minimumu uygulamak, tamam mı? ‘yi alınca, önceden olanın minimumunu alıyorsunuz. Bir anlamda bu sıfır kenar ağırlığına bakarken düşündüğümüz olanaklardan bir tanesiydi. Burada pekala diyoruz, “veya, i’den bir k’ye daha önce nasıl olduğunu bildiğimiz bir şekilde gidebiliriz ve sonra kenarın üstüne ekleriz ve daha iyi olup olmadığını kontrol ederiz, eğer daha iyi ise, güncel tahminimizi ona dayandırırız.”

Ve bunu, bütün k’ler için yaparsınız. Özellikle, bu minimumdan daha küçük bir şeyi de hesaplayabilirsiniz, çünkü buraya üstsimge koymamıştım. Ancak bu yolları daha da iyileştirmek olur. Bu sebepten gevşetmenin daima yapılacak iyi bir şey olduğunu tartışmamız gerekir. Böylece, üstsimge koymayarak belki biraz daha fazla gevşeme yapıyorum, ancak fazlasının hiçbir zaman bir zararı olmaz. Doğruluğu bu iddiayı kullanarak hala tartışabilirsiniz.

Gördüğünüz gibi yaptığımız doğrudan bir uygulama değil, ama böylece dinamik programlama algoritmasına ulaşıyorsunuz. Ana sebebi aşağıya yazacağım;: gevşetme olduğunu görüyorsunuz, koşma süresinin -- olduğunu görüyorsunuz, -- tamam ama Bellman-Ford dan hiçbir şekilde daha iyi değil. Bellman-Ford, yoğun-halde bile idi, seyrek durumda biraz daha iyidir. Sonuçta pek başarılı değil.

Ama bir başlangıç. Olumlu tarafı, dinamik programlama zihnimizi düşündürtüyor. Ve birazdan daha iyi bir dinamik program elde edeceğiz. Ama ilk olarak, bu formülasyonla ilgili yapabileceğimiz faydalı bir şey var. -- Sanırım önce soracağım ve eğer biriniz görebilir ise gerçekten çok etkileneceğim.

Bu formül, matematiksel veya algoritmik yönlerden, şimdiye kadar herhangi bağlamda görmüş olduğunuz bir şeye benziyor mu? O özyinelemeyi başka bir yerde gördünüz mü? Ve tamtamına söylendiği gibi değil, ama benzeri. Eğer bir süre düşünseydiniz, eminim cevabı verebilecektiniz. Herhangi bir cevap var mı? Bunun çok sezgisel olacağını düşünmüyordum, ama sorumun cevabı matris çarpımıdır. Şimdi sizin için açık olabilir veya olamaz. Doğru ve kıvrak bir akılla düşünmelisiniz. O zaman matris çarpımı olduğu belirginleşir. Matris çarpımı hatırlayın, A, B ve C var. Hepsi, n ye n matris. Ve C eşit A çarpı B yi hesaplamak istiyoruz.

Ve bunun demek istediği, ’nin, tüm k’ler için, çarpı ‘nin toplamı olduğudur. Pekala, bu matris çarpımı için yaptığımız tanımdı. Ve o formül, sanki bunun gibi. Alt simgelere dikkat edin: ik ve kj. Şimdi, “operators” yani işlemciler biraz farklı. Burada içerdeki şeyleri çarpıyor ve hepsini topluyoruz. Orada, içerdeki şeyleri topluyor ve minimumunu alıyoruz. Ama bunun dışında, aynı. Evet, acayip ama bu işler böyle.. Bunu en-kısa yollarla ilintilendirmek için ---- bu işlemcileri değiştiriyorsunuz.

Öyle ise, bir matris çarpımı alalım ve yerlerini değiştirelim, önce ne yapmam lazım --, artı bu minimum’lu şey. Neden sadece işlemcileri değiştirip, noktanın yerine artı koymuyoruz? Bu, işleme aldığım değişik bir cebir sadece; bu cebirde, artı aslında min, ve nokta da artı demek oluyor. Bu şeylerin bu bağlamda çalışacağını kontrol etmeniz lazım, ancak eğer bunu yaparsak, ’nin, bütün k değerlerinde, artı ’lerin minimumu olduğunu elde ederiz.

Bu da gerçekten, asıl hesaplamak istediğimiz şeye benziyor. Burada m’nin bir değeri için, bunu m kere, yapmalısınız. Bu, teorik olarak, ’ dir ve bu da ’dir. Böylece bu, bir matrisin çarpımına benziyor ve bu da güzel bir şey. Eğer bu iddiayı burada kullanırsak ve öğeleri matrisler olarak düşünün, -- iddiaya göre yineleme bize, -- ve şimdi bunu matris formunda yazacağım,-- eşit olduğunu veriyor; bu komik A çarpımı olarak.

Pekala bunlar ağırlıklardı. Bu, komşuluk matrisinin ağırlığı. Bu, daha önceki d değeri idi. Bu, yeni d değeri. Böylece, onu matris şeklinde büyük harfler ile yeniden yazdım. Bu komik cebir işleminin kullanıldığı durumu daire içine alıp daire çarpımı dedim. Bayağı da şık oldu. Matris çarpımların hesaplanması hakkında bazı şeyler biliyoruz. Bunu, sürede yapabiliyoruz. Eğer biraz daha ince çalışırsak, belki küp-altı sürede de yapabiliriz.

Böylece, bu bağlantıyı kullanmayı deneyebiliriz. Ve burada ne hesaplayacağımız üzerinde düşünebiliriz. d üzeri m’nin, bir önceki 1 çarpı A olduğunu söylüyoruz. Öyle ise, d^(m) ne oluyor? Bildiğimiz başka bir cebir kavramı mı? Evet, “exponent”i yani üstü. A‘ yı alıyoruz ve bu komik çarpım nosyonu ile, m’ nin kuvvetine çıkarmak istiyoruz. Başka bir deyim ile, böylece d üzeri m, gerçekten gülünç bir şekilde, A üzeri m’dir; bu nedenle onu bir daire içine alıyorum, tamam mı? Bu, kulağa iyi geliyor. Eğer hatırlıyorsanız, bir şeyin kuvvetini hızlı sayılacak bir şekilde nasıl hesaplayacağımızı da biliyoruz. Bu kuvvet kavramının bir anlamı olması için, A’nın sıfırıncı kuvvetinin ne anlam taşıdığını söylemem lazım. Ve bu nedenle, bir çeşit özdeşlik matrisine ihtiyacım var.

Ve eğer doğru algılıyorsam, burası için özdeşlik matrisi budur. Böylece, köşegen boyunca sıfırlar ve diğer yerlerde de sonsuzlar var. Bu tanıma uyacak biçimde, yani, sıfır, köşegende sıfır ve diğer her yerde sonsuz. Aslında bu bir özdeşlik ve bunu kontrol edebilirsiniz. Eğer, onu bu gülünç çarpımla, başka herhangi bir matrisle çarparsanız, tekrar aynı matrisi elde edersiniz. Böylece hiçbir şey değişmez.

Bu gerçekten geçerli bir özdeşlik matrisidir. Ve A üzeri m’nin bir anlamı olması için, çarpım işleminizin “associative” yani çağrımsal olması gerektiğini belirtmeliyim. Yani “çember içinde A üzeri m” anlamlıdır, çünkü daire içindeki çarpım çağrımsaldır ve bunu kontrol edebilirsiniz; kontrolü zor değil çünkü min. çağrımsaldır, toplama işlemi çağrımsaldır ve tüm diğer iyi şeyler de öyle.. Ve bir çeşit dağıtılabilirlik özelliğiniz var. Ve bu da gerçek rakamlarla elde ettiğiniz doğru düzende, min ile toplama işlemi ve artı ile çarpma işlemi, kapalı bir yarım dairedir.

Kuvvetlerin ne zaman bir anlam ifade ettiğini bilmek isterseniz, bu iyi bir kural’dır. Yani eğer kapalı bir yarım daireniz varsa, bu yarım daire üzerindeki matris çarpımları size bir çağrımsal işlemci verecektir ve bundan sonra çarpımları alabilirsiniz. Bu işin sadece biraz resmi kural kısmı. Şimdi biraz sezgimiz oldu. Soru, doğru algoritma hangisidir? Olası pek çok cevap var; bunların bazıları doğru, bazıları ise yanlış.

Demek ki, matris çarpımlarına ve matris kuvvetlerine bu bağlantımız var. Ve her ikisi için algoritmalarımız var. Soru, ne yapmalıyız? Öyleyse şimdi yapmamız gereken tek şey, A’nın bu komik (n eksi bir) kuvvetini hesaplamak; n eksi bir, negatif ağırlık çevrimleri olmadığını farz ettiğimizde, en kısa yolları elde ettiğimiz süredir. Aslında, n eksi bir’den daha büyük bir kuvveti de hesaplayabiliriz. Bir kere n eksi bir’ in ötesine geçtikten sonra, A ile çarpım artık bir şeyi değişmez. Öyle ise, bunu nasıl yapmalıyız? Pekala, hiç akıllıca cevap vermiyorsunuz; ben saçma cevabı vereceğim.. A’yı alır, A ile çarparım. Sonra A ile çarparım ve A ile çarparım ve normal sıkıcı matris çarpımını uygularım.

O zaman n eksi iki, standart matris çarpımı gibi bir şey yaparım. Standart çarpım, gibi bir şeye mal olur. Ve bunu n defa yapıyorum. Bu bana bir algoritması veriyor ve içindeki tüm en kısa yolları hesaplıyorum. Wooohoo! Hiç iyileşme yok. Pekiyi, bunu nasıl daha iyi yapabilirim? -- Doğru, yapılacak normal şey, küp-altı matris çarpım algoritmasını kullanmak, ama bunun da çalışmaması üzücüdür. Bir şekilde istediğimiz yere biraz sonra nispeten daha kolay bir problem ile varacağız. Ancak en kısa yolların, Strassen’in algoritmasında olduğu gibi, hızlı matris çarpımları kullanılarak nasıl hesaplanacağı,pratikte bilinmiyor. Ama, iyi bir öneriydi. Pekiyi, bunun neden çalışmadığını düşünmelisiniz ve ben size bunu söyleyeceğim.

Çok açık değil ama, tamamen mantıklı bir öneri. Ancak bu bağlamda pek işlemiyor. Birkaç dakika sonra kendini gösterecek. Sorun, Strassen’in çıkarma kavramlarına dayanır. Burada ise, toplama min’dir-- ve min’in karşıtı yok. Bir kere argümanları aldıktan sonra, min’i iptal edemezsiniz. Yani çıkarma kavramı olmadığı için onun nasıl çalıştırılacağı maalesef bilinmiyor.

Pekala, başka ne numaralarımız var? Evet? Böl ve fethet, log n kuvveti, evet, yinelenen kare kökleme. Bu çalışır. Güzel, elimizde iyi bir yol var... Eğer bir n sayısı olursa, n’nin, bir şekilde iki tabanındaki gösterimine bakmak için, ya sayının karesini alırsınız, ya da karesini aldıktan sonra, A faktörünü eklersiniz. Burada ise, çok zeki olmamıza gerek bile yok. Evet, sadece hesaplayabiliriz. Sadece ikinin kuvvetlerini düşünmemiz lazım. Bilmek istediğimiz,-- burada daha büyük bir fonta ihtiyacım var, çünkü farklı düzeyde sayısız alt-simgeler var, -dairesel kuvvete A; log n tavanına da 2; aslında, n eksi bir yeterli olur.

Benim gibi siz de yeterli yazacak yer bırakmadıysanız,-- n tavanı, dairenin içinde.. Bunun anlamı, ikinin n eksi bir’den sonraki kuvveti, yani iki üzeri tavan logu dur. Öyleyse, n eksi bir’e doğrudan gitmemiz gerekmez. Daha ileri gidebiliriz çünkü, n eksi birden daha uzak herhangi bir değer, hala en-kısa yoldur.Eğer tanıma bakarsanız ve yollarınızın basit olduklarını bilirseniz, ki bu sadece negatif ağırlık çevrimleriniz olmadığı zaman geçerlidir, o zaman güzel, daha da ileri gidin.

Neden olmasın? Ve böylece bunu hesaplamak için, sadece log n eksi birin çarpımlarının tavanını yapıyoruz, sadece A’nın karesini alıyoruz ve sonra sonucu alıp onun karesini alıyoruz; sonucu alıp yine karesini alıyoruz. Böylece bu, log n kareler düzeyi oluyor. Strassen’i nasıl kullanacağımızı bilmiyoruz, ama ün sıkıcı standart çarpımını kullanabiliriz ve bu bize, log n koşma süresini verir; , bu da Bellman-Ford ’dan, hem de yoğun durumunda bile daha iyi bir sonuç veriyor.

Pekala, yoğun şıkta Bellman-Ford idi. Biz burada, log n, elde ediyoruz, böylece nihayet daha iyi birşey elde ediyoruz.Seyrek durumda, eşit gibi, belki biraz daha kötü. E V düzeyinde. Sonra, Bellman-Ford için olduğu gibi elde edeceğiz. Burada, log n, elde ediyoruz. Pekala, log faktörlerden sonra, bu bazen bir iyileştirme olur. Tamam, diğer zamanlarda yaklaşık eşit olurlar. Bundan ücretsiz olarak elde ettiğiniz diğer hoş bir şey, negatif ağırlık çevrimlerini belirleyebilmenizdir. Öyleyse, işte bir bulmaca. Bu çarpımı hesapladıktan sonra, yani A’ nın tavan log (n -1)inci kuvvetini bulduktan sonra bir negatif ağırlık çevrimi bulup bulmadığımı nasıl bilebilirim? Yani bu, tüm ağırlıkların en kısa yolları matrisinde, en fazla belli bir uzunluk ne demektir?

Eğer bir çevrim bulduysam, o matrisin içinde ne olması gerekir? Efendim? Doğru, örneğin bu şeyi alabilir, A ile çarpar, matrisin değişip değişmediğine bakabilirim. Doğru, bu iyi çalışır. Bellman Ford’da yaptığımız da bu.Hatta, daha da kolay bir şey.Çünkü zaten orada çarpmanıza gerek yok. Ancak, bu aynı koşma süresidir. İyi bir cevaptı. Evet, köşegenin, negatif bir değeri olur . Böylece bu hoş bir şey.

Her iki yaklaşım da çalışır, bir negatif ağırlık çevrimini, matrisin sadece köşegenine bakarak belirleyebilir. Köşegende sadece bir negatif değer ararsınız. Pekala bu birinci algoritmaydı. Demek istediğim, birkaç tane gördük, hepsi kötüydü, ama buna bir numara diyeceğim. İki tane daha göreceğiz. Bu içlerinde tek – tamam da bunu söylememeliyim.-- Pekala, yolumuza devam edelim. Sonuç olarak bu çok yararlı bir dinamik program olmadı, sadece ilginç olan matris çarpımlarıyla bir bağlantı kurdu. Birazdan bunun neden yararlı olduğunu göreceğiz.

Fakat bu 4 çirkin döngüye yol açtı. Ve bu numarayı kullanarak, log n’ ye indik. Şimdi sadece ’ü deneyelim. O log’ dan kurtulalım. O can sıkıcı. Sonucu, Bellman-Ford’ un seyrek durumundan daha kötü etkiliyor. Böylece, bu iç içe geçmiş döngülerden birini silelim. Evet bunu yapmak istiyorum. O algoritmanın çalışmaması gayet normal, çünkü ilk küçülme hali için ve o da ayrıca tanımlanmamış, ama benim yeterli değişkenim var. Neden, k’ nin m’ ninci kuvvetini tanımlamıyorum?

Bunun çalıştığı ortaya çıkar. Yeni baştan başlayacağım, neden olmasın? Floyd ve Warshall da, algoritmalarına bu yolla mı vardılar bilmiyorum, ama biz devam edelim. İşte, Floyd - Warshall. Temel fikirleri, alt-problemleri biraz daha akıllıca tanımlamak; böylece bu değerlerden birini hesaplamak için n şeyin min ‘ ini almanıza gerek kalmasın. Sadece iki şeyin mi ‘ ini almak istiyorum. Eğer bunu yapabilirsem, sadece alt problemim olur, dolayısıyla zamana mal olur. Yani dinamik programın koşma süresi, alt problemlerin sayısı, çarpı bir alt-problem için yinelemenin hesaplanmasının aldığı zamandır. Böylece işte, doğrusal, çarpı ve biz çarpı sabit istiyoruz. Bu iyi olurdu. Bu da Floyd - Warshall oluyor. Böylece, ‘yi yeniden şöyle tanımlayacağız: --

Sanırım orada, idi. İyi, böylece yeni bir şey tanımlayacağız. , üst simge k, şimdi önceki gibi, i’den j’ ye, en kısa yolun ağırlığı olacak. m yerine, üst simge k’yi kullandığıma dikkatinizi çekerim, zira, k ve m‘ nin aynı şey olmasını istiyorum. Derin mevzu. Pekala, işte yeni kısıt. Yol boyundaki tüm ortadaki köşelerin, başta ve sondaki i ve j dışındaki tüm köşelerle buluşanlarının küçük bir etiketleri olmasını istiyorum. Böylece, 1’den k‘ ye kadar olan setin içinde olmalılar. Burası 1’den m’ye kadar etiketlenmiş olan köşelerimizi gerçekten kullandığımız yer oluyor. Öyle ise, ilk önce başka köşeleri kullanmayan, en kısa yolları düşünün diyeceğim. Bu k’nin sıfır olduğu zaman.

Sonra, belki köşe 1’i kullanan tüm en kısa yolları, düşünün. Ve sonra, belki köşe 1 ve köşe 2’yi kullanan en kısa yolları düşünün. Neden olmasın? Bu şekilde tanımlayabilirsiniz. Öyle ise, k’ yi arttırdığınızda, sadece bir yeni köşeyi düşünmek zorundasınız. Burada, min bölü tüm k’yi almak zorundaydık. Şimdi ise, hangi k’ye bakmak istediğimizi biliyoruz. Belki bu anlamlı geliyor, belki de henüz çok açık değil. Ama, bu iddiayı yeniden yazacağım, yeniden bir özyineleme yapacağım.

Belki önce çok bilinen şeyler söylemeliyim. Eğer en kısa yolun Delta (i, j)’sini istiyorsam, o takdirde tüm köşeler alınmalı. Yani üstsimge n’ yi alın, Bu hepsi olur. Ve bu yol negatif ağırlık çevriminiz olsa da çalışır. Ancak, gene de negatif ağırlık çevrimlerini saptayabildiğimiz sürece görmezden geleceğiz. Ve diğer bir basit durum da, ..

Bunu iddiamın içine koyayım ki biraz daha uyumlu olsun. İşte yeni iddiamız: .Eğer, üst-simge sıfır‘ ı hesaplamak istersek --bu nedir? Üst simge sıfır, herhangi bir orta köşeyi kullanmayalım demektir. Bu sorunun çok kolay bir yanıtı var, üç harfli bir yanıt. Sıfır değil, o üç harfli değil.. Ne dediniz? NIL, yani hiç. Hayır, o da çalışmaz. Onun da bazı alt simgeleri var. Tanım şöyle oluyor, ortadaki köşelerin kullanımına izin verilmemiş ise, i’den j’ye en kısa yol ağırlığı nedir? Efendim?

Evet çok kolay bir adı var. Aldatıcı tarafı orası. Pekala, eğer i eşit j olursa-- çok akıllısın, doğru, aç köşeli parantezi, i eşit j bir demek, tamam. Sanki çalışır gibi ama tam doğru değil. Gerçekten eğer i eşit j değilse, ben sonsuz olmasını istiyorum; ve i eşit j ise ben sıfır istiyorum. -- , iyi. Galiba da a_ij. Bunun doğru olması lazım. Belki yanılıyorum. Evet . Böylece bu başta söylediğim değil. Eğer, i, j’ ye eşit değil ise, gene de i’yi j’ye bağlayacak bir tek-kenar bulmayı düşünmelisiniz, tamam mı? Dolayısıyla bir parça incelik var. Bu sadece ortadaki köşeler, o nedenle, i’den j’ye tek-kenar ile gene de gidebilirsiniz.

Bu, ’ye mal olur. Eğer, bir kenar varsa sonsuzdur. Yoksa, ‘ dir. Böylece bu bizi başlatabilir. Ve sonra, bir özyineleme istiyoruz. Özyineleme ile belki, daha evvel sahip olduğunuz tüm köşelerinizden kurtulursunuz. Önceden sahip olduğunuz yolları bilmek isterseniz yani daha önce 1’den k’ye kadar olanları kullanan yolları bilmek isterseniz, ben sadece 1’den (k – 1)’e kadar olanları kullanırdım. Bunu deneyebilirsiniz. Veya k’yi kullanmayı deneyebilirsiniz. Yani, k’yi ya kullanırsınız veya kullanmazsınız. Eğer kullanmazsanız, bu olması lazım. Eğer kullandıysanız, o takdirde k’ye gitmelisiniz. Gerçekten, niye sonunda k’ ye gitmeyesiniz? Böylece, i’den k’ye, daha önceki köşeleri kullanarak gidiyorsunuz. Şüphesiz oradaki k’yi, tekrarlamak istemezsiniz. Ve sonra, k’den j’ye, bir şekilde k olmayan köşeleri kullanarak gidersiniz.

Bunun oldukça sezgisel olması gerek. Gene bir resim çizebilirim. Böylece, ya k’ye hiç bir zaman gitmezsiniz ve o yol bu düz olmayan çizgi. i’den j’ye, sadece 1’den (k-1) kadar olan şeyleri kullanarak gidersiniz. Burada “birden k’ye kadar” olanı kullanmak zorundayız, yani k’yi tek başına kullanmayın. Böylece bu da bu şeydir. Veya k’ yi, orada ortada bir yerde kullanırsınız. Tamam, bu iki şeyden birinin olması lazım. Ve bu durumda i’den k’ye, sadece daha küçük köşeleri kullanarak gidersiniz, çünkü k’ yi tekrarlamak istemezsiniz.

Ve burada, k’den j’ye, sadece etiketlenmiş daha küçük köşeleri kullanarak gidersiniz. Böylece, her yol ikisinden biri olur. Yani bu iki alt problemden en kısa olanını alırız. Doğru cevap budur. Şimdi, iki şeyin min.’ine sahibiz. Hesaplaması sabit zaman alır. Böylece kübik bir algoritma elde ederiz. Bunu yazayım: Bu bir Floyd- Warshall algoritmasıdır. İsmi yeniden yazacağım. Ona bir A matrisi veriyorsunuz. Bilmesi gereken şeyin hepsi bu. Her şeyi kodluyor. Siz A’ya C’yi kopyalıyorsunuz. Bu işin ısınması oluyor. Sıfır anında, C eşittir A.

Ve sonra, k’nin, her değeri, i’nin her değeri, ve j’nin her değeri için, bu üç döngünüz var. O min ‘ i hesaplıyorsunuz. Eğer üzerinde biraz düşünürseniz, o min bir gevşetmedir. Sürpriz, sürpriz. İşte bu da Floyd-Warshall algoritması oluyor. Ve koşma süresi de, açıkça ‘dür. üç içiçe döngü, içeride sabit zamanlı. Böylece,sonunda Bellman-Ford’dan asla daha kötü olmayan bir şey elde ederiz. Seyrek durumda da aynı. Ve daha yoğun durumlarda kenarların sayısı süper doğrusal. Bu nitelikleri ile, Bellman-Ford’dan, mutlak surette daha iyi. Ve şimdiye kadar tüm-ikili- en-kısa-yollar için gördüğümüz şeylerin hepsinden daha iyi. Negatif ağırlıkların da üstesinden gelir; çok basit bir algoritma, bir öncekinden bile daha basit. Üç döngü içinde sadece gevşetme. Daha başka ne isteyebilirsiniz? Şimdi, bunun gerçekten bizim hesapladığımız min olup olmadığını kontrol etmemiz lazım; ancak üst simgeleri atlanmıştı.

Bu yine işin biraz kolayına kaçmaktı. Üstsimgeleri kullanmamak yerinde bir şey, çünkü bu yapmanız gerekenden daha fazla gevşetme yapıyorsunuz demektir. Fazla gevşetme yapmak size bir zarar vermez. Özellikle yapmamız gerekenlerin hepsini yapıyorsunuz. Böylece en-kısa-yol ağırlıklarını buluyorsunuz. Ve gene burada negatif ağırlık çevrimleri olmadığını farz ediyoruz. Onları bulmak zor olmamalı ama, biraz düşünmeniz gerekir.

Pekala, Bellman-Ford’u bir tur daha kullanabilir ve yeni bir kenarda gevşetmeye neden olup olmadığını görebilirsiniz. O versiyonda başka hoş bir ustalık olmadığını düşünüyorum. Şimdi, -- bu tüm-ikili-en-kısa-yollar için ikinci algoritmamızdı. Üçüncü algoritmaya geçmeden önce, içlerinde en akıllısı olacak-- ve hepsine üstünlük kuracak olana geçmeden önce, üçlemeleri değiştirmek için küçük bir sapma yapıp, kısaca “transitive closure” yani geçişli kapanış’tan bahsedeceğiz.

Bu bilinmesi gerçekten iyi bir şey ve şimdiye kadar gördüğümüz tüm algoritmalarla ilintili. İşte geçişli kapanış problemi. Size yönlendirilmiş bir grafik veriyorum ve bütün ikili köşeler, i ve j için, bu sayıyı hesaplamak istiyorum. Eğer, i’den j’ye bir yol varsa, bu 1‘ dir.-- i’ den j’ye. Tamam aksi takdirde, sıfır. Bu bir çeşit, “adjacency matrix with no weights” yani sıkıcı ağırlığı olmayan komşuluk matrisi; farklı tarafı, kenarlar hakkında değil, yollar hakkında olması. Pekala, öyleyse bunu nasıl hesaplayabilirim?

Çok kolay. Nasıl hesaplamalıyım? Bu bana bir anlamda grafik veriyor. Bu, yeni bir grafiğin komşuluk matrisi ve adı da benim giriş grafiğimin geçişli kapanışı.. Evet? Enine arama, evet, iyi. Öyleyse bütün yapmam gereken en-kısa yolları bulmak; eğer ağırlıklar sonsuz çıkarsa, yol yok demektir. Eğer sonsuzdan az ise, öyleyse bir yol vardır. Ve bundan dolayı belki, “ağırlıklara aldırmam, böylece enine aramayı n defa çalıştırırım ve bu gerçekten işler,” diyorsunuz. O takdirde, V çarpı B(S) yaparsak -- belki burada konuyu ortasından anlatıyorum ama bunu “5 dakika ara..” kabul edin.

“Böylece, V çarpı E gibi bir şey olur. Bu algoritmalardan herhangi birini kullanabilirsiniz. Mesela,Floyd-Warshall’ ı alabilirsiniz. Neden olmasın? O takdirde bu olur. Bu algoritmaların herhangi birini, bir veya sıfır ağırlıklı çalıştırabilir ve değerlerin sonsuz olup olmadığını kolaylıkla kontrol edebilirsiniz. Yani, eşit sıfır, “if and only if” yani sadece, i’den j’ye en-kısa-yol-ağırlığı sonsuz ise olabilir.. Öyleyse, bunu çözelim. Bu, en-kısa yollardan daha kolay bir problemdir. Gerçekten, bir anlamda kesinlikle daha kolaydır, çünkü geçişli kapanışta olan biten..—ve bunu ilgi duyduğumdan anlatmak istiyorum çünkü geçişli kapanış gerçekten bilinmesi faydalı bir şey.

Aslında yaptığımız, bunu doğru yazayım, farklı bir işlemciler seti kullanmak; “or & and” yani veya-ve-ve kullanıyoruz; min-ve-artı yerine, mantıksal veya-ve-ve’yi kullanıyoruz, tamam mı? Çünkü bir gevşetmeyi düşündüğünüzde, bir bakıma belki de onu bu min açısından düşünmeliyim. Örneğin “i’den j’ye giden ve ortadaki 1’den k’ye kadar olan köşeleri kullanan bir yol var mı? diye sorabilirim.

Ya, k köşesini kullanmayan bir yol vardır, ya da k’ yı kullanan bir yol vardır ve o takdirde şöyle görünmesi lazım. Yani, burada bir yol olması lazım ve orada da bir yol olması lazım. Bu durumda, “min” ve “artı” , “veya” ve “ve” ile yer değiştirir. Ve hatırlıyorsanız, bu artı idi; ve bu matris dünyasında çarpım idi. Böylece, artı şimdi “veya” gibi ve çarpı ise, “ve” gibi oluyor. Bu çok iyi gibi, değil mi?

Artı, ‘veya’ gibi hissediyor ve çarpı da ‘ve’ gibi hissediyor, eğer sıfır-bir’ler dünyasında yaşıyorsanız. Böylece bu – tam anlamıyla, “Z mod iki” alanı değil ama, içinde çalışılması iyi ve güzel bir alan. Boolean Dünyası. Ben sadece Boole diye yazacağım. Kadim dost Boole, bu şeyleri iyi biliyordu. Boole’un cebiri hakkında konuşmak, onun master tezinde olmak gibi.. Bu aslında hızlı matris çarpımını kullanabilirsiniz anlamına gelir. Strassen ’in algoritmasını kullanabilirsiniz ve daha fantazi algoritmaları kullanabilirsiniz ve geçişli kapanışı küp-altı sürede hesaplayabilirsiniz. Eğer kenarlar seyrekse, bu küp-altı olur. Ama en kötü durumda, eğer pek çok kenar varsa, kübiktir. Bu kübiktir. Aslında Strassen’i kullanarak bunu daha iyi yapabilirsiniz. Ben sadece yapabilirsiniz diyorum.

Burada detay vermiyorum. Sanırım olması lazım.. -- aslında bir teorem var. Muhtemelen ders kitabında da yok ama, bir teoreme göre, geçişli kapanış sadece matris çarpımı kadar zormuş. Birbirlerine eşitler. Koşma süreleri aynı. Bir alan üzerine matris çarpım yapmanın ne kadar zaman aldığını bilmiyoruz. ile arasında bir şey olması lazım. Ancak, yanıt her ne ise bu geçişli kapanış için de aynıdır.

“5 dakika ara” bitti.. Strassen ve arkadaşlarını kullandığımız yer de bu oluyor. Strassen’in olduğunu hatırlayın. Bunu özellikle final sınavında hatırlayın. Bu şeyleri daima dilinizin ucunda tutmalısınız. Pekala son işleyeceğimiz algoritma, geçenlerde gördüğümüz Johnson’ un algoritmasının üzerine inşa edecek. Ve burada koşma sürelerinden bazılarını kaybettim. Ancak ağırlıksız grafiklerimiz olduğu zaman, tüm-ikilileri gerçekten çok hızlı yapabiliriz; örneğin, tek kaynaklı Bellman-Ford kadar hızlı. Oldukça hoş bir şey. Tek kaynak durumunda, Bellman-Ford’u iyileştirmenin yolunu bilmiyoruz.

Bu nedenle, V çarpı E‘den daha iyisini elde edemiyoruz. V çarpı Dijkstra’ yı hatırlarsanız, V çarpı Dijkstra, yaklaşık aynı idi. Bunu buradaki hatırlama balonunun içine koyun: V çarpı Dijkstra, bize V çarpı E artı log V ‘ yi verir. Eğer, o log faktörüne önem vermezseniz, bu sadece, VE’ dir. Bu da gerçekten iyiydi. Dijkstra muhteşemdi. Ve bu negatif olmayan kenar ağırlıklarıyla idi.

Negatif kenar ağırlıklarına gelince, bunlarla bir anlamda aynı koşma süresini elde etmek istiyoruz. Şimdi, aynı koşma süresini nasıl elde edebilirim? Dijskra’ yı kullanabilseydim iyi olurdu. Kullanamam çünkü Dijkstra negatif ağırlıklar ile çalışmaz.Öyle ise ne yapabilirim? Ne yapmayı ümit edebilirim? Algoritmanın tam ortasında, “n defa Dijkstra” denildiğini düşünün. Buna hazırlıklı olmak için ne yapabilirim? Tüm ağırlıkları pozitif yapmalı, evet.. Neden olmasın? Sadece iyi niyetle düşünüyoruz. Yapacağımız da bu. Buna “graph re-weighting” yani grafiğin yeniden ağırlıklandırılması deniliyor. Ve hoş olan yanı bunun nasıl yapılacağını biliyoruz. Sadece nasıl yapılacağını bildiğimizi, bilmiyoruz. Ama ben nasıl yapılacağını bildiğimizi biliyorum. Siz daha bunun nasıl yapılacağını bildiğimizi bildiğimi bilmiyorsunuz.

Aslında köşeleri yeniden ağırlıklandırabilirsiniz. Geçen dersin sonunda birisi bana, tüm kenarlara aynı ağırlığı eklemenin mümkün olup olmadığını sordu. Bu çalışmaz. Nedeni, farklı yolların kenarları da farklı sayıdadır. Şimdi yapacağımız, her bir köşeye belli bir ağırlık eklemeye çalışmak. Bu ne demek oluyor? Çünkü sadece kenarlarda ağırlıklarımız vardı. Yapacağımız şey şu:

Her kenara yeniden ağırlık vereceğiz, böylece (u,v) -- matris dili yerine grafik diline dönüyorum, i ve j’nin yerine (u,v), bu değişen ağırlığa w_h diyeceğiz. Burada h bizim fonksiyonumuz. Her köşe için bize bir sayı veriyor. Böylece, o kenarın eski ağırlığı, artı başlangıç köşesinin ağırlığı, eksi sonlanma köşesinin ağırlığı, oluyor. Bunların iyi isimler olduğuna eminim. Bunlardan biri ‘baş’, diğeri de ‘kuyruk’, ancak hangisi hiç hatırlayamam. Öyle ise, (u,v) adlı yönlendirilmiş-kenarımız var. Sadece, bir tanesini ekleyin, diğerini çıkarın. Bu bir yönlendirilmiş kenar yani uyumlu bir tanımı var. Buna yeniden ağırlıklandırma deniliyor.. Şimdi bu aslında bir teorem.

Eğer bunu, grafikteki u ile v gibi herhangi iki köşe için yaparsanız, u’dan v’ye giden tüm yollar, eskisi gibi aynı ağırlığa sahip olurlar; bu çok doğru olmadı. Aynı yeni eklenen ağırlığa sahip olurlar. Eğer tüm farklı yollara bakar ve, ile..-- pardon, delta diyelim çünkü eski en-kısa-yollar onlardı; ve delta _h de,bu yeniden ağırlıklandırma fonksiyonuna göre en-kısa-yol ağırlıklarıdır, o takdirde fark aynıdır.Yani tüm bu yollar aynı miktarlarda yeniden ağırlıklandırılmıştır. Aslında bu beyan sadece en-kısa yollar için değil, tüm yollar için geçerlidir. İşte bu kadar..

Bu kaç kişi için yeterince açık? Bayağı az,evet. O tek kelime, neydi? Pekiyi, belki o kadar aşikar bir şey değildi. Pekala, ne olduğunu çıkardığınız zaman, o kelimeyi yüksek sesle söyleyin. Bu arada ben de bu sözcüklerle dolu ispatı yazacağım. Tek kelimelik bir ispat var-- hala bekliyor. Şimdi sadece, u’dan başlayıp v’de son bulan bu yollardan bir tanesini alalım. Herhangi birini alın. Sadece yeni ağırlığının, eski ağırlığına olan ilişkisini göreceğiz. Bu amaçla, yolun ‘sini yazalım, her zamanki gibi, yolun kenarını, ’den, ’e yeni ağırlığının, tüm kenarlar üzerindeki toplamı olarak tanımlıyoruz.

Kelimeyi bulan var mı? Hayır mı? Öyleyse zor bir bilmeceymiş. Böylece, bir yolun ağırlığının tanımı bu. Ve bu şeyin, sadece w(, ) olduğunu biliyoruz. Bunu doğru yazacağım, artı ilk köşenin ağırlığı, artı ’nin yeniden ağırlıklandırılmışı, eksi v_i+1’in yeniden ağırlıklandırılmışı.. Bunların hepsi parantez içinde ve i sayıda toplanıyor. Şimdi sihirli kelimeye ihtiyacım var: Teleskoplar, iyi. Şimdi bu açık: bu teleskoplar birbirini götürüyor, bir önceki ekstra ile en baştaki ile en sondaki hariç. Böylece, bu kenarların ağırlıklarının toplamı, ama bu toplamın dışında, bir de artı h() ile eksi h() var.

O ahbaplar birbirlerini götürmüyorlar. Çevrime bakmıyoruz, sadece bir yola bakıyoruz.Ve bu şey tamamen yolun w’si, çünkü bu, yolun normal ağırlığı. Böylece fark, yani w_h(P) ile, w(P) arasındaki değişim bu şeydir, o da h(u) eksi h(v)’dir. Buradaki önemli nokta, u ile v arasındaki en-kısa yolun uç-noktalarını sabitlediğiniz sürece bu, yol ağırlığını tüm yollar için aynı ağırlıkla değiştirir. Bu, u’dan v’ye herhangi yol için geçerlidir ve bu teoremi ispatlar. Buradaki tek kelime teleskoplardı. Ağırlıklardaki bu değişiklikler, teleskop bölü herhangi yoldur, bu nedenle eğer en-kısa yolları bulmak isterseniz, en-kısa yolu doğrudan bu yeniden ağırlıklandırma versiyonu içinde bulun ve bu tek miktar ile değiştirin.

Bu miktarı eklemek yerine çıkarırsanız, bu size en-kısa-yol ağırlığını orijinal ağırlık değerinde verir. Yani bu bir araç. Şimdi ağırlıkları grafikte değiştirme şeklini biliyoruz. Ancak asıl istediğimiz, grafikteki ağırlıkların hiç birini negatif olmayacak şekilde değiştirmek. Pekiyi bunu nasıl yapıyoruz? Niçin yeryüzünde tüm kenar ağırlıklarını negatif olmayacak şekilde değiştirecek bir h fonksiyonu yok?

Böyle yakınmanın anlamı yok. Çünkü nasıl yapılacağını zaten bildiğimiz ortaya çıkacak. Öyle ise bu sonucu yazmalıyım. Düzenli bir sıraya koyayım. Özellikle en kısa yol, bu miktar kadar değişiyor. Ve bu değeri bilmek isterseniz, elinizdeki bu şeyleri öbür tarafa taşıyın. Önce, delta_h’yi hesaplarız, sonra da delta’yı. Buradaki sonuç bu. Buradaki kaç kişi, bu ‘corollary’ kelimesini doğru telaffuz edebiliyor?

Pekala, kaç kişi ‘corollary’ diye telaffuz ediyor? Ya biz yalnız kaldık. Her zaman en az bir öğrenci daha oluyordu, genellikle Kanadalı veya İngiliz. Aksan, sanırım. Bu nedenle bu sözcüğü kullanmaktan kaçınıyorum, aslında ‘corollary’ olduğunu benimseyene kadar; sonra doğru telaffuz ediyorum. Hiç değilse ben Z diyorum, Zed değil.Pekiyi devam ediyoruz.Yapmak istediğimiz bu fonksiyonlardan bir tanesini bulmak. Elde etmeyi ümit edebileceğimiz şeyi yazıya dökelim. Bir, yeniden ağırlıklandırma fonksiyonu, h’yi bulmak istiyoruz. Her köşeye ağırlıklar atasın ve öyle ki, w_h (u, v) hiç negatif olmasın; E’nin içindeki tüm (u,v) kenarları için..

Bu takdirde Dijkstra’yı kullanabilir, delta h’leri elde edebilir ve sonra yeniden ağırlıklandırmayı kaldırabilir ve istediğimizi elde ederim. Bu da Johnson’ ın algoritması olur. İddia, bunun her zaman mümkün olduğu. Niçin her zaman mümkün olması gerekir? Bu sınırlamaya bakalım. (u,v), yani w(u,v) artı, h(u), eksi h(v)’nin negatif olmaması lazım. Bunu bir daha yazayım. Bu ahbapları buraya koyacağım. Doğrusu bu olacak, h(v) eksi h(u), w(u, v) ‘ye küçük- eşittir. Bu size tanıdık geliyor mu?

Doğru yaptım mı? Doğru olması lazım. Kimse bu eşitsizliği daha önce gördü mü? Evet, evet doğru cevap. Pekiyi, nerede? Önceki bir derste mi? Önceki derste. Bunun adı nedir? -- Eğer h’yi, x ile değiştirirsem..-- Charles biliyor. İyi bölüm iki’ye geri gittiğinde hatırlayan başka kimse var mı? Biliyorum, bir hafta sonu vardı. Bu işlemcinin adı ne? Çıkartma değil, ama, -- galiba işittim, -- vay canına. Pekala ben söyleyeceğim. Bir fark kısıtı, değil mi? Bu fark kısıtı işlemcisi.. Tamam bu iyi dostumuz fark kısıtları.. Yani karşılanmasını istediğimiz bu. Bir fark kısıtı sistemimiz var. h(v)’ eksi, h(u)’nun ne olduğunu bulmak istiyoruz. Bunlar, bilinmeyenlerimiz. Bu kısıtlar çerçevesinde bize w’yi verirler.

Şimdi, bu fark kısıtlarının ne zaman karşılanabildiklerini biliyoruz. Bana birisi bunların ne zaman karşılanabileceğini söyleyebilecek mi? Ne zaman karşılanacaklarını kesin olarak biliyoruz.- Her çeşit fark kısıtı seti için.. Matematiğini hatırlamanız lazım. Terminolojiyi anlayabilirim- belki de dil bilimci değilseniz sözcükleri hatırlamak güçtür. Pekala, fark kısıtları sistemi ne zaman karşılanır? Evet—kesinlikle—çok iyi.. Biri ders notlarını getirmiş. Kısıt grafiğinde hiç negatif ağırlık çevrimi olmadığı zaman. İyi, teşekkür ederim. Şimdi, fark grafiği ne demek?

Bu sorunun tek harflik bir yanıtı var, -- aşağı yukarı.. Bir harflik cevabı kabul edeceğim. Ne, A mı? A, yakındı, G. Evet, ben de aynı şeyi kastediyorum. Evet, böylece fark grafiği temelde G. Aslında tamamen G, iyi . Ve bunu yeni bir kaynak köşesi ekleyip tüm köşelere bağlayarak kanıtlıyoruz. Ama bu, esas konunun dışında bir husus. Bu sadece şunları karşılamak içindi. Bu ise, bizim belirlememiz. Başka bir anlatımla, eğer grafiğimizde her zamanki gibi, hiç negatif ağırlık çevrimi olmadığını varsayarsak, bunun karşılanabilir olduğunu da biliriz. Bu nedenle bu h’lerin bir görevi var. Tüm ağırlıkları, negatif olmayan ağırlıklar haline getiren bir yeniden ağırlıklandırma söz konusu. O zaman Dijkstra’yı da çalıştırabiliriz. Öyleyse, tamam. Çok güzel değil mi? Ve bu kısıtları nasıl karşılarız? Bunun Bellman-Ford’un bir turuyla nasıl yapılacağını biliyoruz; . Bu işlem, VE düzeyinde bir şeye mal olur ki, bu da V çarpı Dijkstra’ dan daha azdır.

Yani, hepsi bu kadar; detayları bir yerlere yazayım. Böylece bu Johnson’un algoritması; hepsinin en fiyakalısı. Gördüklerimiz içinde en hızlı tüm- ikili- en-kısa yol algoritması. Böylece iddia, grafiğimizdeki her (u,v) kenarı için, değişmiş ağırlığı, her kenarda negatif olmayacak şekilde düzenleyen, V’den R’ye bir h fonksiyonu bulabiliriz.Ve bunu Bellman - Ford ile yaparız; fark kısıtlarını çözmek amacıyla..

Evet bunlar, çözmek için doğduğumuz ve çözmesini geçen derste öğrendiğimiz fark kısıtlarıydı. Eğer tanıma dönüp bakarsanız, buradaki grafiklerin tam uyumlu olduğunu görebilirsiniz. Ya da, Bellman-Ford bir negatif ağırlık çevrimi olduğunu bize söyleyecektir. Bu iyi.. Yani, negatif ağırlık çevrimi olmadığını varsaymamız şart değil; bunu öğrenebiliriz. Eğer titiz davranırsanız bundan eksi sonsuzları da çıkarabilirsiniz. Ancak bu noktada sadece hiç negatif ağırlık çevrimi olmadığı durum üzerinde düşünmek istiyorum.

Eğer varsa, var olduğunu bulabiliriz, o kullanıcıya söyler. O durumda dururuz. Aksi takdirde hiç negatif ağırlık çevrimi yoktur; çünkü negatif olmayan kenar ağırlıklarını veren bir görevlendirme var. Öyle ise, sadece kullanırız. Bunu Dijkstra’yı işletmek için kullanırız. İkinci adımda – bu arada tüm bunların koşma süresinin V çarpı E olduğunu söylemeliyim. Giriş grafiği üzerinde tamamen Bellman-Ford’u kullanıyoruz, artı, hatırlıyorsanız, fark kısıtları setini çözmek için bir kaynak ilave ediyoruz. Bir kaynak S köşesi ekliyorsunuz, hepsine sıfır ağırlıkta bağlıyorsunuz, burada bir kaynağımız olmadığından Bellman-Ford’u oradan çalıştırıyorsunuz. Sadece bir grafiğimiz var ve bütün ikilileri bilmek istiyoruz. Böylece bunu, bir yerde negatif ağırlık çevrimi olup olmadığını bulmak için kullanabilirsiniz.

Ya da, bu sihirli atamayı elde edebiliriz. Böylece, negatif değil, öyle ise, üzerinde Dijkstra’yı kullanabiliriz. ’yi hesaplayabiliriz, bu doğrusal zaman alır. Ve Dijkstra’ yı her olası kaynak için çalıştırırız. Bunu çok açık bir şekilde yazacağım. Bu şey birkaç kere aklımıza gelmişti; n çarpı Dijkstra bölü, n çarpı BFS dediğimiz işte burada. Şimdi bütün v’ler için, Delta_h (u,v)’yi hesaplamak ve bunu bütün u’lar için de ayrıca yapmak istiyoruz. Böylece, buradaki koşma süresi, VE artı log V ‘ dir. Bu da V çarpı, Dijkstra’ nın koşma süresi, o da E artı V log V dir.

Bu terimin bu terim ile aynı olması mümkündür; bu iyi bir şey çünkü bunun anlamı birinci adımın bize asimptotik olarak hiçbir şeye mal olmaması demektir. Sonra, son adım, delta h‘yi biliyoruz. Sadece Delta’yı hesaplamaya ihtiyacımız var. Öyle ise, her (u,v) ikili köşesi için, sadece orijinal ağırlıkların ne olacağını hesaplıyoruz; yani delta(u,v)’yi. Ve bunu, bu doğal sonucu kullanarak yapabiliriz. Delta_h (u,v) , eksi h(u), artı h(v). İşaretleri doğru aldım. Evet, böylece bu zaman alıyor. Dijkstra’nın koşma süresi bunu da gölgede bırakır. Böylece, Johnson algoritmasının net koşma süresi, ikinci adımın koşma süresi olup, o da Dijkstra’yı n defa çalıştırmak oluyor.

Ki bayağı güzel. Tek kaynak en kısa yollarda, genel ağırlıklar için Bellman - Ford en iyisidir. Dijkstra, negatif olmayan ağırlıklar için en iyisidir. Ama tüm- ikili-en-kısa yollar için, negatif ağırlıklar sorununu, Bellman – Ford’dan gördüğümüz bu sihri kullanarak örtebiliriz. Ama şimdilik, tüm-ikili negatif olmayan ağırlıklar halinde, Dijkstra’yı n tur çalıştırmak bildiğimiz en iyi yöntemdir ve bunu genel ağırlıklar için de uyguladığımızda, görmüş olduğumuz tüm tekniklerin güzel bir bileşimini oluşturmuş oluruz.

Bu üçlemede epey dinamik programlama gördük ve bu iyi bir pratik oldu. Herhangi bir soru var mı? Quiz’den önce bu, yeni içerikli son ders oluyor. Eğer doğru hatırlıyorsam gelecek ders quiz için bir gözden geçirme yapacağız, , Ondan sonra da Şükran günü nedeniyle etüt yok.. Ve sonraki derste de quiz var. Yani çalışın. Görüşmek üzere.