İçeriğe atla

Gezgin satıcı problemi

Seyyar satıcı problemi yöneylem araştırması ve teorik bilgisayar bilimi alanlarında incelenen bir "kombinatorik optimizasyon" problemidir.

Tanımlama

Seyyar satıcı problemi şu şekilde tanımlanabilir:

  • Bir seyyar satıcı var;
  • Bu satıcı, mallarını şehirde satmak istiyor;
  • Öte yandan, mantıklı bir şekilde, bu satıcı bu şehirleri mümkün olan en kısa şekilde ve her bir şehre maksimum bir kere uğrayarak turlamak istiyor.

Problemin amacı, satıcıya bu en kısa yolu sunabilmektir.

Bu problem, bir matematiksel problem olarak 1930'lu yıllarda formüle edilmiştir. Optimizasyon konusunda en derin inceleme konularından biridir. "Hesaplamanın karmaşıklığı" teorisine göre çözümü NP-Tam olan en önemli algoritma problemlerinden biridir. Bundan dolayı seyyar satıcı problemlerini etkin olarak çözebilecek bir algoritma olmadığı kabul edilmektedir. Diğer bir deyimle en kötü durumda algoritma kullanılırken yapılan hesapların sayısının (yani bilgisayar kullanma zamanının) şehir sayıları arttıkça üstel olarak artması çok olasıdır. Bazı durumlarda sadece yüz şehirlik liste olmasına rağmen çözüm yapılırken çözümün yıllar alabileceği iddia edilmektedir.

Diğer optimizasyon problemlerine bir nirengi noktası ve bir mihenk taşı gibi yol gösterici ve değerleyici problem olarak kullanılmaktadır. Problem sonucunu hesaplamak, çok zor olmakla beraber hem tam sonuç hem de "sezgisel (heuristic)" sonuçlar verebilecek birçok çözüm yöntemi bilinmektedir ve pratikte bazen on binlerce şehri ihtiva eden listelerden oluşan problemlerin çözülebileceği bilinmektedir.

Çözüm

Basit bir şekilde:

  • Başlangıç için seçebileceği değişik şehir vardır
  • İlk şehirde, satıcının değişik şehir arasında seçim hakkı vardır
  • İkinci şehirde, satıcının değişik şehir arasında seçim hakkı vardır
  • vs.

Dolayısıyla, sonuç olarak satıcının değişik tur arasından seçim hakkı olacaktır. Bu, 100 şehirlik bir tur için bile değişik tur etmektedir!

Su an itibarıyla bulunabilmiş en güçlü kesin çözüm sunan algoritma (Dinamik Programlama) ile zamanda çözülebilmektedir. Örneğin, 100 şehirlik bir tur için bu adım etmektedir.

Bugüne kadar çözülen en büyük seyyar satıcı problemi 33.810 noktalı bir problemdir ve bir mikroçipin model tasarımı için çözülmüştür.[1] Bundan önceki en büyük seyyar satıcı problemi ise 24.978 noktalıdır ve İsveç'te yerleşimi olan her nokta için çözülmüştür. Bu çözüm, Intel Xeon 2,8 GHz bir işlemcinin 92 yılına denk bir sürede yapılmıştır (öte yandan, 96 bilgisayarlı bir ağ üzerinde çözüldüğünden çözülmesi 3 yıl sürmüştür). Şu anda çözülmeye çalışılan en büyük problem dünya üzerinde kayıtlı yerleşim olan her nokta için en kısa yolun ne olduğudur. Bu problem 1.904.711 şehir içermektedir.[]

Bu problem, seyyar satıcılardan öte internet üzerinde paketlerin yönlendirilmesi gibi konuların çözümünde de faydalı olacağından önemli bir problemdir.

Ayrıca bakınız

Kaynakça

  1. ^ William Cook, Daniel Espinoza, Marcos Goycoolea: Computing with Domino-Parity Inequalities for the TSP. 20 Şubat 2012 tarihinde Wayback Machine sitesinde arşivlendi. 2005. (Preprint, pdf; 261 kB)

Dış bağlantılar

İlgili Araştırma Makaleleri

P harfi "polynomial", NP harfleri ise "non-deterministic polynomial" ifadelerini temsil eder, Türkçe karşılıkları "polinom" ve "belirleyici olmayan polinom"dur. "P eşittir NP?" ise hesaplama teorisi'nin en temel ve meşhur problemidir.

Üstel zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğunun en fazla katı tane adımda çözebildiği bir problemdir. Doğal olarak, üstel zaman polinomsal zamanı içine alabilir.

<span class="mw-page-title-main">Benzetilmiş tavlama</span>

Benzetilmiş tavlama ya da benzetimli tavlama algoritması, eniyileme problemi için tasarlanmış olasılıksal yaklaşımlı bir algoritmadır. Diğer olasılıksal yaklaşımlar gibi en iyi çözümün en kısa zamanda üretimini hedefler. Bu sebeple, özellikle matematiksel modellerle çözülmesi maliyetli olan kombinasyonel eniyileme problemlerinde kullanılır. Benzetilmiş tavlama algoritması; elektronik devre tasarımı, görüntü işleme, yol bulma problemi, gezgin satıcı problemi, malzeme fizigi simulasyonu, kesme ve paketleme problemi, akış çizelgeleme ve iş çizelgeleme problemlerinin çözümlerinde başarılı sonuçlar vermiştir.

<span class="mw-page-title-main">Genetik algoritma</span>

Genetik algoritmalar, doğada gözlemlenen evrimsel mekanizmalara benzer mekanizmalar kullanarak çalışan eniyileştirme yöntemidir. Çok boyutlu uzayda belirli bir maliyet fonksiyonuna göre en iyileştirme amacıyla iterasyonlar yapan ve her iterasyonda en iyi sonucu üreten kromozomun hayatta kalması prensibine dayanan en iyi çözümü arama yöntemidir.

Matematikte matematiksel programlama, eniyileme ya da optimizasyon terimi; bir gerçel fonksiyonu minimize ya da maksimize etmek amacı ile gerçek ya da tam sayı değerlerini tanımlı bir aralıkta seçip fonksiyona yerleştirerek sistematik olarak bir problemi incelemek ya da çözmek işlemlerini ifade eder. Örneğin bu problem şöyle olabilir:

<span class="mw-page-title-main">Sırt çantası problemi</span>

Sırt çantası problemi bir klasik yöneylem araştırması ve matematiksel olarak "kombinatorik optimizasyon" problemidir. Çözüm algoritması bakımından sırt çantası problemi en ünlü NP-hard problemleri arasındadır.

Matematik biliminde, özellikle yöneylem araştırması uygulamalı dalında, doğrusal programlama problemleri bir doğrusal amaç fonksiyonunun doğrusal eşitlik ve/veya eşitsizlik kısıtlamalarını sağlayacak şekilde optimizasyon yapılmasıdır. Bir optimizasyon modeli eğer sürekli değişkenlere ve tek bir doğrusal amaç fonksiyonuna sahipse ve tüm kısıtlamaları doğrusal eşitlik veya eşitsizliklerden oluşuyorsa, doğrusal (lineer) program olarak adlandırılır. Başka bir deyişle, modelin tek-amaçlı fonksiyonu ve tüm kısıtlamaları, süreklilik gösteren karar değişkenlerinin ağırlıklı toplamlarından oluşmalıdır.

Bilgisayar bilimlerinde, sezgisel ya da buluşsal (heuristic) bir problem çözme tekniniğidir. Sonucun doğruluğunun kanıtlanabilir olup olmadığını önemsememektedir fakat genelde iyiye yakın çözüm yolları elde eder. Sezgisel algoritmalar ise geçiş süresinde daha verimli hale gelebilmek için en iyi çözümü aramaktan vaz geçerek çözüm zamanını azaltan algoritmalardır.

Mann-Whitney U testi niceliksel ölçekli gözlemleri verilen iki örneklemin aynı dağılımdan gelip gelmediğini incelemek kullanılan bir parametrik olmayan istatistik testdir. Aynı zamanda Wilcoxon sıralama toplamı testi veya Wilcoxon-Mann-Whitney testi) olarak da bilinmektedir. Bu testi ilk defa eşit hacimli iki örneklem verileri için Wilcoxon (1945) ortaya atmıştır. Sonradan, Mann and Whitney (1947) tarafından değişik büyüklükte iki örneklem problemleri analizleri için uygulanıp geliştirilmiştir.

<span class="mw-page-title-main">Sayısal analiz</span>

Sayısal analiz, diğer adıyla nümerik analiz veya sayısal çözümleme, matematiksel analiz problemlerinin yaklaşık çözümlerinde kullanılan algoritmaları inceler. Bu nedenle birçok mühendislik dalı ve doğa bilimlerinde önem arz eden sayısal analiz, bilimsel hesaplama bilimi olarak da kabul edilebilir. Bilgisayarın işlem kapasitesinin artması ile gündelik hayatta ortaya çıkan birçok sistemin matematiksel modellenmesi mümkün olmuş ve sayısal analiz algoritmaları burada ön plana çıkmıştır. 21. yüzyıldan itibaren bilimsel hesaplama yöntemleri mühendislik ve doğa bilimleri ile sınırlı kalmamış ve sosyal bilimler ile işletme gibi alanları da etkilemiştir. Sayısal analizin alt başlıklarına adi diferansiyel denklemlerin yaklaşık çözümleri ve özellikle veri biliminde önem taşıyan sayısal lineer cebir ile optimizasyon örnek gösterilebilir.

<span class="mw-page-title-main">Pergel ve çizgilik çizimleri</span>

Pergel ve çizgilik çizimi, belli uzunlukta doğrular, belli büyüklükte açılar ve diğer geometrik şekilleri çizmek için sadece ideal bir çizgilik ve pergel kullanılmasıdır.

Sayı teorisinde, asal çarpanlara ayırma bir bileşik sayının, çarpıldıklarında yine aynı sayıyı verecek şekilde, bir ve kendisi dışındaki bölenlerine ayrılmasıdır.

Matematikte, özellikle soyut cebir ve uygulamalarında, ayrık logaritma, genel logaritmanın grup kuramındaki karşılığıdır. Genel olarak bakıldığında, loga(b) ifadesi, ax = b ifadesinin gerçel sayılar kümesi içindeki çözümlerine karşılık gelir. Benzer olarak, g ve h sonlu devirli grup G'nin elemanları olduğunda, gx = h ifadesinin çözümü olan x sonuçlarına h'nin g tabanındaki ayrık logaritması denir.

<span class="mw-page-title-main">Lagrange çarpanı</span>

Optimizasyon yaparken, Lagrange çarpanı methodu, bir fonksiyonun maksimum ve minimum noktalarını bulmak için kullanılan bir yöntemdir.

<span class="mw-page-title-main">Simpleks algoritması</span>

Simpleks algoritması, doğrusal programlama problemlerinde optimum çözümü pratik olarak bulmak amacıyla George Dantzig tarafından 1947 yılında geliştirilen bir algoritmadır.

<span class="mw-page-title-main">Evrimsel hesaplama</span>

Bilgisayar bilimlerinde, evrimsel hesaplama; kullanılan algoritmaların türüne göre tanımlanabilen yapay zekanın bir alt alanıdır. Evrimsel algoritmalar olarak adlandırılan bu algoritmalar, Darwinci ilkeleri benimsemek üzerine kurulmuştur.

Bilgisayar bilimi, matematiksel modelleme ve problem çözme yaklaşımlarında köklü bir değişim geçirmektedir. İlk bilgisayar bilimcileri öncelikle ayrık matematik ile ilgilenmişlerdir. Bu dönemde grafikler, ağaçlar ve sonlu sayıda veri seti içeren diziler gibi yapılara odaklanmışlardır. Hızlı kayan noktalı işlemleri "büyük veriler" ile birlikte icra etmeye çalışmışlardır. Üç boyutlu taramanın ve diğer yoğun girdi kaynaklarının gerçeklenmesi modern bilgisayar bilimi pratisyenleri ve mühendisleri tarafından mümkün kılınmıştır. Buna paralel olarak gerçek değere yakın veriyi işlemek ve anlamak için sağlam yöntemler tasarlama ihtiyacı da doğmuştur. Bu ihtiyacın karşılanması için bilgisayar bilimcileri, özellikle ayrık matematik, çok değişkenli hesap, lineer cebir gibi alanlarda bilgi ve tecrübelerini kullanmalıdırlar.

Bilgisayar bilimi, matematik, ekonomi ve biyoinformatikte dinamik programlama karmaşık bir problemi tekrarlanan alt problemlere bölerek, her bir alt problemi yalnız bir kere çözüp daha sonra bu çözümü kaydederek karmaşık problemin çözümünde kullanma yöntemidir. Bir alt problem çözüldükten sonra tekrar çözülmesi gerektiğinde daha önce kaydedilen çözüm kullanılarak zaman kazanılır, ancak alt problemlerin kaydedileceği daha fazla alana gereksinim duyulur. Yani dinamik programlama algoritmaları alandan ödün verilerek zamandan kazanılmasını sağlar. Dinamik programlama algoritmaları optimizasyon problemlerinin çözümünde yaygın olarak kullanılır.

Kaunoslu Dionysodorus eski bir Yunan matematikçi.

Tepe Tırmanma Algoritması, yapay zeka alanındaki matematiksel optimizasyon problemleri için kullanılan sezgisel bir algoritmadır. Çok sayıda verinin girilmesi ve iyi bir sezgisel fonksiyon verildiğinde, probleme yeterince iyi bir çözüm bulmaya çalışmaktadır. Bilgisayar bilimlerinde aktif olarak kullanılmakta olan arama algoritmalarından birisidir. İki boyutlu bir grafikte en düşük noktaları arama esnasında yapmış olduğu hareket tepe tırmanmaya benzemesinden dolayı bu isimi almıştır.