Sözlük

Soldaki anahtar kelimelerden birini seçin…

Grafikler ve AğlarGezgin Satıcı Sorunu

Okuma zamanı: ~15 min
Bu sayfa otomatik olarak çevrilmiştir ve hatalar içerebilir. Çevirileri incelememize yardımcı olmak istiyorsanız lütfen iletişime geçin!

Bir kez daha ağlar ve haritalar hakkında düşünelim. Bir dağıtım hizmetinin ziyaret etmesi gerektiğini düşünün ${tsn} parsel dağıtmak için farklı şehirler. Bu şehirleri bir grafikteki köşe noktaları olarak düşünebiliriz. Tüm şehirler karayollarıyla birbirine bağlıysa, bu , yani ${tsn} × ( ${tsn} - 1)2 = ${tsn*(tsn-1)/2} toplam kenarlar.

Dağıtım kamyonu tüm şehirleri herhangi bir sırayla ziyaret etmelidir. Königsberg köprüsü probleminde her kenardan tam olarak bir tane giden yollar bulmak istedik. Şimdi her köşeyi tam olarak bir kez ziyaret eden yollar bulmak istiyoruz. Bu yollara Hamilton çevrimleri denir.

Tam grafiklerde Hamilton döngüleri için sayısız farklı olasılık vardır. Aslında, herhangi bir tepe noktasını başlangıç tepe noktası olarak seçebilir ve ardından kalan şehirlerden herhangi birini herhangi bir sırayla seçebiliriz:

Diagram coming soon…

Diagram Coming Soon…

İle bir grafikte ${tsn1} şehirlerde, her Hamilton döngüsünde ${tsn1} şehirler. Şimdi,

    Bu, toplamda, ${tsnPaths(tsn1)} olası yollar. Bu ürün için bir kısayol ${tsn1} ! veya ${tsn1} Faktöriyel .

    Başka bir şehirden geçmeden doğrudan iki şehir arasında seyahat etmenin mümkün olmayabileceğini hayal edebilirsiniz. Bu durumda artık tam bir grafiğe sahip değiliz ve eğer varsa, Hamilton döngülerinin sayısını bulmak çok daha zor hale geliyor.

    Şimdiye kadar bazı şehirlerin diğerlerinden daha uzak olabileceği gerçeğini görmezden geldik. Bununla birlikte, gerçek hayatta bu çok önemli bir husustur: sadece bir yol bulmak istemiyoruz, aynı zamanda en kısa yolu bulmak istiyoruz. Buna Gezgin Satıcı Sorunu denir. Sadece nakliye ve lojistikte değil, aynı zamanda transistörleri mikroçiplere yerleştirirken, daha hızlı bilgisayarlar yapmak için veya DNA'nın yapısını analiz ederken de çözülmelidir.

    Basit bir yöntem, olası tüm yolları denemek, her birinin uzunluğunu bulmak ve sonra en kısa olanı seçmek olacaktır. Ancak, bunu ${tsn2} şehirler var ${tsn2} ! = ${factorial(tsn2)} olası yollar. Yüzlerce veya binlerce köşe noktasına sahip olduğunuzda, güçlü bilgisayarlar kullanarak bile tüm olası yolları denemek imkansız hale gelir.

    Maalesef, seyahat eden satıcı problemini çözmek için daha etkili bir algoritma yoktur. Bunun yerine, matematikçiler ve bilgisayar bilimcileri, en iyisi olmasalar bile, iyi çözümler bulan çeşitli algoritmalar geliştirdiler. Sadece yaklaşık çözümler veren bu algoritmalara Sezgisel denir.

    Bu haritadaki şehirleri yeniden düzenlemeyi deneyin ve aralarındaki en kısa yolun nasıl değiştiğini izleyin. Şehirlere dokunarak onları kaldırabilir ve haritada herhangi bir yeri tıklayarak (8'e kadar) şehirler ekleyebilirsiniz:

    Açgözlü Algoritma (veya En Yakın Komşu Algoritması) çok basittir: rastgele bir şehirde başlarsınız ve art arda daha önce ziyaret etmediğiniz en yakın şehre taşınırsınız. Tüm şehirleri ziyaret ettikten sonra durursunuz.

    Animasyon çok yakında…

    Açgözlü algoritmayı kullanarak bulunan yolların ortalama olarak mümkün olan en kısa yoldan% 25 daha uzun olduğunu gösterebilirsiniz.

    2-Opt Algoritması rastgele olası bir yolla başlar. Sonra tekrar tekrar iki kenar seçin ve yolun uzunluğunu azaltacaksa onları takas edin. Herhangi bir kenar çiftini değiştirerek uzunluğu daha fazla azaltamayacağınız zaman durursunuz.

    Animasyon çok yakında…

    Bilgisayarların var olmasından çok önce, Doğa'nın farklı konumlar arasında en uygun yolları bulmanın akıllı bir yolunu bulduğu ortaya çıktı: karınca kolonileri.

    Karıncalar yuvaları ile olası gıda kaynakları arasında mümkün olan en kısa yolları bulmak ister. İzleri boyunca bıraktıkları ve diğer karıncaların takip edebileceği kimyasallar aracılığıyla birbirleriyle iletişim kurabilirler.

    • Karınca kolonisi başlangıçta rastgele yönlere giden birçok izci gönderir. Yiyecek bulduklarında, bir feromon izi bırakarak geri dönerler. * Diğer karıncalar bulduklarında bir yolu takip etme eğilimindedir ve bu da onları yeme yönlendirir. Dönüş yolculuğunda daha fazla feromon biriktirir, böylece izi güçlendirir. * Zamanla feromon buharlaşır. Bir yol ne kadar uzun olursa, karıncalar boyunca seyahat etmek o kadar zaman alır ve bu nedenle feromonun buharlaşması için daha fazla zaman olur. Öte yandan, kısa yollar daha hızlı bir şekilde güçlendirilebilir, böylece güçleri daha hızlı artar.

    Diyagram çok yakında…

    Karınca Kolonisi Sistemi (ACS) algoritmaları, bu davranışı birçok "sanal" karınca kullanarak bilgisayarlarda kopyalamaya çalışır. Seyahat eden satıcı sorunu için hızlı bir şekilde çok iyi çözümler bulabilirler.

    ACS algoritmalarının özellikle kullanışlı bir özelliği, sürekli olarak çalışabilmeleri ve grafikteki değişikliklere gerçek zamanlı olarak uyarlanabilmeleridir. Bu değişikliklere, trafik kazaları ve sokak ağlarındaki yol kapanmaları veya bilgisayar ağlarındaki web sunucularına yönelik trafik artışları neden olabilir.

    Gezgin Satıcı problemi NP-zordur , yani bilgisayarlar (en azından çok sayıda şehir için) tarafından çözülmesi çok zordur.

    Hızlı ve kesin bir algoritma bulmanın bilgisayar bilimi alanında ciddi etkileri olacaktır: bu, NP zorluğu olan tüm problemler için hızlı algoritmalar olduğu anlamına gelir. Ayrıca, İnternet güvenliğinin çoğunu işe yaramaz hale getirir, bu da bazı sorunların bilgisayarlar için çok zor olduğuna inanılır.

    Gezgin Satıcı problemini çözmek için hızlı bir algoritma bulmak, matematik ve bilgisayar bilimlerindeki en ünlü açık problemlerden birini, P vs NP problemini de çözecektir. Her biri 1 milyon dolar ödül alan yedi Milenyum Ödül Probleminden biridir.