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[artı bir] için ispatlayacağız.Genellikle, sizlere bir şeyi farz etmenizi öneririm. Aslında, niye kendi tavsiyemi kendim uygulayıp değiştirmiyorum? Genellikle tümevarımı bir özyineleme gibi düşünmek daha hoştur. Böylece bunun doğru olduğunu farz edersiniz, örneğin j’ye ilgilendiğiniz i’ den küçük dersiniz ve sonra bunu d[] için ispatlarsınız. Bu şekilde düşünmek genellikle çok daha kolaydır. Özellikle i’den daha küçük tüm değerler için güçlü tümevarım kullanabilirsiniz. Burada sadece bir eksiğine ihtiyacımız olacak. Burada deltalar bağlamında “i” ile (i -1) arasında belli bir ilişkimiz var. Ve bu sebeple, d değerleri konusunda bazı şeyleri tartışmak istiyoruz.

Pekala, burada ne olup bittiği hakkında biraz düşünelim. (i-1) sayıda turdan sonra, tümevarım hipotezine göre d[] eşittir Delta (s, ) olduğunu biliyoruz. Ve bunu i’ninci turda bitirmek istiyoruz; yani bunu yapmak için bir turumuz daha var. d[]’nin, doğru cevabının Delta (s, ) olduğunu sonuçlandırmak istiyoruz. Bu hiç tanıdık geliyor mu? Böylece, bu turda her kenarı gevşetmek istiyoruz. Özellikle belli bir noktada, () köşesiyle köşesi arasındaki kenarı gevşetmemiz gerekiyor. Bu yolun kenarlardan oluştuğunu biliyoruz. Yolun tanımı bu şekilde.

Böylece, i’ ninci turda her kenarı gevşetiyoruz. Bu nedenle, eksi bir ile arasındakini de gevşetsek iyi olacak. Ve sonra, ne olur? Hafıza testiniz. Çabuk, çabuk .. Ölüm Yıldızı yaklaşıyor. Öyle ise, eksi bir için doğru bir değerimiz var ise, oradan dışarı çıkan bir kenarı gevşetiyoruz; bu da demektir ki, o kenar s’den ’ye en kısa yoldur. Ne biliyoruz? d[] doğru değer oluyor – yani Delta (s, ) oluyor. Son derste, buna doğruluk önkuramı adını vermiştik. Dijkstra algoritmasında ispat ettiğimiz şeylerden biri idi, ancak gerçekten gevşetme ile ilgili gerçeklerden biriydi. Ayrıca çok basit bir kanıtlamaydı.

Ve bu, şu gerçekten çıkar. En kısa yol ağırlığının bu olduğunu biliyoruz. Bu nedenle, elbette, d[] bu nedenle en az bu kadar büyüktü --ve şimdi daha da büyük olduğunu düşünelim aksi halde işimiz son bulmuş olurdu. d[]’nin buna ayarlanmış olduğunu biliyoruz. Böylece, gevşetme aşamasında kontrol edilen koşul tamamen bu. Ve, d[] değerinin bundan daha büyük olacağını farz edelim. Ve sonra buna eşitleştireceğiz. Ve böylece bu s’nin d’si, olur.

Demek ki kenarı gevşettiğimizde onu doğru değere getirmemiz gerekiyor. Böylece bu ispatın da sonu oluyor, değil mi? Çok basit. Kısacası, en kısa yolunuza bakıyoruz. Ve işte burada. Ve eğer bunun hiç negatif ağırlık çevrimi olmadığını varsayarsak, başlangıçtaki değeri doğrudur. D[s] sıfır olacaktır. Birinci turdan sonra bu kenarı gevşetmeniz gereklidir. Ve ondan sonra bu köşe için doğru değeri elde edersiniz. İkinci turdan sonra, bu kenarı gevşetmeniz lazım. Bu kenar, bu köşe için size doğru d değerini verir ve bu devam eder.

Böylece, hangi en kısa yolu alırsanız alın, bu çözümlemeyi ona uygulayabilirsiniz. Eğer bu yolun uzunluğuna baktığınızda -- burada k kenar olduğunu varsaymıştık, o durumda k turdan sonra bitmiş olması gerektiğini bilirsiniz. Aslında daha ispatın sonuna gelmemişiz, özür dilerim. Demek ki, k sayıda turdan sonra için doğru yanıtı buluyoruz ve o da sadece v. Böylece tek soru, k ne kadar büyük olabilir? Ve cevabın da doğru olması iyi olur, en çok v eksi bir, çünkü algoritmanın sadece v eksi bir sayıda adım atmanızın yeterli olacağı şeklinde bir savı var.. Ve gerçekten de bir grafikteki basit bir yolun kenarlarının azami sayısı, köşelerin sayısından bir eksiktir.

Gerçekten de p basit olduğunda, k da en çok v eksi bir’dir. Sadece en kısa yol olması ile yetinmeyip basit olmasını da istememizin nedeni buydu. Basit olması, herhangi bir köşeyi tekrarlamaması bakımından gerekliydi. Yani yolda en çok v sayıda köşe varsa, o yolda en çok v -1 kenar olur. Bellman-Ford konusunun hepsi bu kadar. Doğruluk açısından çok kolay. Şüphesiz daha evvel görmüş olduğumuz önkuramların çoğunu bu kapsamda kullanabiliyor olmamız her şeyi daha kolaylaştırıyor. Bu teoremin yada kanıtlamanın bir diğer sonucu da, “eğer Bellman-Ford yakınsama yapamazsa” sorusu olabilir ama algoritma bu d eksi bir adımdan sonra gevşetmenin hala işlem gerektirip gerektirmediğini zaten kontrol ediyor.

Gerçekte bu algoritmanın sonunda bir tur daha vardır, V’ninci turla son bulur ve o zaman bir değişiklik olup olmadığına bakar. O halde algoritmanın, V eksi bir adım yada turdan sonra yakınsama yapmadığını söyleyeceğiz. Böyle bir durumun söz konusu olabilmesi için negatif ağırlık çevrimi olması lazım. Bu ise kanıtladığımızın, “contrapositive” yani devrik durumu olur. İspatladık ki, eğer negatif ağırlık çevrimi olmadığını varsayarsanız, d[s]’nin sıfır olduğunu biliyoruz; ve öyleyse bu argüman, v eksi bir’den sonraki turlarda da bir yakınsama yapmanız gerektiğini anlatıyor. Oysa, en kısa yol ağırlıklarına ulaştığınızda yapılacak bir şey kalmaz, çünkü monoton şekilde gittiğiniz için hiçbir zaman dibe vuramazsınız.

En alta asla varamazsınız. V eksi bir turdan sonra yakınsamada başarısız olursanız, bu ilk baştaki varsayımın ihlali olur. Yaptığımız tek varsayım, negatif ağırlık çevrimi olmadığı varsayımı idi. Böylece, bu da bize Bellman-Ford’un gerçekten doğru olduğunu söylüyor. Bellman-Ford, negatif çevrim yok dediği zaman, gerçekten yoktur. Doğrusu budur. Bellman-Ford’u, böyle bir durumda değiştirebilir, biraz daha uzun çalışmasını sağlayabilir ve eksi sonsuzların nerede olduğunu bulabilirsiniz.

Aslında bu, bence bir anlamda problem setinde yapmanız gereken şeylerden biri. O nedenle burada daha fazla yer vermeyeceğim. Ama her durumda, eksi sonsuzların nerede olduklarını bulmak açısından iyi bir egzersizdir. Bir negatif ağırlık çevrimiyle ulaşılabilecek tüm köşeler nelerdir? Eksi sonsuz olan köşelerdir. Pekala bunun çok hızlı olduğunu söyleyebilirsiniz. Ancak ders daha bitmedi. Macera henüz bitmiş değil. Bellman-Ford’u daha büyük ve kapsamlı en-kısa yol problemlerini çözmek için kullanmaya devam edeceğiz.

Bugünkü derste kalan zaman içinde, doğrusal programlama denen daha genel probleme uygulandığını göreceğiz. Gelecek derste de, “tüm-ikili-en-kısa yollar ” ile, hayret verici bazı şeyleri yapmada Bellman-Ford’u gerçekten kullanacağız. Şimdi buraya geçelim. Demek ki bugün, pek o kadar açık olmasa da hedefimiz, her köşe çifti arasındaki en-kısa yolları hesaplamak. Vardığımız aşamada Bellman-Ford’u v kere kullanarak bu hedefe ulaşabiliriz.

Ama şüphesiz biz daha iyisini yapmak istiyoruz. Ve o da, üçlemenin zirvesi olacak. Pekiyi bugün Luke’un babasının kim olduğunu keşfettik. Demek ki, en-kısa yolların babası doğrusal programlamadır. Aslında, aynı anda hem babası, hem annesi olur, çünkü programların cinsiyeti yoktur. Babam,’’annenle beraber tuluat dersleri aldık, tuluatçılıkta derecemiz var’’ demekten hoşlanır.

Bir defasında,’’komedi-tuluatçılık derslerine espri kabiliyetimizi arttırmak için gittik. Dersler, espri gücümüzü arttırmadı. Sadece kullanmaktan korkmamamızı öğretti’ dedi.. Böylece hepiniz bu espriye muhatap oldunuz. Luke’ un babasının bununla ilgisini göremedim, ama devam edelim. Demek ki, doğrusal programlama çok genel bir sorun ve çok büyük bir araç. Doğrusal programlamayı daha önce görmüş olan var mı? Pekala, bir kişi. Ben eminim, hayatınızda bir gün, optimizasyon yani en-iyileştirme hesaplamaları ile ilgili bir şeyler yaparken, doğrusal programlama bir noktada karşınıza çıkacaktır. Çok faydalı bir araçtır. Size bir matris ve iki vektör veriliyor; bu daha çok heyecan verici değil. Yapmak istediğiniz bir vektör bulmak. Bu konunun çok kuru bir açıklaması oldu.

O kadar ilginç kılan şeyin ne olduğunu birazdan göreceğiz. Böylece bir hedefi maksimize etmek istiyorsunuz ve bunu önleyici sınırlamalarınız var. Ve bunların hepsi doğrusal. Yani hedefiniz, x değişkenleri içinde bir doğrusal fonksiyon ve sınırlarınız bir grup doğrusal limit, eşitsizlik limitleri ve bu da işi ilginç hale getiriyor. Bu, doğrusal cebir veya başka yerde görmüş olduğunuz gibi yalnızca doğrusal bir sistemi çözmekten ibaret değil. Veya öyle bir x değişkeni de yok. Böylece belirsiz biçimde tanıdık geldiğinden Bellman-Ford teoremini aklınıza getirebilirsiniz. Yani bir şeyi bulmak, ya da olmadığını göstermek istediğinizde, arada belli bir ilinti olduğunu ortaya koyacağız.

Her şeye rağmen hala belirsiz bir bağlantı ama, ben bir şeyi maksimize etmeyi de istiyorum, veya en kısa yolları bir çeşit minimize etmeyi; buna benzer bir şey. Bu sınırlamalarımız var. --Evet.-- Bu size sezgisel gelebilir bilmiyorum. Ben daha geometrik bir anlatımı tercih ettiğimden, bir geometrik resmi çizmeye çalışacağım ve bunu şimdiye kadar bir kara tahta üzerinde hiç denemedim, bu yüzden ilginç olacak. Galiba, feci şekilde başarısız olacağım. Oniki yüzeyli gibi bir şeye benziyor değil mi? O biçimde, o tipte; pek de değil. Altı biraz fazla kaba. Neyse, eğer bir grup doğrusal sınırlamalarınız varsa, bunun 3 boyutlu olması gerek. Şimdi onu etiketliyorum.. İşte 3-D oldu.. İyi.

Demek ki bu doğrusal sınırlayıcılarınız var. Bu, n boyutlu hiper- uçakları tanımlamak gibi oluyor. Pekala, burada bu üç boyutlu alanınız var. Dolayısıyla, n eşit üç. Ve bu hiper-uçakların eğer sadece bir tarafına bakarsanız ve bu küçük-eşit durumudur – ve arakesitini alırsanız, belli bir poli-topaç, yada bir dışbükey “polihedron” yani çok yüzeyli cisim elde edersiniz. 3-D boyutunda on iki yüzlü yada benzerini elde edebilirsiniz . Ve hedefiniz, vektör c, ve o da yukarı yönlü diyelim var. Bunun c vektörü olduğunu farzedin.

Böylece hedefiniz bu politopaçta en yüksek noktayı bulmak. Burada belki de burası.. Evet, hedef bu. Bu optimal yani en iyi x. Bu geometrik görünümü. Eğer cebirsel görünümünü tercih ederseniz, “c-transpose” yani c-çapraz çarpı x’in en büyük değerini istersiniz. Böylece bu m’dir. Bu da n. Boyutların uygunluğunu kontrol edelim. Yani bu nokta çarpımı maksimize etmek istiyorsunuz.. c yönünde x’in uzunluğunu maksimize etmek istiyorsunuz. Ve, bunu belki de şöyle görünen belli sınırlamalar çerçevesinde yapmak istiyorsunuz. Böylece, bu A ve bu da m’ye n. Onu, n yüksekliği ile çarpmak istiyorsunuz.

Bu x .. x’i buraya aşağıya koyayım; bu n’ye bir. Bu yükseklikte bir şeyden daha küçük veya ona eşit olmalı; ve o da b olmalı -- sağ taraftaki. Tamam, bu da cebirsel görünüm, tüm boyutların çalıştığını kontrol etmek için. Ama burada her sırada bir şeyleri okuyabilirsiniz, bu sütün ile çarpıldığında size burada bir değer verir. Ve bu da tüm x kenarlarında doğrusal bir sınırlamadır. Böylece bu doğrusal fonksiyonu, tüm bu sınırlamalara bağlı kalarak ’den ’ ye kadar maksimize etmek istiyorsunuz. Pekala, oldukça kolay ama, çok da kuvvetli ve genel. Böylece, bununla en kısa yollar gibi sayısız problemi doğrusal bir program olarak formüle edebilirsiniz. Bu nedenle, genel bir araçtır.

Ve bu sınıfta doğrusal programlamayı çözmek için hiçbir algoritma görmeyeceğiz. Biraz şaşırtıcı. Sadece varlıklarını söylemekle yetineceğim. Böylece, bunu yapan pek çok etkili algoritma ve de kod var. Çok pratik kurulumlar. Böylece, LP’leri yani doğrusal programları çözmek için çok algoritma var. Doğrusal programlar genellikle LP olarak kısaltılır. Ve sadece birkaç tanesini belirteceğim. “Simpleks” yani Tek-Yönlü Algoritma var. Bu ilk algoritmalardan biri. Yanılmıyorsam ilki. Elipsoid-algoritma var. Dahili nokta metodları ve rastgele örnekleme var. Bunların her biri hakkında birkaç şey söyleyeceğim çünkü hiçbirini derinliğine incelemeyeceğiz.

Simpleks algoritma, dünyadaki ilk algoritmalardan biri olup şüphesiz en popüler algoritmalardan da biridir. Bugün hala kullanılıyor. Aşağı-yukarı bütün doğrusal programlama kodları, tek-yönlü algoritma kullanır. En kötü durumda, üstel zaman kullandığından, teorik olarak oldukça kötüdür. Ancak pratikte çok iyi çalışır. Ve son zamanlarda bunun nedenini anlamak için çalışmalar yapılıyor. Ama en kötü durumda gene de üstel’dir. Ama pratiktir. Simpleksin, polinomsal zamanda çalışan bir varyasyonu olup olmadığı hala açık bir problem. Fakat bu konuya girmeyeceğim. Çünkü bu doğrusal programlama alanındaki büyük bir problem.

Polinomsal zamanda doğrusal programlamayı çözmede ilk model, elipsoid algoritma olmuştu; yani uzun süre kimse bunun nasıl yapılacağını bilmiyordu. Bu süre içinde insanlar polinomsal zamanın iyi bir şey olduğunu farketti. Bu 1960’ların sonunda oldu. Polinomsal zaman iyidir. Ve elipsoid algoritma bunu uygulayan ilk algoritma olmuştu. Çok genel bir algoritmadır ve teorik bakımdan çok kuvvetlidir; öte yandan tamamen pratik olmayan bir algoritmadır. Ama güzel tarafı, üstel açıdan pek çok limitleri olan doğrusal bir programı çözümlemeyi polinomsal zamanda yapmanıza izin vermesidir. Çılgınca her şey var. Son olarak sadece polinomsal zamanlı olduğunu söylemekle yetineceğim. Hakkında güzel bir şey söyleyemiyorsam hiçbir şey söylemesem daha iyi olacak herhalde.. Pratik değildir.

Dahili nokta metodları, bir çeşit karışımdır. Onlar da polinomsal zamanda çalışır. Bunu garanti edebilirsiniz. Bu metotlar çok da pratiktir ve bu sebepten, “Tek yönlünün” mü, “dahili noktaların” mı daha iyi olduğu konusunda bugünlerde bir hayli rekabet var. Bugünkü durumu tam olarak bilmiyorum ama, birkaç yıl önce gırtlak-gırtlağa idiler. Rastgele örneklemeye gelince bu tamamen yeni bir yaklaşım. Bu da birkaç yıl önce iki MIT profesörü Dimitris Bertsimas ve Santosh Vempala tarafından geliştirildi, biri Elektrik Mühendisliği, diğeri sanırım uygulamalı matematik dallarında çalışıyor.

Bunları sırf bu alanda aktif çalışma olduğunu göstermek için anlattım. Pek çok kişi, hala doğrusal programların sorunlarını çözmek için yeni yollar buluyorlar. Bu tamamen rastgele hale getirilmiş, çok kolay ve çok genel. Şimdiye kadar hiç kullanılmadı. O nedenle ne kadar pratik olduğunu bilmiyoruz. Ama potansiyeli var. Çok düzenli. Pekiyi biz doğrusal programlamanın nispeten daha basit bir versiyonuna bakacağız. Yapacağımız ilk sınırlama aslında pek o kadar sınırlama da değil. Ama her şeye rağmen öyle sayacağız. Düşünmesi nispeten daha kolay. Böylece, burada bir poli-topacımız vardı ve belli bir hedefi maksimize etmek istiyorduk. Bir fizibilite probleminde bilmek istediğim şey, poli-topacın boş olup olmadığıdır? O poli-topaçta herhangi bir nokta bulabiliyor musunuz? Bu sınırlamaları karşılayacak, önceden saptanmış herhangi grup değer, x, bulabiliyor musunuz?

Pekala, öyle ise bir c hedefi yok. Öyle bir x bulun ki, böylece Ax, B’ye küçük-eşit olsun. Görünüşe göre, ‘’ Eğer doğrusal fizibiliteyi çözebilirseniz, doğrusal programlamayı da çözebilirsiniz ‘’ şeklindeki çok genel bir teoremi ispatlayabilirsiniz. Biz burada bunu ispatlamayacağız ama, daha kolay gelmesine ve düşünülmesinin kolay olmasına karşın bu, gerçekte orijinal problemin kendinden daha kolay değildir. Aslında, “LP’den yani doğrusal programlamadan daha kolay değildir.” diyecektim. Pekala, yapacağımız ikinci sınırlama, gerçek bir sınırlamadır. Ve bu problemi oldukça basitleştirmektedir.

Ve bu “difference constraints” yani fark kısıtları’na bir bakış olacak. Eğer tüm bu anlattıklarım biraz soyut geldi ise şimdi ayaklarımızı biraz yere basacağız. Fark kısıtları sistemi, bir doğrusal fizibilite yani olurluk problemidir. Yani hedefi olmayan bir Doğrusal Programlamadır. Ve bir kısıtlaması vardır; burada bir A matrisinin her sırasında bir adet 1, ve bir adet eksi 1 vardır ve geri kalan her şey 0’dır.

Başka bir deyişle, her kısıtlayıcının kendine özgü çok basit bir şekli vardır. Bunlar, iki değişken ile birkaç sayıdan oluşur. Böylece, eksi , ‘ye küçük - eşit, gibi bir şey. Bu sadece bir sayıdır. Bunlar da iki değişken. Bir eksi işareti var, burada başlarında hiç katsayı yok, buradaki ’lerden yok, sadece ikisi var. Ve bu çeşit kısıtlayıcılardan bir grup var, matrisin her sırasında bir tane. Geometrik olarak bunun ne anlamı olduğunu düşünmedim. Bence bu hiper-uçakların basit şeyler olduğu anlamını taşıyor. Af edersiniz, bundan daha iyisini yapamıyorum. Çoklu boyutlarda bunu görmek biraz güç.

Ancak yakında, daha önce gördüğümüz bir şeyle ilişkilenmeye başlayacak, yani yandaki tahtadan söz ediyorum. Pekala sırf göstereceğimiz bir şey olması için, çok hızlı bir örnek yapalım. Burada fark kısıtları olan basit bir sistem var -- Pekiyi ve bir de çözüm. Neden olmasın? Bunu çözmek çok basit de değil ama -- işte çözümü. Burada kontrol edilmesi gereken tek şey, bu kısıtların her birinin karşılanmış oldukları. eksi , 3 eder ki, o da, 3’ten az veya ona eşittir, ve böylece devam ediyor.

Negatif değerler olabilir. Pozitif değerler olabilir. Fark etmez. Bu fark kısıtları sistemini, bir grafik şekline dönüştürmek istiyorum, çünkü grafikler hakkında epey şey biliyoruz. Böylece buna kısıt grafiği diyeceğiz. Ve bu kısıtları temsil edecek. Nasıl mı yaparım? Her bir kısıtı alıyorum, genelde buna benziyor ve onu bir kenar haline dönüştürüyorum. Pekala, eğer onu eksi , ’den küçük veya onu eşit şeklinde yazarsam, w ağırlıkları ima eder.

Bunu w olarak adlandırmamın nedeni buydu. Onu da, ‘den ‘ye bir kenar yapacağım. Böylece düzen biraz evriliyor. Ve o kenarın ağırlığı, ’dir. Öyleyse böyle yapın. n köşe yapın. Yani, köşelerin sayısı n olsun. Kenarların sayısı kısıtların sayısına eşit olur ki, o da m, yani matrisin yüksekliğidir; ve sadece dönüştürün. Örneğin burada üç değişkenimiz var. Öyle ise, üç köşemiz var, yani , , . Bizim, eksi ’miz de var. Böylece, ‘den ’e kadar ağırlığı 3 olan bir kenarımız var. eksi ümüz var. Öyleyse, ‘den ‘ye , ağırlığı eksi 2 olan bir kenarımız var. eksi ‘ümüz var. Öyleyse, ‘ten, ’e ağırlığı 2 olan bir kenarımız var. Ümit ederim, yönleri doğru aldım. Evet..

Böylece işte bir grafik : şimdilik en kısa yollara belirgin bir bağlantı yok, değil mi? Ancak, aslında bu kısıtlar en kısa yollarla yakın şekilde bağlantılıdır. Şunu yeniden yazayım. Doğal olarak, , artı ’den daha küçük veya ona eşit, diyebilirsiniz. Veya onu d[j], küçük- eşit d[i] artı w (i virgül j) gibi düşünebilirsiniz. Burası kavramsal bir balon... Bir hayli tanıdık mı? Üçgen eşitsizliğine çok benzer, gevşetme yada dengeye dönmeye çok benzer gibi. Yani şimdi kanıtlayacağımız gibi, bu iki problem arasında çok yakın bir bağlantı bulunmaktadır.

Öyleyse iki teoremimiz olacak. Negatif ağırlık çevrimlerinden bahsetmeleri nedeniyle Bellman – Ford ‘un doğruluğuna benzer görünecekler. Başlıyoruz. Bu kısıtlar grafiğimiz var. Negatif ağırlıkları olabilir. Pozitif ağırlıkları olabilir. Eğer negatif ağırlık çevriminiz var ise, bu önem kazanır. Bu nedenle ispatlanması gereken ilk şey, eğer negatif ağırlık çevriminiz var ise, bunun kötü bir şey olacağıdır. Pekiyi kötü ne olabilir? Aslında sadece bu kısıtlar sistemini karşılamaya çalışıyoruz. Dolayısıyla ‘’kötü şey,’’ hiçbir çözümün olmaması olabilir. Bu kısıtlar, olurluk kavramının dışında olabilirler. İddia da o. Başka bir deyişle iddia, bunun aslında, “if and only if” yani bir ‘’eğer ve sadece eğer’’ durumu olduğudur.

Ancak ilk olarak ‘’eğer’’ i ispatlayacağız. Eğer bir negatif ağırlık çevriminiz varsa işiniz bitmiş demektir. Fark kısıtları karşılanamaz. Tabii bu, durumu sezgisel anlatmak oluyor. Doğrusal Programlama dünyası bunu, ‘’infeasible’’ yani olursuz diye tanımlıyor. Ama, ‘’unsatisfiable’’ yani karşılanamaz çok daha anlamlı olurdu. Örneğin, tüm kısıtları aynı anda karşılamak için, ‘yi görevlendirebileceğiniz bir yol yoktur. Haydi, bir göz atalım. Negatif ağırlık çevrimini düşünün. Belli bir köşeden başlıyor, bazı köşelerden geçiyor ve belli bir noktada geri geliyor. Bu çevrim, ’den ’e kadar negatif ağırlıklıysa, negatif ağırlıklı olduğu sürece köşeleri tekrarlamasına aldırmıyorum.

Şimdi yapacağım şey bütün kısıtları yazmak. Bu kenarlardan her biri, o grafikteki kısıtlar grubunda yer alan bir kısıta karşılık geliyor. Bunların hepsi kenarlar. Bize ne vereceklerine bakalım. Şimdi, ‘den ’ye, bir kenarımız var. Bu, eksi ve en çok gibi bir şeydir. Sonra, eksi ’ miz var. O da ağırlıklı ve bu böyle devam ediyor.

Ve sonunda, eksi gibi bir şeye varıyoruz. O, bu kenar. ve en sonunda, hepsini tamamlayan bu kenar var. Yani, eksi . -- . Eğer işaretleri doğru aldıysam. İyi, böylece, işte bir grup kısıt. Onlarla ne yapmamı öneriyorsunuz? Bu kısıtların herhangi bir özelliği var mı, örneğin sol taraftakilerin? Efendim? Doğru kelime gibi geldi. -- Neydi?

Teleskop, evet doğru. Her şey birbirini götürüyor. Eğer bu şeylerin hepsini toplarsam, bir ile bir eksi var. Bir tane, eksi ile bir tane var. Bir tane, eksi ile, bir tane, . Eğer sol tarafların hepsini toplarsam, hepsi birbirini götürüyor. Eğer sağ tarafları toplarsam ne olur? Burada sıfır elde ediyorum, en sevdiğim yanıt. Ve burada da, negatif ağırlık çevrimindeki tüm kenarların ağırlığını elde ediyoruz, doğal olarak bu çevrimin kendisinin toplam ağırlığı olmak yanında, negatif bir ağırlıktır da.

Bu nedenle, sıfır kesinlikle sıfırdan küçük : Sonuç çelişki. Çelişki; bir dakika, hiç yanlış bir şey varsaymadık. Bu nedenle, matematiksel yönden bu aslında bir çelişki değil; dünyayla çelişmedik. Sadece, bu kısıtların, birbirleriyle çelişkili olduklarını beyan ettik. Başka bir deyişle, bu ’lerin herhangi bir değerini alırsanız, bunların hepsinin gerçek olmaları mümkün olamaz, çünkü o zaman çelişki ortaya çıkar.. Yani bunların, bazı gerçek ’lerce karşılanması imkansızdır. Bu nedenle bunlar “karşılanamaz” olmalılar.

Bunların tatmin edici görevleri bulunmuyor diyelim, biraz daha kesin olarak, ’den ’ye kadar ağırlık yok. Bu kısıtları karşılamanın yolu yok. Çünkü sol tarafta toplamları sıfır oluyor, sağ tarafta ise tamamen negatif. Pekala işte bu kolay bir ispat yolu. Ters yönde olanı biraz daha zor. Yani güzel. Bu bağlantımız var. Şimdi, bu fark kısıtlarını çözmeye motive olacağız ve böyle bir uygulama göreceğiz. Google’da fark kısıtlarını şöyle bir araştırdım. Bu konuyla ilgili oldukça kayda değer sayıda makale var. Ve çözüm için hepsi en kısa yolları kullanıyor. Öyleyse çözümlemesini bildiğimiz en kısa yollar ile, fark kısıtları arasında bir bağlantı olduğunu kanıtlayabilirsek, o zaman çok güzel bir şey elde edeceğiz. Ve gelecek derste, fark kısıtlar alanında daha fazla uygulama göreceğiz.

Tüm çift en kısa yollar için.. Ama şimdilik sadece bu eşitliği ispatlayalım ve bitirelim. Böylece, ters yönden yaklaşıldığında, eğer bu kısıt grafiğinde negatif ağırlık çevrimi yoksa, sistemin tatmin edilmesi mümkün olsa iyi olur. İddia: bu fark kısıtlarına bir çözüm bulmada tek engeller, negatif ağırlık çevrimleridir. Sanırım, buralarda bir yerde kısıt grafiği hakkında konuşmam gerekiyordu. İyi -- karşılanabilir. İyi..

Şimdi, en kısa yolları düşünürken çok yararlı olan bir tekniği göreceğiz. Eğer özellikle daha evvel görmediyseniz tahmin etmeniz güç. Bu teknik problem setlerinde, Quiz’ lerde ve sınavlarda her şeyde yararlıdır. Bu nedenle hatırınızda tutun. Bunu nispeten kolay bu teoremi ispatlamak için kullanıyorum ama, asıl fikir bu grafiği değiştirmek; böylece bu kısıt grafiğine bundan böyle büyük harf G diyeceğim. Grafik değiştirmek çok güçlü bir fikirdir. Böylece, yeni bir S köşesi veya kaynağı ekleyeceğiz; “kaynağı kullan Luke !” Ve s’den bir takım kenarlar ekleyeceğiz, çünkü kaynak olarak bir şeylere bağlantılı olması uygun olur.

Böylece, sıfır ağırlıklı bir kenar ekleyeceğiz; kısıt grafiğinde, s’den her yere, yani, her köşeye sıfır ağırlıklı kenarlar ekleyeceğiz. O köşeler, ’den ye kadar olan köşeler olarak adlandırılıyor. Böylece, kısıt grafiğim var. Sonra değiştirebilmek için bunu kopyalayayım. Değişiklik yapmadan önce işinizi kopyalamak daima yararlıdır, değil mi? Yeni kaynağım S köşesini buraya eklemek istiyorum. Böylece, kısıt grafiğimi alıyorum, neye benzerse benzesin, tüm köşelere bağlantılı sıfır ağırlıklı kenarlar ilave ediyorum.

Bu kadar basit. Şimdi ne yaptım? Hah, hah.. Sen ne yaptın? Artık, tüm köşelere ulaşabilen bir kaynak adayım var. Böylece, S’ den bu köşelere ulaşan en kısa yolların, aslında yolların olduğunu umut ediyoruz. Başka bir deyimle, s’ den her yere, en çok sıfır ağırlık ile ulaşabilirim. Tamam, belki de daha azıyla. Daha küçük olabilir mi? Biliyorsunuz, gibi; ona 0 eksi iki ile ulaşabiliyorum. Bu sıfırdan daha küçüktür. Öyleyse, bir parça dikkatli olmam lazım. Yani, ya eğer negatif ağırlık çevrimi varsa? Oh! hayır. O takdirde, en kısa yol olmazdı. Orijinal grafikte şansımıza, hiç negatif ağırlık çevrimi olmadığını varsayıyoruz. Eğer düşünürseniz, sadece negatif ağırlık çevrimi yoksa, orijinal grafikte s’den herhangi bir yere kenar ilave edebiliriz. Yaptığımız işlem ile biz, yeni bir negatif ağırlık çevrimi yaratmıyoruz çünkü, s’den başladığınızda, herhangi bir yere sıfır maliyetle gidiyorsanız bu ağırlığı hiç etkilemiyor demektir.

Ve sonra, eski grafikte kalmak zorundasınız. Böylece, yeni bir negatif ağırlık çevrimi söz konusu olamaz. Öyleyse, değiştirilmiş grafikte negatif ağırlık çevrimi yoktur. Bu iyi bir şey, çünkü s’ den de yollar var, bu nedenle s’den her köşeye en kısa yollar var. Değiştirilmiş grafikte hiç negatif ağırlık çevrimi yok, çünkü önceden de yoktu. Ve.. s’den gelen yolları var. Her köşeye s‘den bir yol var. Daha önce bu olmayabilirdi. Örneğin önceden, ‘den ‘e ulaşamıyordum. Bu hala doğru ama, s’den her yere ulaşabilirim. Bunun anlamı, bu değiştirilmiş grafikte en kısa yolların var olduğudur.

Yani, s’den çıkan en kısa yollar vardır. Başka bir deyimle, Bellman-Ford’u kullandığım zaman yaptığım gibi, eğer s’den çıkan tüm en kısa yolların ağırlıklarını almış olsaydım, her bir köşe için, her bir değer için, v’nin d’sine karşılık olan bir grup sonsuz sayı elde ederdim. Mmm.. Bu iyi bir fikre benziyor. Haydi yapalım. Demek ki en kısa yollar mevcut. s’den ’ye enkısa yol ağırlığını, olarak tanımlayım. Neden olmasın? Bir rakam olarak iyi bir seçim, s’den ’ye en kısa yol ağırlığı. Bu sonsuz, çünkü sonsuz ’dan daha küçük ve eksi sonsuzdan da daha büyük; bu nedenle sonlu bir sayı. Bu kısıtları karşılamak için, yapmanız gereken de bu.

Buradaki iddia, yaptığımızın tatmin edici bir atama yada işlem olduğudur.. Niçin? Üçgen eşitsizliği. Buralarda bir yere, üçgen eşitsizliği yazmıştık. Bu durum üçgen eşitsizliğine çok benziyor. Aslında bu galiba kanıtın da sonu.. Buraya bir bakalım.. Bu işlem ile gerçekleşmesini istediğimiz şey, eksi ’nin, ij’ nin bir kenar olduğu her zaman, ’ye küçük – eşit olması; veya, kenarlar kümesi içindeki , ’deki her bu tür kısıt için diyelim.

Pekiyi bu ne zaman doğru? Bunu genişleterek açıklayalım. Yani, bu deltadır, , bir diğer deltadır. Böylece, bir taraftan, Delta (s, ) eksi Delta ( s, ) var. Ve sağ tarafta da, ; bu da i’ den j’ye kenar ağırlığı idi. Öyleyse bu ’den ‘ye kadar olan ağırlıktır. Bunu biraz farklı yazacağım. Delta (s , ) küçük –eşittir, Delta (s, ) artı w (, ) . Bu da üçgen eşitsizliği olur; aşağı yukarı. Böylece, s’den ‘ye en kısa yol, en çok, s’den ‘ye en kısa yol artı ‘den ‘ye özel bir yol, yani ‘den ‘ye giden tek yol olur. Bu ise, en kısa yoldan sadece daha uzun olabilir.

Ve bu da sağ tarafı büyütür, o da bu eşitsizliği daha doğru kılar, aynen önceden de gerçek olduğu gibi. Ve şimdi bu hala doğru. Bu da kanıtlamayı tamamlar. Bu doğrudur. Bunların hepsi eş beyanlardı. Bunun eşit olduğunu üçgen eşitsizliği aracılığıyla biliyoruz ve bu nedenle bu kısıtların hepsi karşılanmış oldu. Sihirli gibi.. Çok heyecanlıyım. Böylece negatif ağırlık çevrimine sahip olmanın, bu kısıt farklarının karşılanamadığı duruma bağlı olduğunu ispatlamış bulunuyoruz.

Öyle ise, eğer onları karşılamak istersek, x ’e doğru bir yanıt bulmak istersek, Bellman-Ford’u uyguluyoruz. Bellman-Ford, ya “olmaz, negatif ağırlık çevrimi var.” der; o zaman çuvallarsınız. Bu takdirde bir çözüm yok demektir. Ama bilmeyi ümit edebileceğiniz en iyi yanıt bu olabilir. Aksi takdirde, “negatif ağırlık çevrimi yoktu, işte en kısa yol ağırlıklarınız.” da diyebilir. Bu takdirde çıktıları yerine yerleştirirsiniz ve bum -- kısıtları karşılayacak x_i’lerinizi elde etmiş olursunuz. Şahane. Şimdi, bu herhangi bir grafik değildi.

Yani, demek istediğim, kısıtlar ve cebir ile başladık, bu dönüşümle onu bir grafik haline getirdik. Sonra, bir kaynak köşeyi, s’yi ekledik. Yani sorunumuzu çözmek için bir grafik yapmak zorundaydık ve bu çok güçlü bir fikirdi. Sonra Bellman-Fordu devreye alır, ondan yanıtları elde ederiz. Güzel. Bu bir “reduction” yani indirgeme fikridir. Çözmek istediğiniz bir problemi, çözüm şeklini bildiğiniz problem haline indirgeyebilirsiniz. Negatif ağırlık çevrimleri olmadığında en kısa yollar problemini nasıl çözeceğinizi yada bir negatif ağırlık çevrimini bulma yolunu Bellman-Ford ile biliyorsunuz.

Şimdi de fark kısıtlarını nasıl çözeceğimizi artık biliyoruz. Aslında biraz daha fazlasını yapabilirsiniz. Çünkü Bellman-Ford, fark kısıtlarını sırf çözme dışında, biraz daha fazla şey de yapıyor. Ama önce sürekli ima ettiğim şeyi yazayım. Corollary yani Doğal Sonuç; Bellman-Ford’u kullanabilirsiniz. Yani bu grafiği yaparsınız, sonra Bellman- Fordu uygularsanız, o sizin fark kısıtları sisteminizi çözer. Buraya bazı sayılar yazayım. m fark kısıtınız var. Ve, n değişkeniniz var. Bellman-Ford onları (m çarpı n) düzeyinde çözecektir.

Gerçekte bu rakamlar biraz artar çünkü n kenar ekliyoruz ve bir köşe ekliyoruz ama, tüm bu rakamların önemsiz olmadıklarını varsayarsak, m en az n’ dir. Düzeyi m çarpı n’dir. Bazılarının sıfıra yakın olduğu durumlardan kaçınmaya çalışıyorum. İyi. Ve biraz önce bahsettiğim diğer bazı gerçekler.-- Ve bunları egzersiz olarak bırakacağız, çünkü çok da gerekli değiller. İhtiyacımız olan esas şey bu. Ama Bellman-Ford ile ilgili diğer bazı güzel gerçekler: Bellman-Ford, aslında bazı hedef fonksiyonlarını optimize eder. Bazen “bu bir fizibilite problemidir. Sadece, bu kısıtların karşılanıp karşılanamayacağını bilmek istiyoruz.” deriz. Aslında belirli bir hedef fonksiyonunu ekleyebilirsiniz. Ona rastgele bir hedef fonksiyonu veremezsiniz ama, işte ilginç olan bir tanesi..

artı artı , -- ama, sadece bu kadar değil. Bazı kısıtlar da var. Pekiyi, bu bir doğrusal program. ’lerin toplamını, ’lerin pozitif olmamaları ve fark kısıtlarının olması koşuluyla, maksimize etmek istiyorum. Bu, daha önce vardı. Bu, tamam. Belli bir noktada, s ‘den her yere, en çok sıfır maliyete gidebileceğinizi gördük. Buradan, bu atamadan da tüm x_i’lerin negatif olduklarını biliyoruz. Gerekli bir bilgi değil ama, Bellman-Ford’u uyguladığınızda, bu da doğru oluyor. Yani sisteminizi diğerlerinden daha az genel olmayan Bellman-Ford’u kullanarak çözerseniz, pozitif olmayan ’ leri de elde ediyorsunuz. Ve o kısıta bağlı kalarak onları sıfıra azami yakınlıkta, L1 normunda yapıyor.

Bu değerlerin toplamını sıfıra mümkün mertebe yaklaştırıyor, değerlerini mümkün olduğunca en küçük mutlak değerler haline getirmeye çalışıyor. Ve bundan daha fazlasını da yapıyor. Pişiriyor, temizliyor, en kısa yolları buluyor. Aynı zamanda “spread”i yani yayılı hali de en aza indiriyor; i’nin tüm değerlerindeki maks. eksi, i’nin tüm değerlerindeki min. ’yi en aza indiriyor. Yani, eğer gerçek bir yolunuz varsa ve buralarda ’leriniz varsa -- bu mesafeyi en aza indiriyor. Ve sıfır da buralarda bir yerde. Böylece, x_i’ leri, mümkün olduğunca derli toplu hale getiriyor. Bu aslında L sonsuz normu, doğrusal cebir derslerinizden normlar hakkında bir şeyler biliyorsanız. Bu L1 normu. Sanırım her LP normunu en aza indiriyor.

İyi. Öyleyse, bunu bir şey için kullanalım. Evet, -- gerçek bir problem çözelim, ondan sonra bugünü bitirmiş olacağız. Gelecek derste, gerçekten çok güzel şeyler, bu şeylerin pratikteki güzel uygulamalarını göreceğiz. Şimdilik gene güzel, ancak nispeten basit bir uygulama göreceğiz. Bunun adı VLSI yerleşimi’ dır. Çok önceden VLSI’yi biraz görmüş ve böl-ve-fethet bağlamında konuşmuştuk. Pek çok yonganız var veya onlara bir çeki düzen vermek istiyorsunuz ve bazı hedefleri en küçük boyuta indirmek istiyorsunuz. VLSI serimleri yada yerleşim planlarında karşınıza tonlarca problem çıkar. İşte, bir tanesi.. Bir entegre devrenin çok sayıdaki özellikleri ile karşı karşıyasınız.

Onları birbirlerine fazla yaklaştırmadan devrenizde düzenlemek istiyorsunuz. Örneğin üst üste gelmelerini önleyecek şekilde asgari ayrımlar var. Belki aralarından iletkenlerin geçmesi için mesafe bırakmanıza yada öyle şeylere gerek var.. Yani herhangi iki parçayı çok yan yana gelmeyecek şekilde ayrı tutmaya ihtiyacınız var. Pekala, sırf bir fikir vermek için, elimde bazı parçalar var; bunun nasıl çalıştığı konusunda çok açık olmayacağım. Bazı özellikler var. Bu parçalarınız yongalar ve benzeri şeyler. Şekillerine fazla aldırmıyoruz. Sadece onları dilediğim şekilde hareket ettirebilmeyi istiyorum, böylece belli bir noktadaki boşluk -- boşluk demişken biraz bu boşluğu düşüneyim. Bu boşluğun en az birkaç delta olması lazım. Ya da, deltayı kullanmak istemiyorum, epsilon diyelim. İyi, küçük bir sayı.

Yani sadece parçalarımın arasında belli bir ayrım olmasına ihtiyacım var. Ve bu problemi basit kılmak için parçaların sadece yatay yönde kaymalarına izin verdiğimi söyleyeceğim. Öyleyse, tek-boyutlu bir problem. Bu şeyler, iki boyutlu veya ne olurlarsa olsunlar, onları sadece x ekseninde kaydıracağım. Bunu modellemek için, her parçanın sol kenarına bakacağım ve “bu iki sol kenar en azından birazcık ayrı olmalılar”, diyeceğim.

Böylece mesafe ne olursa olsun, birkaç epsilon artı olacak. Ancak, hesaplamanız gereken üç boyutlu acayip şekilleriniz varsa, bunlar aynı hizaya geldiklerinde, mesela bu çok yakın olabilir. Ancak, belli kısıtlar var, öyleyse, her iki parçanın, birbirlerine en çok ne kadar yaklaşabileceğini bilmem lazım. Çünkü birbirlerine çok da yakın olmamaları lazım. Öyle ise, buna diyorum. Buna, diyorum. Öyleyse, eksi ’lik bir kısıtımız var ve bu da en az d artı epsilon’ dur, yada o ağırlığı ne kadar hesapladıysanız.

Böylece, her çift parça için bunu yapabilirim, birbirinden ayrı durmaları gereken ölçüde belli bir kısıt hesaplarım. Şimdi bu x-koordinatlarını belirlemek istiyorum. Şimdilik onları değişken farz ediyorum. Dağınık durumdaki bu parçaları azami ölçüde derli toplu hale getirmek ve böylece yapabileceğim en küçük yonganın içine sığabilmeleri için yatay yönde kaydırmak istiyorum; çünkü bu para, zaman, enerji ve daha pek çok şeyden tasarruf demek. Yonganızın daima küçük olmasını istersiniz.

Bellman-Ford bunu sağlar. Pekala, Bellman-Ford, bu kısıtları çözümler; çünkü bunlar bir takım fark kısıtlarıdır. Ve bunların çözümlenebilir olduklarını biliyoruz çünkü parçaları dilediğimiz kadar uzaklıkta etrafa serpiştirebiliriz. Ayrıca, yayılmayı da en aza indirdiğinden ihtiyacım olan yonganın boyutunu da maks. eksi min boyutuna minimize eder. Öyleyse bu, derli topluluğu maksimize ediyor, ya da yonga boyutunu minimize ediyor. Pekala bu tek boyutlu bir program olduğundan biraz yapay gelebilir ama iki-boyutlu problemin çözümü gerçekten güçtür. Polinomsal bir algoritma ile yapabileceğinizin en iyisi budur.

Eğer multimedya ortamı gibi olayların zaman çizelgesini yapıyorsanız, başka uygulamalar da vardır ve örneğin bu audio’nun yani sesin, bu videodan en az iki saniye sonra oynamasını garanti etmek istiyorsunuz ve ayrıca aynı zamanda oynayan başka şeyler de var ve bunların birbirlerinden ayrı belli aralarda olmalarını istiyorsunuz; multimedya ortamındaki fark kısıtlarını çözümlemek ve olayı mümkün kılmak için Bellman-Ford’un kullanım yolları konusunda pek çok makale bulunmaktadır. İşte böyle.. Gelecek ders, Bellman-Ford’un tüm çiftler enkısa yollarındaki uygulamalarından başka örnekler göreceğiz. Sorular var mı? Şahane.