Bitonik tur - Bitonic tour

Bitonik bir tur

İçinde hesaplamalı geometri, bir bitonik tur bir dizi nokta içindeki siteler Öklid düzlemi bir kapalı çokgen zincir her sitenin köşelerinden biri olduğu, öyle ki herhangi bir dikey hat zinciri en fazla iki kez geçer.

Optimal bitonik turlar

optimal bitonik tur minimum toplam uzunlukta bitonik turdur. Standart bir alıştırmadır dinamik program tasarlamak polinom zamanı optimal biytonik turu oluşturan algoritma.^[1][2] Bu şekilde çözmenin olağan yöntemi zaman alsa da ${displaystyle O (n ^ {2})}$, zamanla daha hızlı bir algoritma ${displaystyle O (nlog ^ {2} n)}$ bilinen.^[3]

Optimal biytonik turları inşa etme problemi, genellikle 1990'da birçok buluşsal yöntemin deneysel bir karşılaştırmasını yayınlayan Jon L. Bentley'e atfedilir. seyyar satıcı sorunu;^[4] ancak Bentley'in deneyleri biytonik turları içermez. Biytonik tur problemini tanımlayan ilk yayın, ders kitabının ilk baskısı olan farklı bir 1990 yayını gibi görünüyor. Algoritmalara Giriş tarafından Thomas H. Cormen, Charles E. Leiserson, ve Ron Rivest, Bentley sorunun kaynağı olarak listelendi.

Özellikleri

Optimal bitonik turda kendiliğinden kesişme yoktur, çünkü kesişen herhangi iki kenar, üçgen eşitsizliği nedeniyle daha kısa toplam uzunluğa sahip, çaprazlanmamış bir çift kenar ile değiştirilebilir.

Bitonik olmayabilecek diğer turlarla karşılaştırıldığında, optimum bitonik tur, Öklid mesafesiyle kopan bağlarla toplam yatay hareket miktarını en aza indiren tur.^[5]

Düzlemde farklı tam sayıya sahip noktalar için ${displaystyle x}$-Kordinatlar ve gerçek sayı ile ${displaystyle y}$-bir uzunluk aralığında yer alan koordinatlar ${displaystyle 2 {sqrt {2}}}$ veya daha az, en uygun bitonik tur, optimum seyahat eden satış görevlisi turudur.^[6]

Diğer optimizasyon kriterleri

En uygun biytonik turu bulan aynı dinamik programlama algoritması, seyahat eden satıcı probleminin en aza indiren diğer varyantlarını çözmek için kullanılabilir. alfabetik sırayla sabit sayıda koordinat yönündeki hareket kombinasyonları.^[5]

5'inde Bilişimde Uluslararası Olimpiyat, içinde Mendoza, Arjantin 1993'te, yarışma sorunlarından biri bitonik turları içeriyordu: yarışmacılar, bir dizi siteyi ve siteler arasında izin verilen kenarların bir koleksiyonunu girdi olarak alan bir algoritma tasarlayacak ve mümkün olduğunca çok siteyi içeren bu kenarları kullanarak bir biytonik tur oluşturacaktı. . Optimal bitonik turda olduğu gibi, bu problem dinamik programlama ile çözülebilir.^[7][8]

Referanslar