Problema del camino más largo
- Problema del camino más largo
-
Problema del camino más largo
En teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima. A diferencia del problema del camino más corto, que se puede solucionar en tiempo polinómico en grafos sin ciclos negativos, este problema es NP-completo, lo que quiere decir que la solución óptima no se puede encontrar en tiempo polinómico a menos que P=NP.
El problema del camino más largo tiene una solución de programación dinámica eficiente en un grafo dirigido acíclico utilizando selección topológica. También se puede solucionar en un grafo dirigido acíclico invirtiendo los pesos y utilizando el algoritmo de Bellman-Ford(este enfoque no funciona en general porque crea ciclos de peso negativo).
Wikimedia foundation.
2010.
Mira otros diccionarios:
Problema del ángel — Saltar a navegación, búsqueda La región azul de puntos indica a dónde podría ir un ángel de poder 3. El problema del ángel es un problema perteneciente a la Teoría de Juegos, propuesto por John Horton Conway.[1 … Wikipedia Español
Problema de los caminos más cortos — Saltar a navegación, búsqueda Ejemplo de Grafo Ponderado En la Teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las… … Wikipedia Español
Largo — (Del lat. largus, abundante.) ► adjetivo 1 Que tiene mucha longitud: ■ este año se llevan las faldas largas; escogió el camino más largo. SINÓNIMO extenso luengo ANTÓNIMO corto 2 Que tiene una longitud excesiva: ■ esta cama es larga para este… … Enciclopedia Universal
Estado del bienestar — Para otro concepto similar pero diferenciado en su origen y uso en la bibliografía, véase Estado social. Estado del bienestar o Estado providencia (en inglés welfare state) es un concepto de las ciencias políticas y económicas con el que se… … Wikipedia Español
Comisión del Papaloapan — Para otros usos de este término, véase Papaloapan. Comisión del Papaloapan Acrónimo CODELPA … Wikipedia Español
Guerra del Chaco — Teatro de operaciones militares entre Bolivia y el Paraguay Fecha Septiembre de 1932 a junio de 1935 … Wikipedia Español
Herrera del Duque — Para otros usos de este término, véase Herrera (desambiguación). Herrera del Duque … Wikipedia Español
Programa del transbordador espacial — Este artículo se refiere a los transbordadores espaciales estadounidenses. Existió un proyecto cancelado de transbordador espacial ruso, cuyas características pueden consultarse en Transbordador Buran, y otro proyecto cancelado de transbordador… … Wikipedia Español
Historia de la Puerta del Sol — Aspecto actual de la Puerta del Sol … Wikipedia Español
Historia del Imperio bizantino — Esta página o sección está siendo traducida del idioma francés a partir del artículo Histoire de l Empire byzantin, razón por la cual puede haber lagunas de contenidos, errores sintácticos o escritos sin traducir. Puedes colaborar con… … Wikipedia Español
