Problema del camí més curt de Euclides

El problema del camí més curt de Euclides és un problema en geometria computacional: donat un conjunt d'obstàculs polièdrics en un espai Euclídeo, i dos punts, trobar el camí més curt entre els punts que no es interseque en cap dels obstàculs.

En dos dimensions, el problema pot resoldre's en temps polinòmic en un model de computació que permeta sumar i comparar número real, a pesar de les dificultats teòriques que implica la precisió numèrica necessària per a realisar dits càlculs. Estos algoritmes es basen en dos principis diferents, ya siga realisant un algoritme que done el camí més curt com l'algoritme de Dijkstra en un grafo de visibilitat derivat dels obstàculs o propagant un front d'ona des d'un dels punts fins que es troba en l'atre.

En tres dimensions (i majors) el problema és NP-Hard en el cas general, pero existixen algoritmes d'aproximació eficients que s'eixecuten en temps polinomial basats en l'idea de trobar una mostra adequada de punts en les vores dels obstàculs i realisar un càlcul gràfic de visibilitat utilisant estos punts de mostra.

Hi ha molts resultats en el càlcul de les trayectòries més curtes que permaneixen en una superfície polièdrica. Daus dos punts s i t, digam en la superfície d'un poliedre convexo, el problema és calcular el camí més curt que mai ixca de la superfície i conecte s en t. Esta és una generalisació del problema de 2 dimensions pero és molt més fàcil que el problema de 3 dimensions.

Ademés, hi ha variacions d'este problema, a on els obstàculs són pesats, és dir, un pot passar a través d'un obstàcul, pero açò té un cost extra per a passar a través eixe obstàcul. El problema estàndar és el cas especial en el que els obstàculs tenen un pes infinit. Açò es denomina el problema de la regió pesada.

Vore també

• Problema del camí més curt

Referències

• .
• .
• .
• .
• .
• .

• .
• .
• .
• .
• .