Öklid'in en kısa yolu - Euclidean shortest path

Üç boyutlu bir Öklid uzayında en kısa yol örneği

Öklid'in en kısa yolu problem bir problemdir hesaplamalı geometri: bir dizi verildiğinde çok yüzlü bir engel Öklid uzayı ve iki nokta, hiçbir engelle kesişmeyen noktalar arasındaki en kısa yolu bulun.

İki boyutta sorun şu şekilde çözülebilir: polinom zamanı teorik zorluklara rağmen gerçek sayıların toplanmasına ve karşılaştırılmasına izin veren bir hesaplama modelinde sayısal kesinlik bu tür hesaplamaları yapmak için gerekli. Bu algoritmalar, ya en kısa yol algoritmasını gerçekleştiren iki farklı ilkeye dayanmaktadır. Dijkstra algoritması bir görünürlük grafiği engellerden türetilmiş veya (adı verilen bir yaklaşımda sürekli Dijkstra yöntem) bir noktadan diğeriyle buluşana kadar bir dalga cephesini yaymak.

Üç (ve daha yüksek) boyutta sorun şudur: NP-zor genel durumda,^[1] ancak, engel kenarlarında uygun bir nokta örneği bulma ve bu örnek noktaları kullanarak bir görünürlük grafiği hesaplaması yapma fikrine dayanan polinom zamanında çalışan verimli yaklaşım algoritmaları vardır.

Çok yüzlü bir yüzeyde kalan en kısa yolları hesaplamanın birçok sonucu vardır. S ve t olmak üzere iki nokta verildiğinde, örneğin a'nın yüzeyinde dışbükey çokyüzlü sorun, yüzeyden asla ayrılmayan ve s ile t'yi birbirine bağlayan en kısa yolu hesaplamaktır. Bu, problemin 2 boyutlu bir genellemesidir ancak 3 boyutlu problemden çok daha kolaydır.

Ayrıca, engellerin olduğu bu problemin varyasyonları vardır. ağırlıklıyani kişi bir engelden geçebilir, ancak bir engelden geçmek ekstra maliyete neden olur. Standart sorun, engellerin sonsuz ağırlığa sahip olduğu özel durumdur. Bu, ağırlıklı bölge sorunu literatürde.

Ayrıca bakınız

• En kısa yol problemi

Notlar

Referanslar

• Aleksandrov, Lyudmil; Maheshwari, Anıl; Sack, Joerg (2005), "Ağırlıklı çok yüzlü yüzeylerde yaklaşık en kısa yolların belirlenmesi", ACM Dergisi, 52: 25–53, doi:10.1145/1044731.1044733.
• Chiang, Yi-Jen; Mitchell, Joseph S. B. (1999), "İki noktalı Öklid'in düzlemdeki en kısa yol sorguları", Proc. Kesikli Algoritmalar üzerine 10. ACM-SIAM Sempozyumu (SODA 1999), s. 215–224.
• Choi, Joonsoo; Sellen, Jürgen; Yap, Chee-Keng (1994), "Yaklaşık Öklid'in 3-uzayda en kısa yolu", Proc. Hesaplamalı Geometri Üzerine 10. ACM Sempozyumu, s. 41–48, doi:10.1145/177424.177501, ISBN  0-89791-648-4.
• Hershberger, John; Suri, Subhash (1999), "Düzlemdeki Öklid'in en kısa yolları için optimal bir algoritma", Bilgi İşlem Üzerine SIAM Dergisi, 28 (6): 2215–2256, CiteSeerX  10.1.1.47.2037, doi:10.1137 / S0097539795289604.
• Kapoor, S .; Maheshwari, S. N. (1988), "Öklid'in en kısa yolu ve poligonal engellerle görünürlük problemleri için verimli algoritmalar", Proc. 4. ACM Hesaplamalı Geometri Sempozyumu, s. 172–182, doi:10.1145/73393.73411, ISBN  0-89791-270-5.
• Kapoor, S .; Maheshwari, S. N .; Mitchell, Joseph S. B. (1997), "Düzlemdeki poligonal engeller arasında Öklid'in en kısa yolları için etkili bir algoritma", Ayrık ve Hesaplamalı Geometri, 18 (4): 377–383, doi:10.1007 / PL00009323.
• Lanthier, Mark; Maheshwari, Anıl; Çuval Joerg (2001), "Ağırlıklı çok yüzlü yüzeylerde yaklaşık en kısa yolların belirlenmesi", Algoritma, s. 527–562.
• Lee, D. T.; Preparata, F.P. (1984), "Doğrusal engellerin varlığında Öklid'in en kısa yolları", Ağlar, 14 (3): 393–410, doi:10.1002 / net. 3230140304.
• Li, Fajie; Klette Reinhard (2011), Öklid En Kısa Yolları: Tam veya Yaklaşık Algoritmalar, Springer-Verlag, doi:10.1007/978-1-4471-2256-2, ISBN  978-1-4471-2255-5.
• Samuel, David; Toussaint, Godfried T. (1990), "Basit bir çokgenin dış jeodezik çapının hesaplanması", Bilgi işlem, 44 (1): 1–19, doi:10.1007 / BF02247961.
• Toussaint, Godfried T. (1989), "Basit bir çokgen içinde jeodezik özelliklerin hesaplanması" (PDF), Revue d'Intelligence Artificielle, 3 (2): 9–42.

Dış bağlantılar

• Uygulama Öklid En Kısa Yol algoritmasının KernelCAD yazılım

Bu kombinatorik ile ilgili makale bir Taslak. Wikipedia'ya şu yolla yardım edebilirsiniz: genişletmek.

Bu geometri ile ilgili makale bir Taslak. Wikipedia'ya şu yolla yardım edebilirsiniz: genişletmek.