En geniş yol sorunu - Widest path problem
Olarak grafik algoritmaları , en geniş yol problemi bir bulma sorunudur yolu , iki belirlenmiş arasındaki köşe bir de ağırlıklı grafik yoldaki en az ağırlık kenarının ağırlığı maksimize eder. En geniş yol problemi aynı zamanda maksimum kapasite yolu problemi olarak da bilinir . En kısa yol algoritmalarını, yol uzunluğu yerine darboğaz mesafesini kullanacak şekilde değiştirerek, en geniş yolları hesaplamak için uyarlamak mümkündür . Ancak, çoğu durumda daha hızlı algoritmalar bile mümkündür.
Örneğin , İnternet'teki yönlendiriciler arasındaki bağlantıları temsil eden bir grafikte , bir kenarın ağırlığının iki yönlendirici arasındaki bağlantının bant genişliğini temsil ettiği bir grafikte , en geniş yol sorunu, iki İnternet arasında uçtan uca bir yol bulma sorunudur. Mümkün olan maksimum bant genişliğine sahip düğümler. Bu yoldaki en küçük kenar ağırlığı, yolun kapasitesi veya bant genişliği olarak bilinir. Ağ yönlendirmedeki uygulamalarının yanı sıra, en geniş yol sorunu aynı zamanda çok yönlü bir seçimin kazananına karar vermek için Schulze yönteminin önemli bir bileşenidir ve dijital birleştirme , metabolik yol analizi ve maksimum akışların hesaplanmasına uygulanmıştır .
Yakından ilgili bir problem olan minimax yol problemi veya darboğaz en kısa yol problemi , herhangi bir kenarının maksimum ağırlığını en aza indiren yolu sorar. Ulaşım planlamasını içeren uygulamaları vardır . En geniş yol problemi için herhangi bir algoritma, minimum yol problemi için bir algoritmaya dönüştürülebilir veya tam tersi, algoritma tarafından gerçekleştirilen tüm ağırlık karşılaştırmalarının anlamı tersine çevrilerek veya eşdeğer olarak her kenar ağırlığının negatifi ile değiştirilmesiyle dönüştürülebilir.
Yönsüz grafikler
Bir in yönsüz grafik , bir geniş yolu iki köşe arasındaki yol olarak bulunabilir maksimum yayılan ağaç grafik ve minimaks yol en az bir kapsayan ağacın iki köşe arasındaki yol olarak bulunabilir.
Yönlendirilmiş veya yönlendirilmemiş herhangi bir grafikte, minimum ağırlıklı kenarının ağırlığı bilindiğinde en geniş yolu bulmak için basit bir algoritma vardır: sadece tüm küçük kenarları silin ve genişlik ilk aramayı veya derinliği kullanarak kalan kenarlar arasında herhangi bir yol arayın ilk arama . Bu teste dayalı olarak , maksimum yayılan ağacı kullanmayan, yönlendirilmemiş bir grafikte en geniş s - t yolunu bulmak için doğrusal bir zaman algoritması da mevcuttur . Algoritmanın ana fikri, doğrusal zamanlı yol bulma algoritmasını grafikteki medyan kenar ağırlığına uygulamak ve ardından bir yolun olup olmamasına göre ya tüm küçük kenarları silmek ya da tüm büyük kenarları daraltmaktır. ve elde edilen daha küçük grafikte yineleme.
Fernández, Garfinkel ve Arbiol (1998) , örtüşen alanların birden fazla görüntüsünü birleştiren kompozit hava fotoğrafları oluşturmak için yönlendirilmemiş darboğaz en kısa yolları kullanır . En geniş yol probleminin uygulandığı alt problemde, iki görüntü zaten ortak bir koordinat sistemine dönüştürülmüştür ; kalan görev bir dikiş seçmektir , örtüşme bölgesinden geçen ve iki görüntüden birini diğerinden ayıran bir eğri. Dikişin bir tarafındaki pikseller resimlerden birinden kopyalanacak ve dikişin diğer tarafındaki pikseller diğer resimden kopyalanacaktır. Her iki görüntüden piksellerin ortalamasını alan diğer birleştirme yöntemlerinden farklı olarak, bu, fotoğraflanan bölgenin her parçasının geçerli bir fotoğraf görüntüsünü üretir. Bir ızgara grafiğinin kenarlarını, o kenar boyunca bir dikişin görsel olarak ne kadar belirgin olacağına dair sayısal bir tahminle ağırlıklandırırlar ve bu ağırlıklar için bir darboğaz en kısa yolu bulurlar. Daha geleneksel bir en kısa yol yerine bu yolu birleşim yeri olarak kullanmak, sistemin görüntünün bir bölümünde daha fazla görünürlüğü daha az görünürlükle takas etmesine izin vermek yerine, sistemlerinin tüm noktalarında ayırt edilmesi zor bir dikiş bulmasına neden olur. görünürlük başka yerde
İki çokgen zincir arasındaki zayıf Fréchet mesafesini bulmak için bir ızgara grafiğinin iki zıt köşesi arasındaki minimaks yol problemine bir çözüm kullanılabilir . Burada, her bir ızgara grafiği tepe noktası, her zincirden bir tane olmak üzere bir çift çizgi parçasını temsil eder ve bir kenarın ağırlığı, bir parça çiftinden diğerine geçmek için gereken Fréchet mesafesini temsil eder.
Yönlendirilmemiş bir grafiğin tüm kenar ağırlıkları pozitifse , nokta çiftleri arasındaki minimaks mesafeleri (minimaks yollarının maksimum kenar ağırlıkları) bir ultrametrik oluşturur ; tersine her sonlu ultrametrik uzay bu şekilde minimax mesafelerden gelir. Minimum yayılan ağaçtan oluşturulan bir veri yapısı , Kartezyen ağacındaki en düşük ortak ata sorguları kullanılarak, sorgu başına sabit zamanda sorgulanacak herhangi bir köşe çifti arasındaki minimum mesafenin sorgulanmasına izin verir . Kartezyen ağacın kökü, en ağır minimum yayılan ağaç kenarını temsil eder ve kökün çocukları , en ağır kenarı kaldırarak oluşturulan minimum yayılan ağacın alt ağaçlarından özyinelemeli olarak oluşturulan Kartezyen ağaçlardır . Kartezyen ağacın yaprakları, giriş grafiğinin köşelerini temsil eder ve iki köşe arasındaki minimum mesafe, en düşük ortak ata olan Kartezyen ağaç düğümünün ağırlığına eşittir. Minimum yayılan ağaç kenarları sıralandıktan sonra, bu Kartezyen ağaç doğrusal zamanda oluşturulabilir.
Yönlendirilmiş grafikler
Olarak yönlendirilmiş grafikler , en kapsayan ağaç çözeltisi kullanılamaz. Bunun yerine, birkaç farklı algoritma bilinmektedir; Hangi algoritmanın kullanılacağının seçimi, yol için bir başlangıç veya hedef tepe noktasının sabit olup olmadığına veya birçok başlangıç veya hedef tepe noktası için yolların aynı anda bulunması gerekip gerekmediğine bağlıdır.
Tüm çiftler
Tüm çiftler en geniş yol problemi, seçmenlerin adayları tercih sırasına göre sıraladığı çok yönlü seçimlerde bir kazanan seçmek için Schulze yönteminde uygulamalara sahiptir . Schulze yöntemi , köşelerin adayları temsil ettiği ve her iki köşenin bir kenarla bağlandığı tam bir yönlendirilmiş grafik oluşturur. Her kenar, bağladığı iki aday arasındaki ikili bir yarışmanın kazananından kaybedenine yönlendirilir ve o yarışmanın zafer marjı ile etiketlenir. Daha sonra yöntem, tüm köşe çiftleri arasındaki en geniş yolları hesaplar ve kazanan, tepe noktası her rakibe göre daha geniş yolları olan adaydır. Bu yöntemi kullanan bir seçimin sonuçları, Condorcet yöntemiyle tutarlıdır - tüm ikili yarışmaları kazanan bir aday otomatik olarak tüm seçimi kazanır - ancak Concorcet yönteminin kendisinin başarısız olduğu durumlarda bile genellikle bir kazananın seçilmesine izin verir. Schulze yöntemi, Wikimedia Vakfı da dahil olmak üzere birçok kuruluş tarafından kullanılmıştır .
Oylama uygulamasında ortaya çıkanlar gibi yoğun bir yönlendirilmiş grafikteki tüm düğüm çiftleri için en geniş yol genişliklerini hesaplamak için , asimptotik olarak en hızlı bilinen yaklaşım O ( n (3+ω)/2 ) zaman alır , burada ω hızlı matris çarpımı için üs . Matris çarpımı için en iyi bilinen algoritmaları kullanarak, bu zaman sınırı O ( n 2.688 ) olur . Bunun yerine, Schulze yönteminin referans uygulaması , O ( n 3 ) zaman alan daha basit Floyd-Warshall algoritmasının değiştirilmiş bir versiyonunu kullanır . İçin seyrek grafikler , sürekli yol algoritması en geniş tek kaynak uygulamak daha verimli olabilir.
Tek kaynak
Kenarlar ağırlıklarına göre sıralanırsa, Dijkstra algoritmasının değiştirilmiş bir versiyonu, belirlenmiş bir başlangıç tepe noktası ile grafikteki diğer her tepe noktası arasındaki darboğazları doğrusal zamanda hesaplayabilir. Dijkstra algoritmasının geleneksel bir versiyonuna göre hızlanmanın arkasındaki ana fikir, köşelerin bu algoritma tarafından dikkate alındığı sırayla, her bir köşeye darboğaz mesafeleri dizisinin, sıralanmış kenar ağırlıkları dizisinin monoton bir alt dizisi olmasıdır; bu nedenle, Dijkstra'nın algoritmasının öncelik sırası bir kova sırası olarak uygulanabilir : 1'den m'ye (grafikteki kenarların sayısı) sayılarla indekslenen bir dizi , burada dizi hücresi i , darboğaz mesafesinin ağırlığı olan köşeleri içerir. sıralı sırada konum i olan kenar . Bu yöntem, en geniş yol sorununun sıralama kadar hızlı bir şekilde çözülmesini sağlar ; örneğin, kenar ağırlıkları tamsayılar olarak temsil ediliyorsa, o zaman m tamsayı listesini tamsayı sıralama için zaman sınırları bu problem için de geçerli olacaktır.
Tek kaynak ve tek hedef
Berman & Handler (1987) , servis araçlarının ve acil durum araçlarının bir servis çağrısından üslerine dönerken minimax yolları kullanmaları gerektiğini önermektedir. Bu uygulamada, araç iade sürecindeyken başka bir servis çağrısı gelirse, geri dönüş süresi yanıt süresinden daha az önemlidir. Bir kenarın ağırlığının, uçtaki bir noktadan mümkün olan en uzak servis çağrısına kadar maksimum seyahat süresi olduğu bir minimax yolu kullanarak, bir hizmet çağrısının alınması ile varış arasındaki olası maksimum gecikmeyi en aza indiren bir rota planlanabilir. yanıt veren bir araç. Ullah, Lee & Hassoun (2009) , metabolik ağlardaki baskın reaksiyon zincirlerini modellemek için maximin yollarını kullanır ; modellerinde, bir kenarın ağırlığı, kenar tarafından temsil edilen metabolik reaksiyonun serbest enerjisidir.
En geniş yolların başka bir uygulaması , maksimum akış problemi için Ford-Fulkerson algoritmasında ortaya çıkar . Akışın artık ağındaki bir maksimum kapasite yolu boyunca bir akışı tekrar tekrar artırmak, maksimum akışı bulmak için gereken büyütme sayısı üzerinde küçük bir sınıra, O ( m log U ) yol açar ; burada, kenar kapasitelerinin en fazla U olan tam sayılar olduğu varsayılır . Ancak bu analiz, tam maksimum kapasiteye sahip bir yol bulmaya bağlı değildir; kapasitesi maksimumun sabit bir faktörü içinde olan herhangi bir yol yeterlidir. Bu yaklaşım fikrini Edmonds-Karp algoritmasının en kısa yol büyütme yöntemiyle birleştirmek , çalışma süresi O ( mn log U ) olan bir maksimum akış algoritmasına yol açar .
Giriş grafiğinin kenar ağırlıklarının aritmetik olarak değil, yalnızca karşılaştırılmasına izin veren hesaplama modellerinde bile, tek bir kaynak ve tek hedef ile maksimum kapasiteli yolları ve minimax yollarını çok verimli bir şekilde bulmak mümkündür. Algoritma , optimal yolun darboğaz kenarını içerdiği bilinen bir dizi S kenarını korur ; başlangıçta, S sadece grafiğin tüm m kenarlarının kümesidir . Algoritmanın her tekrarda, parçalanır S alt-kümeleri sıralı bir dizi halinde S 1 , S 2 , ... , yaklaşık eşit büyüklükte, bu bölümdeki alt kümelerin sayısı, alt kümeler arasındaki tüm bölünme noktalarının O ( m ) zamanında tekrarlanan medyan bulma ile bulunabileceği şekilde seçilir . Algoritma daha sonra grafiğin her bir kenarını, kenarı içeren alt kümenin indeksine göre yeniden ağırlıklandırır ve yeniden ağırlıklı grafik üzerinde değiştirilmiş Dijkstra algoritmasını kullanır; bu hesaplamanın sonuçlarına dayanarak, hangi alt kümelerin darboğaz kenar ağırlığını içerdiğini doğrusal zamanda belirleyebilir. Daha sonra yerini S alt kümesi tarafından S i o darboğaz ağırlığını içerecek şekilde belirlediğini ve bu yeni bir dizi ile bir sonraki yinelemesini başlatır S . S'nin bölünebileceği alt kümelerin sayısı her adımda üstel olarak artar, bu nedenle yineleme sayısı yinelenen logaritma işlevi O ( log * n ) ile orantılıdır ve toplam süre O ( m log * n ) olur . Her kenar ağırlığının bir makine tamsayı olduğu bir hesaplama modelinde, bu algoritmada tekrarlanan ikiye bölmenin kullanılması, S'nin O ( √ m )'ye bölünmesine izin veren Han & Thorup'un (2002) liste bölme tekniği ile değiştirilebilir. daha küçük setler S i tek bir adımda ve doğrusal bir genel zaman sınırına yol açar.
Öklid nokta kümeleri
Öklid düzlemindeki nokta kümeleri için minimaks yol probleminin bir çeşidi de düşünülmüştür . Yönsüz çizge probleminde olduğu gibi, bu Öklid minimaks yolu problemi, bir Öklid minimum yayılan ağacı bularak verimli bir şekilde çözülebilir : ağaçtaki her yol bir minimaks yoludur. Bununla birlikte, sadece sekme uzunluğunu en aza indirmekle kalmayıp aynı zamanda aynı atlama uzunluğuna sahip yollar arasında yolun toplam uzunluğunu en aza indiren veya yaklaşık olarak en aza indiren bir yol istendiğinde sorun daha karmaşık hale gelir. Çözüme geometrik anahtarlar kullanılarak yaklaşılabilir .
Gelen sayılar teorisi , çözülemeyen Gauss hendek sorun verip veremeyeceğini minimaks yolları sorar Gauss asal sayılar sınırlanmış veya sınırsız minimaks uzunluğu var. Sabit bir orada mevcut mu olduğu bu B noktaları her çifti için, örneğin, bu p ve q Gauss asal ile tanımlanan sonsuz Öklid nokta setinde arasında Gauss asal minimax yol p ve q en minimaks kenar uzunluğuna sahiptir B ?