English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtÇizgeler ve AğlarGezgin Satıcı Problemi
Bir defa daha ağlar ve haritalar üzerine düşünelim. Bir kargo şirketinin ürünleri
Dağıtım kamyonu her şehri ziyaret etmek zorunda, istediği sırayı izleyebilir. Köningsberg Köprüleri probleminde her çizgi üzerinden tam bir defa geçen yolları arıyorduk. Şimdiyse her noktadan tam olarak bir defa geçen yollar arıyoruz. Böyle yollara Hamilton döngüleri denir.
Tam bir çizgede Halimton döngüleri için çok fazla seçenek vardır. Aslında başlangıç noktası olarak herhangi bir noktayı seçebiliriz, ve sonra kalan şehirleri de istediğimiz sırayla seçebiliriz.
Diagram coming soon…
Diagram Coming Soon…
10 şehirli bir çizgede her Hamilton döngüsü ${tsn1} şehire uğramak zorunda. O halde
- İlk şehir için 10 seçenek var.
- Gidilecek ilk şehri seçtikten sonra geriye ikinci şehir için 9 seçenek kalıyor.
- Ardından 3. şehir için 8 seçeneğimiz var.
- Ardından 4. şehir için 7 seçeneğimiz var.
- …
- Son olarak, geriye 10. Şehir için 1 seçeneğimiz kalıyor.
Yani toplamda ${tsnPaths(10)} olası yol var. Bu çarpımı kısaca yazmanın bir yolu 10! Ya da 10 Faktöriyel.
Herhangi iki şehir arasında doğrudan bir olmayabilir, başka bir şehre uğramak gerekiyor olabilir. Bu durumda artık elimizde tam bir çizge yoktur ve eğer Hamilton döngüleri varsa onları bulmak çok daha zorlaşır.
Şimdiye kadar kimi şehirlerin daha uzakta olabileceğini göz ardı ettik. Oysa gerçek hayatta bu çok önemli bir kıstas: herhangi bir yol bulmak istemiyoruz, en kısa yolu bulmak istiyoruz. Bu sorunun adı Gezgin Satıcı Problemi. Sadece ulaşım ve taşımacılıkta değil, örneğin bilgisayarları hızlandırmak için mikroçiplerin üzerine tranzistörleri yerleştirirken de,
Basit bir yöntem olası bütün yolları hesaplamak, her birinin uzunluğunu bulmak ve en kısa olanı seçmek olabilir. Ancak daha az önce sadece
Ne yazık ki gezgin satıcı problemini çözmek için daha etkili bir algoritma yok. Onun yerine matematikçiler ve bilgisayar bilimciler iyi çözümleri bulmak için çeşitli algoritmalar geliştirdiler. Böylece en iyi çözümü bulamasak da iyi bir çözüm bulabiliyoruz. Yaklaşık çözüm sunan bu algoritmalara deneyimsel diyoruz.
Haritadaki şehirleri yeniden düzenlemeyi deneyin ve aralarındaki en kısa yolun nasıl değiştiğini gözlemleyin. Tıklayarak şehirleri kaldırabilir, ya da haritadaki boş bir yere tıklayarak (8e kadar) yeni şehirler ekleyebilirsiniz.
Açgözlü Algoritma (ya da En Yakın Komşu Algoritması) çok basit: rastgele bir şehirden başlıyorsunuz ve sırayla daha önce ziyaret etmediğiniz en yakın şehre gidiyorsunuz. Bütün şehirlere gidince duruyorsunuz.
Animation coming soon…
Açgözlü algoritma ile bulunan yolların en kısa yoldan ortalama olarak %25 daha uzun olduğu gösterilebilir.
2-Opt Algoritması rastgele bir yol ile başlar. Sonra sürekli iki çizgi seçip yerlerini değiştirince yolun kısalıp kısalmadığına bakarsınız. Herhangi çizgi ikilisini değiştirerek yolu daha kısaltamadığınızda durursunuz.
Animation coming soon…
Öyle görünüyor ki bilgisayarlardan henüz icat edilmeden çok daha önce doğa iki konum arasındaki en kısa yolu bulma sorusuna akıllıca bir çözüm geliştirmişti: karınca kolonileri.
Karıncalar besin kaynakları ve evleri arasındaki en kısa yolu bulmak istiyorlar. Yol üzerinde bıraktıkları kimyasallar ile aralarında iletişim kurabiliyorlar.
- Karınca kolonisi ilk başta pek çok kaşifi rastgele yönlerde yolluyor. Besin bulduktan sonra geri dönüyorlar ve arkalarında feromonden oluşan bir yol bırakıyorlar.
- Diğer karıncalar bu yola denk geldikleri zaman takip edip besine ulaşabiliyorlar. Dönüş yolunca onlar da feromon bırakıyorlar, böylece yol daha belirginleşiyor.
- Zaman içinde feromon buharlaşır. Yol ne kadar uzunsa karıncaların da yürümesi o kadar uzun sürüyor, böylece feromonun buharlaşmak için daha çok zamanı oluyor. Diğer yanda kısa yollar sıklıkla destekleniyorlar ve daha kalıcı oluyorlar.
Diagram coming soon…
Karınca Koloni Sistemi(KKS) algoritması bu davranışı bilgisayarlarda “sanal” karıncalar kullanarak kopyalamaya çalışıyor. Gezgin satıcı problemi için hızlı bir şekilde çok iyi çözümler bulabiliyor.
KKS algoritmasının öne çıkan bir tarafı sürekli bir şekilde çalışabilmesi ve çizgedeki gerçek zamanlı değişimlere uyum sağlayabilmesi. Bu değişimler araba kazaları, yol çalışmaları ya da bilgisayar ağları arasındaki trafik sıkışıklıkları yüzünden olabilir.
Gezgin Satıcı Problemi
Hızlı ve kesin çözüm üreten bir algoritma bulunursa bilgisayar bilimleri alanında çok ciddi sonuçları olacak: bütün NP-zor problemler için hızlı bir algoritma olduğu anlamına gelecek. Ayrıca çoğu internet güvenliği uygulamasını işe yaramaz hale getirecek, çünkü bu yöntemler kimi problemlerin bilgisayar tarafından çözülmesinin çok zor olmasına dayalı.
Ayrıca gezgin satıcı problemini çözen hızlı bir algoritma bulunursa matematik ve bilgisayar bilimleri alanındaki en ünlü açık sorulardan birisi çözülmüş olacak: P’ye karşılık NP problemi. Bu her biri $1m ödüllü olan yedi