Endüstri Mühendisliği (EM)’nin en temel konularından biri olan Yöneylem Araştırması (YA)’dır. YA’yı ilginç kılan özelliği, diğer EM konuları içinde belki de disiplinler arası uygulamaların en çok başvurulduğu konu olmasıdır. Matematik modelleme, algoritma kurma becerisi ve bilgisayar bilgisinin bir araya geldiğini söylersek yanlış olmaz. Doğrusal programlama, doğrusal olmayan programlama, kuyruk modelleri (aklınıza hemen dört ayaklı dostlarımız gelmesin, market kasalarındaki bekleme kuyruklarından bahsediyoruz), ulaştırma/atama problemleri, dinamik programlama gibi farklı başlıklar altında sanayide ve günlük yaşantımızda doğrudan ya da dolaylı etkisi olan problemlerin çözümleri ile ilgilenir.
Bahsettiğim konularda uzun süreler çalışmadığımı baştan söylemek isterim, çünkü genel olarak YA çok kapsamlı, başlı başına bir doktora konusudur, hatta alt konuları bile hem teoride hem de pratikte ciddi emek ister, bu sebeple yazımda bazı yanlış ya da atlanmış noktaların bulunabileceğini belirtmek isterim. Bu konuda yazmak istememin sebebi, profesyonel çalışmalarımda biraz da zorunluluklardan dolayı, EM’nin lisans programlarında anlatılanın ötesinde hem modelleme hem matematik hem de veri yapıları açısından çözüm bulmak zorunda kaldığım problemler ile karşılaşmış olmam. Çalışmalarım sırasında konuların özellikle birden fazla disiplinin bir araya gelmesiyle daha keyifli hale geldiğini söylemem lazım. Çözümler kolay mı oldu? Tabii ki hayır. Bu tür problemlerde çözüm üretmek için ciddi boyutta zamana ve bütçeye sahip olmak, teknoloji/platform gibi unsurlarda doğru kararlar vermek gerekir. Yine de sahip olduğumuz imkanlar içinde özgün çalışmalar olduğu kanısındayım. Bu konular üzerine kafa yoran, emek veren ve neredeyse tüm akademik hayatını bunların üzerine kuran değerli insanların yanında benim ve birlikte çalıştığım iş arkadaşlarımın çabaları çok zayıf kalır. Çalışmalarından yararlandığımız akademisyenlere teşekkür ederim.
YA konuları genelde problem çeşitlerine göre matematik modelleme, algoritma kurma ve bunun için gerekli veri yapılarının tanımlanması üzerine dayanır. Örneğin ulaştırma/atama problemlerinin çözümünde ağ modellerinden ve yöntem olarak da ağ algoritmalarından (graph algorithms) yararlanılır. Ağ algoritmaları da DFS (Depth-First-Search) (Derin Öncelikli Arama), BFS (Breadth-First-Search) (Sığ Öncelikli Arama) gibi algoritmaları kullanır. Ağ algoritmaları arasında “en kısa yol (shortest-path)”, “en fazla akış (max-flow)”, “minimum maliyetli akış (min-cost-flow)” başlıklarını sayabiliriz. Yeri geldiğinde bu kavramlardan da bahsedeceğim, bir kısmı ileriki yazılarımda olabilir.
Bu yazımda işe basit kısmından başlayıp, “en kısa yol (shortest-path)” algoritmasından bahsetmek istiyorum. Bu algoritma ne için ortaya çıkmıştır? Diyelim ki yolculuk yapıyoruz, bir yerden yola çıkıp başka bir yere ulaşmak istiyoruz. Bunun için birden fazla seçeneğimiz olabilir. Örneğin arabayla İstanbul’dan yola çıkıp İzmir’e gitmek istiyoruz. Batı kesiminde sahil yolunu izleyip Balıkesir üzerinden de gidebiliriz, daha içeride kalıp Manisa üzerinden de. Normal olarak düşündüğünüzde içerideki yolu izleyerek gitmemiz gerektiğini hemen söyleyebilirsiniz. Hatta elinizde doğrudan her iki rotanın da mesafe bilgisi varsa, yol şartlarının eşit olduğunuz kabul edersek, doğrudan tek seferde içeriden gidilmesi gerektiğini kolayca söyleyebilirsiniz. Peki elimizde böyle bir veri yoksa ve ulaşmamız gereken son noktaya kadar yol üzerinde uğrayabileceğimiz noktalar ve bunların arasındaki mesafeler biliyorsa nasıl bir çözüm izleyebiliriz? Bu noktada ağ modeli denilen kavram karşımıza çıkıyor. Ağ modeli belli noktaları ve bunların arasındaki bağlantıları içeren bir veri modelidir. Noktaları istasyon, durak, havaalanı gibi varılacak ve yola çıkılacak yerler olarak kabul edebilirsiniz. Noktalar arasındaki bağlantılar da otobanları, demiryollarını ya da uçuşları ifade edebilir. Ağ modelinin görsel örneğini aşağıda görebilirsiniz.
Şemada görüldüğü gibi A, B, C gibi noktalar varılacak/yola çıkılacak noktaları, aralarındaki bağlantı çizgileri de iki nokta arasındaki ulaşım süresini gösterir. Benzerlik kurmak gerekirse, şemadaki noktaları, şehirler, havaalanları, istasyonlar, aralarındaki bağlantıları da ulaşım süresi ya da taşıma maliyeti gibi düşünebilirsiniz.
Örneğe göre A noktasından doğrudan J noktasına ya da E noktasına erişim yoktur. Bu durumda en kısa yoldan iki nokta arasındaki ulaşım nasıl hesaplanabilir? Bunun için en kısa yol algoritması çözüm olmaktadır. A ve E arasındaki ulaşımı örnek alacak olursak, A->B->E, A->C->E, A->D->E gibi üç alternatif vardır. Burada bir özelliği de belirtmekte yarar var. Bu tür ağ modellerinde bağlantıların yönlü ya da yönsüz olması durumu da problemin tanımında verilmelidir. Örnek şemada bağlantı okları yönlü olarak verilmiştir, bu durumda bahsettiğimiz üç alternatif rota sözkonusudur. Yön önemli olmasaydı, alternatiflerin sayısı da ciddi şekilde artardı, örneğin A->D->G->H->E rotası da kullanılabilirdi. Şimdilik bağlantıların yönlü olduğunu kabul edelim. Buna göre bahsettiğimiz üç rotanın hangisinin daha kısa olduğunu nasıl hesaplarız?
En kısa yol algoritması başlangıç olarak kabul edilen noktadan, ulaşılması istenen noktaya gelinceye kadar sıradaki komşu noktalara olan mesafeleri hesaplar, sonra en kısa mesafedeki komşudan devam ederek aynı hesaplamaları onun için yapar. Bu işlem hedef noktaya varılıncaya kadar devam eder. Burada önemli olan, her nokta için birikimli (kümülatif) mesafenin hesaplanmasıdır, hedef noktaya ilk seferde ulaşılması her zaman doğru sonucu vermeyebilir. Bunu daha basit bir örnek ile açıklayayım. Basit bir ağ modeli düşünün, üç noktası olsun, A, B ve C. A noktasından B’ye, oradan da C’ye varabiliyoruz. Ayrıca A noktasından doğrudan C noktasına da varılabilsin. Bu durumda A’dan C’ye ulaşmak için en kısa yol, A->C arasıdır diyebilir miyiz? A->B arası 5 saat, B->C arası 3 saat, A->C arası 10 saat ise yanıtımız hatalı olur. En kısa yol algoritmasında A’dan başlanır, A’nın komşuları olan B ve C’ye ulaşım mesafeleri hesaplanır. B (5), C (10) olur, A noktası işlenenler grubuna dahil edilir. C’ye ulaşıldığı için çözüm durdurulmaz, B’den devam edilir. B’nin komşusu C’dir, A da B’nin komşusudur (bağlantılarda yön olmasa) ancak A daha önce işlendiği için hesaba katılmaz. C’nin birikimli mesafesi tekrar hesaplanır, bu durumda C’nin yeni birikimli mesafesi, B’nin birikimli mesafesine (5), B->C arasındaki mesafe (3) eklenerek bulunur ve sonuçta 8 elde edilir. 8 değeri, C’nin o andaki birikimli mesafesinden (10) daha küçük olduğu için C’nin birikimli mesafesi 8 olarak değiştirilir. B noktası da işlenenler grubuna dahil edilir. İşlenmeyen noktalar arasında bir tek C noktası kaldığı için ve hedef nokta olduğu için çözüm sonlanır. Burada bir noktanın komşu noktalarının tek tek değerlendirilip, her biri için mesafe hesaplanmasını ve aynı işlemin sıradaki komşu noktadan devam ettirilmesini BFS (Breadth-First-Search) (Sığ Öncelikli Arama) algoritması olarak isimlendiriyoruz. Sıradaki komşu noktalardan ilkini alıp hemen onunla devam eden ve onun da ilk komşu noktasını alıp ilerleyen algoritama da DFS (Depth First Search – Derin Öncelikli Arama) olarak isimlendirilir. DFS yöntemi, ağ üzerinde bir noktadan başka bir noktaya mesafeleri dikkate almaksınız ulaşmada BFS algoritmasına göre çok daha hızlı sonuç verir. En kısa yol probleminde ise komşu noktaların her biri, hedef noktaya ulaşmada birer alternatif olduğu için ve hangisinin en kısa yol üzerinde olduğu bilinmediği için BFS yöntemini tercih etmek daha doğru olur.
Üç noktalı bir ağ modelinde çözümün iki adımda (iterasyonda) bulunması kolaydır, ancak noktalar ve aralarındaki bağlantı sayıları arttıkça problem kağıt kalemle çözümlenemeyecek kadar karmaşık hale gelir. Bunun için bilgisayar yardımıyla çözülebilen yazılım modeli kurmak gerekir. Öncelikle yazılım oluşturacak veri modeli nasıl olmalıdır? Noktalar ve aralarındaki bağlantılar nasıl ifade edilecektir?
Ağın içinde noktalar kümesi ve bağlantılar kümesi olmak zorundadır. Bağlantıları nasıl tarif edebiliriz? Her bir noktanın komşularının bilinmesi gereklidir. Bu sebeple nokta bazında bir komşu listesi tanımlamak gerekecektir. Noktaların komşu listesi, ilgili noktaya komşu olan diğer noktaları içereceğinden, bağlantı listesi de kendiliğinden tanımlanmış olur, sonuçta bir bağlantı, başlangıç ve bitiş noktası ile birlikte ifade edilir. Her bağlantı için mesafe bilgisinin saklanması gerekecektir. Her nokta için de, o noktanın birikimli mesafesi ve ek kısa yolda kendisine gelen önceki komşu noktanın numarası saklanmalıdır.
Buna göre Nokta, Komsu, Ag isimli yapılar tanımlanmıştır. Ag yapısı, nokta listesini içerir, nokta ekleme çıkarma, bağlantı ekleme çıkarma gibi metotları eklenmiştir.
Aşağıdaki program kodunda algoritmanın uygulaması verilmiştir.
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication4
{
public class Nokta
{
public int NoktaId { get; set; }
private Dictionary<int, Komsu> komsular;
public Nokta()
{
komsular = new Dictionary<int, Komsu>();
}
// En kısa yol algoritmasında bu noktaya ilk noktadan
// ulaşmanın toplam maliyetini tutar.
public double BirikimliMesafe { get; set; }
// En kısa yol algoritmasında bu noktaya hangi noktadan
// gelindiğini tutar.
public int OncekiNoktaId { get; set; }
// Noktanın komşu noktalarını tutar.
public IEnumerable<Komsu> KomsuListesi
{
get
{
return komsular.Values;
}
}
public void KomsuListesiTemizle()
{
komsular.Clear();
}
public Komsu KomsuAl(int NoktaId)
{
if (KomsuMu(NoktaId))
return komsular[NoktaId];
return null;
}
public bool KomsuMu(int NoktaId)
{
return komsular.ContainsKey(NoktaId);
}
public void KomsuEkle(int NoktaId, Komsu.KomsuYonu Yon)
{
KomsuEkle(NoktaId, Yon, 0);
}
public void KomsuEkle(int NoktaId, Komsu.KomsuYonu Yon, double mesafe)
{
if (KomsuMu(NoktaId)) return;
komsular.Add(NoktaId, new Komsu() { NoktaId = NoktaId, Yon = Yon, Mesafe = mesafe });
}
public void KomsuCikar(int NoktaId)
{
if (!KomsuMu(NoktaId)) return;
komsular.Remove(NoktaId);
}
}
public class Komsu
{
public enum KomsuYonu
{
Onceki,
Sonraki,
}
public int NoktaId { get; set; }
public KomsuYonu Yon { get; set; }
public double Mesafe { get; set; }
}
public class Ag
{
private Dictionary<int, Nokta> noktalar;
public Ag()
{
noktalar = new Dictionary<int, Nokta>();
}
public IEnumerable<Nokta> NoktaListesi
{
get
{
return noktalar.Values;
}
}
public int NoktaSayisi
{
get { return noktalar.Count; }
}
public Nokta NoktaAl(int NoktaId)
{
if (NoktaMi(NoktaId))
return noktalar[NoktaId];
return null;
}
public bool NoktaMi(int NoktaId)
{
return noktalar.ContainsKey(NoktaId);
}
public void NoktaEkle(int NoktaId)
{
if (NoktaMi(NoktaId)) return;
noktalar.Add(NoktaId, new Nokta() { NoktaId = NoktaId, BirikimliMesafe = 0 });
}
public void NoktaCikar(int NoktaId)
{
if (!NoktaMi(NoktaId)) return;
var cikarilacakNokta = NoktaAl(NoktaId);
var komsular = cikarilacakNokta.KomsuListesi;
foreach (var kom in komsular)
{
var komNokta = noktalar[kom.NoktaId];
komNokta.KomsuCikar(NoktaId);
}
noktalar.Remove(NoktaId);
}
public void BaglantiEkle(int baslangicNoktaId, int bitisNoktaId)
{
BaglantiEkle(baslangicNoktaId, bitisNoktaId, 0);
}
public void BaglantiEkle(int baslangicNoktaId, int bitisNoktaId, double mesafe)
{
if (!(NoktaMi(baslangicNoktaId) && NoktaMi(bitisNoktaId)))
return;
var basNokta = noktalar[baslangicNoktaId];
if (basNokta.KomsuMu(bitisNoktaId)) return;
var bitNokta = noktalar[bitisNoktaId];
basNokta.KomsuEkle(bitisNoktaId, Komsu.KomsuYonu.Sonraki, mesafe);
bitNokta.KomsuEkle(baslangicNoktaId, Komsu.KomsuYonu.Onceki, mesafe);
}
public void BaglantiCikar(int baslangicNoktaId, int bitisNoktaId)
{
if (!(NoktaMi(baslangicNoktaId) && NoktaMi(bitisNoktaId)))
return;
var basNokta = noktalar[baslangicNoktaId];
var bitNokta = noktalar[bitisNoktaId];
basNokta.KomsuCikar(bitisNoktaId);
bitNokta.KomsuCikar(baslangicNoktaId);
}
}
public class AgAlgoritmalari
{
private class MesafeSirala: IComparer<Nokta> {
public int Compare(Nokta x, Nokta y)
{
return x.BirikimliMesafe.CompareTo(y.BirikimliMesafe);
}
}
public void EnKisaYolHesapla(Ag ag, int baslangicNoktaId, int bitisNoktaId, List<Nokta> yol)
{
yol.Clear();
if (!(ag.NoktaMi(baslangicNoktaId) && ag.NoktaMi(bitisNoktaId)))
return;
var noktalar = ag.NoktaListesi;
// tüm birikimli mesafelere sonsuz büyüklükte değer atanıyor.
// her adımda bunlar azaltılacak.
// her noktanın önceki nokta değeri temizleniyor
foreach (var nokta in noktalar)
{
nokta.BirikimliMesafe = Double.MaxValue;
nokta.OncekiNoktaId = 0;
}
// başlangıç noktasının birikimli mesafesi sıfır yapılıyor.
var baslangicNokta = ag.NoktaAl(baslangicNoktaId);
baslangicNokta.BirikimliMesafe = 0;
var islenecekler = new List<Nokta>();
var islenenler = new HashSet<int>();
islenecekler.Add(baslangicNokta);
var siralayici = new MesafeSirala();
while (islenecekler.Count > 0)
{
var nokta = islenecekler[0];
islenecekler.RemoveAt(0);
if (islenenler.Contains(nokta.NoktaId))
continue;
islenenler.Add(nokta.NoktaId);
var komsular = nokta.KomsuListesi;
foreach (var komsu in komsular)
{
if (islenenler.Contains(komsu.NoktaId))
continue;
var komsuNokta = ag.NoktaAl(komsu.NoktaId);
double yenimesafe = nokta.BirikimliMesafe + komsu.Mesafe;
if (yenimesafe < komsuNokta.BirikimliMesafe)
{
komsuNokta.BirikimliMesafe = yenimesafe;
komsuNokta.OncekiNoktaId = nokta.NoktaId;
islenecekler.Add(komsuNokta);
}
}
// bir sonraki adıma geçmeden önce işlenecek noktaları
// birikimli mesafelerine göre sırala, en küçük
// birikimli mesafeli noktadan devam edilsin.
islenecekler.Sort(siralayici);
}
// işlenen nokta sayısı, ağdaki nokta sayısından az ise
// başlangıç ve bitiş noktaları ağda bağlantılı değildir
if (islenenler.Count < ag.NoktaSayisi)
return;
// son noktadan geri giderek çözüm yolunu üret.
var bitisNokta = ag.NoktaAl(bitisNoktaId);
yol.Insert(0, bitisNokta);
var noktaId = bitisNokta.OncekiNoktaId;
while (true)
{
var oncekiNokta = ag.NoktaListesi.FirstOrDefault(n => n.NoktaId == noktaId);
if (oncekiNokta == null)
break;
yol.Insert(0, oncekiNokta);
noktaId = oncekiNokta.OncekiNoktaId;
}
}
}
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Başladı");
// Ağ yapısında 1->2, 2->3 ve 1->3 bağlantıları olacak.
// 1->2 mesafesi 5 birim, 2->3 mesafesi 3 birim, 1->3 mesafesi 10 birimdir.
// Çözüm yolu bu değerler ile 1->2->3 şeklindedir.
// 2->3 mesafesini 6 veya daha büyük değer yaparsanız çözüm yolu
// 1->3 olarak değişir
var ag = new Ag();
ag.NoktaEkle(1);
ag.NoktaEkle(2);
ag.NoktaEkle(3);
ag.BaglantiEkle(1, 2, 5);
ag.BaglantiEkle(2, 3, 3);
ag.BaglantiEkle(1, 3, 10);
var alg = new AgAlgoritmalari();
List<Nokta> cozum = new List<Nokta>();
alg.EnKisaYolHesapla(ag, 1, 3, cozum);
Console.WriteLine("İzlenen yol");
foreach (var nokta in cozum)
{
Console.WriteLine("Nokta no: {0}", nokta.NoktaId);
}
Console.WriteLine("Bitti");
Console.WriteLine("Press any key to exit, do not search for the \"ANY\" key on keyboard :)");
Console.ReadKey();
}
}
}
Tolga Togan Düz 