YBS401U-YÖNEYLEM ARAŞTIRMASI
Ünite 6: Ağ Problemleri: En Kısa Yol Problemi ve En Küçük Kapsayan Ağaç Problemi
Ağ Problemlerinde Kullanılan Terminoloji
Her bir ağ, noktalar kümesi ile bu kümedeki bazı noktaları birleştiren çizgilerden oluşmaktadır. Bu noktalara ağın düğüm noktaları veya tepe noktaları denir. Bir ağdaki düğüm noktalarını birleştiren çizgiler ise kenarlar veya arklar olarak adlandırılmaktadır. Düğüm noktaları genellikle çemberlerle gösterilir ve büyük harflerle işaretlenir. Kenarlar ise her bir kenarın birleştirdiği düğüm noktaları ile isimlendirilir.
Yönlü kenar, iki tepe noktası arasındaki kenar boyunca sadece bir yönde akışa izin veren yönlü çizgidir. Kenarın yönü okla belirtilir (→), ve AB (veya A-B) şeklinde işaretlenmiş bir kenar, yönün A noktasından B noktasına doğru yönlendirildiğini gösterir.
Yönlendirilmemiş kenar, bir kenar boyunca her iki yönde akışa izin veren çizgidir. Yönlendirilmemiş kenarlar, üzerinde ok olmayan çizgilerle veya birbirine ters yönlerde yönlendirilmiş bir çift yönlü kenarla gösterilebilir.
Yönlü ağ, sadece yönlendirilmiş kenarlardan oluşan ağa denir.
Yönlendirilmemiş ağ, sadece yönlendirilmemiş kenardan oluşan ağa denir.
İki düğüm arasındaki yönlendirilmemiş yol, düğüm noktalarını bağlayan farklı yönlendirilmemiş kenarlar dizisine denir.
Yönlendirilmiş yol, i. düğüm noktası ile j. düğüm noktası arasındaki yönlendirilmiş yol, yönleri j’ye doğru olan yönlendirilmiş kenarlar dizisine denir.
Yönlendirilmemiş yol, i. noktadan j. noktaya yönlendirilmemiş yol, yön farkı gözetmeksizin i ve j noktaları arasındaki kenarlar dizisine denir.
Döngü, başlangıç ve bitiş noktaları aynı noktada olan yola denir.
Bağlı düğüm noktaları; 2 düğüm noktası arasında, bu noktaları bağlayan en az bir yönlendirilmemiş yol varsa, bunlara bağlı düğüm noktaları denir.
Bağlı ağ; aralarında en az bir tane yönlendirilmemiş yol bulunan düğüm noktalarına bağlı düğüm noktaları denir. Tüm düğüm noktaları ikişer ikişer bağlı olan ağa, yani herhangi iki düğüm noktasının en az bir yönlendirilmemiş yol ile bağlantılı olduğu ağa bağlı ağ denir.
Ağaç; döngülerin olmadığı bir ağa ağaç denir.
En Kısa Yol Problemi: Dijkstra Algoritması
En kısa yol problemi; n tane düğüm noktası ve bu düğüm noktalarını birbirine bağlayan her bir kenara atanmış negatif olmayan maliyet değerlerine sahip bağlı ağlarda başlangıç düğüm noktasından son düğüm noktasına, toplam maliyeti en küçük kılacak yolun bulunması problemidir.
En kısa yol problemi olarak tabir edilen problemlerde her bir kenara atanan sayılar bu kenar aracılığı ile birbirine bağlanan düğüm noktaları arasındaki uzaklığı, bu iki düğüm noktası arasındaki ulaşım süresini veya ulaşım maliyetini gösterebilmektedir. Dolayısıyla en kısa yol, her zaman en kısa süreli yol olmaya bilmektedir. Benzer şekilde uzaklık veya zaman anlamındaki en kısa yol, en az maliyetli yol da olmayabilir.
Ağlar üzerinde en kısa yol problemi, aslında en kısa uzaklığa sahip yol, en kısa süreli yol veya en düşük maliyetli yol olarak da tanımlanabilecek problemlerin ortak adı olup probleme göre yorum farklılığı taşısa da çözüm yöntemi açısından bir farklılık göstermemektedir.
En kısa yol problemlerinin çözümü için çok sayıda algoritma geliştirilmiştir. Algoritmanın amacı, başlangıç düğüm noktasından son düğüm noktasına götürecek toplam en kısa uzaklığa sahip yolun bulunmasıdır. Bu algoritmaların muhtemelen en sadesi Dijkstra Algoritmasıdır.
Dijkstra Algoritması
Adım 1. Başlangıç düğüm noktasını seç, bu düğüm noktasını kalıcı kümeye al ve Adım 2’ye git.
Adım 2. Kalıcı kümeye en son alınan düğüm noktasına kalıcı kümede bulunanlar dışında bağlantısı bulunan düğüm noktalarını, bu noktalardan başlayan kenarları ve bu kenarlara karşı gelen uzaklıkları belirle. Bu yeni kenara karşı gelen uzaklık değerini, bu kenarın bağlandığı ve kalıcı kümeye alınan düğüm noktasına kadar daha önce hesaplanmış olan uzaklığa kümülatif olarak ekle. Uzaklıklar sütunundaki tüm uzaklıklar içinde en küçük uzaklığı seç. Bu uzaklığa karşı gelen düğüm noktasını kalıcı kümeye ekle, mevcut listeden bu düğüm noktasına gelen tüm diğer kenarları ve ilgili uzaklık bilgilerini kaldır ve Adım 3’e git.
Adım 3. Kalıcı kümeyi kontrol et. Eğer henüz tüm düğüm noktaları kalıcı kümeye alınmamışsa Adım 2’ye git, diğer durumda, yani eğer mevcut ağdaki son düğüm noktası da kalıcı kümeye alınmış ise algoritmayı sonlandır ve toplam en küçük uzaklığı, en son kalıcı kümeye alınan düğüm noktasına bağlanan kenarın sahip olduğu toplam uzaklık olarak belirle. Kalıcı kümeye alınan en küçük uzaklıklara sahip düğüm noktalarını sondan başa doğru sıralayarak en kısa yolu belirle.
(Kitabınızın 161 ve 163. sayfasında bulunan ÖRNEK 6.1 ve ÖRNEK 6.2’ nin çözümüne bakınız).
En Küçük Kapsayan Ağaç Problemi
Ağlar üzerinde tanımlanan ve en sık kullanılan ağ problemlerinden biri de “En Küçük Kapsayan Ağaç” Problemidir. n tane düğüm noktası ve düğüm noktalarını birbirine bağlayan her bir kenara atanmış negatif olmayan maliyet değerlerine sahip bağlı ağaçlarda en düşük maliyetli ağacın bulunması problemi şeklinde tanımlanmaktadır. Bu problemin amacı, belirlenmiş keyfi bir düğüm noktasından, ağdaki tüm düğüm noktalarına
erişim sağlanacak şekilde bir ağ oluşturmak ve bu ağı belirleyecek kenarlara atanmış uzaklıkların toplamını en küçük kılacak kapsayan ağacı bulmaktır.
En küçük kapsayan ağaç problemi ve en kısa yol probleminde toplam maliyeti en küçükleyecek şekilde belirli özelliğe sahip kenarların seçilmesi talep edilmektedir. En kısa yol probleminde bu özelliğin başlangıç ve son olarak nitelendirilen düğüm noktaları arasındaki bir yol için sağlanması istenirken, en küçük kapsayan ağaç probleminde tüm düğüm noktalarını birbirine bağlayan yollar için sağlanması istenmektedir. En küçük kapsayan ağaç problemini aşağıdaki şekilde özetleyebiliriz.
a. Size şimdilik sadece düğüm noktaları kümesi verilmekte ve kenarlar kümesi verilmemektedir, fakat bu düğümler arasındaki olası kenarlara atanmış pozitif uzaklık (veya maliyet, zaman vb.) değerleri verilmektedir. b. Herhangi iki düğüm noktasının birbirine bir yol ile bağlanmış olacağı bir ağ tasarlanmak istenmektedir. c. Yukarıdaki kısıtlar altında tasarlanması istenen bu ağın kenar uzunlukları toplamının en küçük olması amaçlanmaktadır.
Bu kısıtları sağlayacak ve n adet düğüm noktasına sahip bir ağın tasarlanabilmesi için sadece n – 1 adet kenara ihtiyaç duyulmaktadır. Bu yüzden de problemi, toplam kenar uzunluklarının en küçük olduğu bir kapsayan ağacın oluşturulması problemi olarak tanımlıyoruz.
En Küçük Kapsayan Ağaç Algoritması
Adım 1. Bize verilen düğüm noktalarından herhangi birini ve bu düğüm noktasına en yakın düğüm noktasını belirleyerek bu iki düğüm noktasını bir kenarla birleştir.
Adım 2. Henüz bağlantı kurulmamış tüm düğüm noktaları içinden, birbirine bağlanmış tüm düğüm noktalarına en kısa uzaklık değerine sahip olanı seç ve aralarındaki uzaklık değerinin en kısa olduğu düğümleri bir kenarla birleştir. Aralarındaki uzaklık değerlenin en küçük olduğu düğüm noktaları çifti birden fazla olabildiği durumlarda bu çifti keyfi olarak seçebilirsiniz. Bu seçim en iyi çözüm değerini değiştirmez ama belki alternatif en küçük kapsayan ağaç oluşmasına olanak sağlayabilir.
Adım 3. Eğer henüz bağlantı kurulmamış düğüm noktası varsa Adım 2’ye git, diğer durumda algoritmayı sonlandır: en iyi çözüm bulunmuştur.
En küçük kapsayan ağaç algoritmasının her bir iterasyonunda, henüz bağlantı kurulmamış düğüm noktaları incelenirken, problem verileri kapsamında uzaklık değerleri tanımlı olan düğüm noktaları arasından seçim yapılabilmektedir. Dolayısı ile henüz bağlantı kurulmamış düğüm noktaları içerisinden herhangi biri değil, sadece bağlantı kurulmuş düğüm noktaları ile bağlanma potansiyeli olan düğüm noktaları araştırılabilmektedir.
(Kitabınızın 167. sayfasında bulunan ÖRNEK 6.3’ ün çözümüne bakınız).
Algoritma Üzerinde Tartışma: En küçük kapsayan ağaç algoritması herhangi bir düğümden başlatılarak aralarındaki uzaklık değerinin en küçük olduğu düğüm noktasını tespit eder ve bu düğümler arasında yeni bir kenar oluşturur. Bu algoritma hakkında bölüm başında bilgi verirken de açıkladığımız gibi, en başta bize sadece düğüm noktaları ve bu düğüm noktaları arasındaki uzaklık değerleri verilmekte, fakat ağı oluşturacak kenarlar verilmemektedir. Kenarları bizim oluşturmamız gerekmektedir. Algoritma her iterasyonda tüm düğüm noktalarını “bağlantı kurulmuş” ve “henüz bağlantı kurulmamış” olarak sınıflandırıyor ve henüz bağlantı kurulmamış düğüm noktası kalmayıncaya kadar devam eder. En başta doğal olarak tüm düğüm noktaları henüz bağlantı kurulmamış sınıfta bulunmaktadır. Algoritmayı, ilk düğüm noktasını keyfi seçerek bu düğüm noktasına “en yakın”, yani uzaklık değeri en küçük olan düğüm noktasını belirleyip bu iki düğüm noktasını bir kenarla birleştirerek başlatıyoruz. Dolayısıyla ilk adımdan sonra elimizde iki tane, aralarında bağlantı oluşturulmuş düğüm noktası bulunacaktır. Bir sonraki adımda, geri kalan tüm düğüm noktaları içerisinden, bu iki (aralarında bağlantı oluşturulmuş) düğüm noktasının her birine olan uzaklık değeri en küçük olan düğüm noktası seçilip belirleniyor. Belirlenmiş olan bu düğüm noktası ona en yakın düğüm noktası ile (aralarında bağlantı bulunan iki düğüm noktasından biri ile) bir kenarla birleştiriliyor. Şimdi aralarında bağlantı bulunan elimizde üç adet düğüm noktası bulunuyor. Eğer henüz bağlantı kurulmamış düğüm noktası yoksa algoritma sonlandırılıyor, diğer durumda yukarıdaki prosedür tekrarlanıyor. Bu şekilde en küçük kapsayan ağacın oluşturulacağı garantilenmektedir.