chatkapi v2.0

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).

• Category: blog, vatan