No estoy diciendo que el siguiente es el mejor algoritmo, pero es suficiente.
Sea G el gráfico orientado a la entrada, K sea el conjunto de teclas. Para cada subconjunto S de K, defina [math] G_S [/ math] como el gráfico G sin los bordes cuyas claves faltan en S. Sea J el gráfico obtenido por la unión de [math] G_S [/ math] para todas las S posibles más las siguientes aristas entre distintas [matemáticas] G_S [/ matemáticas]: para cada clave k en un nodo v, agregamos una ventaja de v en [matemáticas] G_S [/ matemáticas] a v en [matemáticas ] G_R, [/ math] para cada par [math] (S, R) [/ math] de modo que S no contiene k y R sí. Este gráfico J obtenido de esta manera es un gráfico donde se puede obtener la ruta más corta con los algoritmos tradicionales de ruta más corta. Si se desea encontrar la ruta más corta de v a w, se debe buscar la ruta más corta desde la copia de v sin ninguna clave hasta cualquier copia de w con cualquier combinación de teclas.
El problema es que el gráfico J es exponencial en el tamaño de G. Sin embargo, dudo que uno pueda escapar de este problema. No sé si el problema es NP-duro, pero no conozco ninguna solución de tiempo polinómico para este problema.
- ¿Cuántas estructuras de datos y algoritmos necesita el desarrollador web?
- ¿Utiliza un algoritmo de búsqueda lineal la estrategia de dividir y conquistar?
- Recientemente llegué a un llamado indicador de opciones binarias del sitio web 'www.investoo.com' que afirma una tasa de éxito del 83% al predecir el resultado de las opciones binarias. ¿Es una estafa?
- ¿Puede la longitud de un comando Mathematica o Wolfram | Alpha ser una aproximación aproximada de su complejidad de Kolmogorov?
- ¿La lista vinculada es una estructura de datos estática o una estructura de datos dinámica?
Uno podría mejorar este algoritmo al no almacenar la explicidad del gráfico J. Solo hay que deducir la adyacencia de la implicidad J, que se puede hacer fácilmente accediendo a G info. Muchos nodos de J probablemente nunca serán visitados, por lo tanto, la aceleración puede ser considerable. (El algoritmo resultante obtiene una apariencia de memorización).
