Gezgin satıcı problemi

Problemimiz şöyle: Arabası ile Türkiye’yi dolaşarak satış yapan bir satış temsilcimiz var. Dolaşması gereken 40 şehir olsun. Beyefendi mümkün olan en az benzini harcayarak 40 şehri hangi sıra ile ziyaret etmelidir? Bu 1800’lerde ortaya çıkmış ünlü bir problem. Literatürde “The Travelling Salesman Problem (TSP)” olarak geçiyor.

Problemi her zaman kaba kuvvetle çözmek mümkün. “Kaba kuvvet”ten kastım, zeka kullanmadan bütün şehirlerin aralarındaki mesafeleri dikkate alarak, bütün sıralamalar arasından en düşüğünü seçmek. Ancak problemi böyle çözmek için “40 faktoriyel” işlem yapmak gerekiyor (1 x 2 x 3 x … x 39 x 40 = 8 x 10 üzeri 47 korkunç bir sayı). Dolayısıyla kaba kuvvetle çözmek süper bilgisayarlar için bile çok uzun zaman alıyor.

Gelin görün ki insanlar haritaya bir bakış atarak, en optimum çözüm olmasa bile en optimuma %97 – 98 oranında yakın bir çözümü şıp diye bulabiliyorlar. Bu da beynimizin bilgisayarlardan ne kadar farklı çalıştığının bir göstergesi.

Aynı probleme bir de şöyle yaklaşalım: Haritayı temsil eden bir elektrik devresi hazırlayalım. Üzerine 40 adet ampul yerleştirelim. Her ampulden her ampule bir bağlantı yapalım. Ama bu bağlantıya, örneğin A şehri ile B şehri arasındaki uzaklığa oranlı bir direnç yerleştirelim. Uzaklık arttıkça direnç de artsın. Bir de elektrik hangi yolu izliyor görebileceğimiz bir düzenek kuralım ve devremizi açalım. Elektronikten pek anlamıyorum ama biraz kıvrandıktan sonra bu derme çatma düzeneğin problemi %98 civarı bir verimle çözmesi gerekiyor.

Sinirsel ağlar (neural networks) dünyasına hoş geldiniz. İşte beynimiz böyle çalışıyor ve bu sayede gerçek hayat problemlerini, işimizi görecek kadar çözmekte çok başarılıyız.

Bilgisayarlar henüz tek başlarına bu kompleks problemleri verimli biçimde çözemiyorlar ama milyonlarcasını bir amaç için bir araya getirdiğimizde, büyülü sayılabilecek sonuçlar elde edebiliyoruz. Örneğin birkaç sene önce 2,6 milyar dolar karşılığında eBay’e satılan Skype (skype.com), iki kişinin internet üzerinden konuşmasını taşırken başka insanların bilgisayarlarını da kullanıyor. Daha önce Kazaa’dan tanıdığımız Skype ekibi, yine aynı neural network’lere dayanan teknolojileri ile, hepimizin bilgisayarına DVD kalitesinde televizyon programları taşımak üzereler (Joost.com).

7 Comments

  1. bu problemin çözümü bana lazım mailime yollarsanız cok yararı olur tesekkürler.

  2. burak arkadaş gibi aynen banada çok lazım çokta acil, maile atarsanız çok sevinirim…

  3. banada ayni diger arkadaslara gibi bu sorunun cevabini gonderirsen sevincemm

  4. beyler, yazıyı okusanız, çözüm için bilgisayarın bir sürü işlem yapması gerekiyor diyor. mümkün olan bütün rotaları hesaplayıp hangisi en kısaymış bakacaksınız işte.

    3 şehir olsa 6 hesaplamada bitiyor (3! = 1x2x3 = 6)
    a -> b -> c,
    a -> c -> b,
    b -> a -> c,
    b -> c -> a,
    c -> a -> b,
    c -> b -> a

  5. Bana da bu problemin çözümünü atarsanız mail olarak çok sevinirim.İyi günler.

  6. bana da gönderebilirmisiniz çok sevinirim. iyi aksamlar

  7. Merhaba,
    bu tüm durumları sinir ağları ile değil de, klasik olarak karşılaştırıp en uygun güzergahı bulmak istediğimizde hangi programları kullanmak mantıklı olur ?
    Yazılmış kod falan var mı dır?

Leave a Reply