Çizgeler ve AğlarSalesman

Ş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, DNA yapısını incelerken de çözülmesi gerekiyor.

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 ${tsn2} şehir için bile ${tsn2}! = ${factorial(tsn2)} olası yol olduğunu gösterdik. Yüzlerce ya da binlerce nokta ele aldığımızda olası bütün seçeneklere bakmak çok güçlü bilgisayarlar için bile imkansız.