Lo que le interesa se llama optimización multi-objetivo , en su caso, de ruta en un gráfico.
La cuestión es que, cuando los pesos de los bordes son vectores en lugar de escalares, puede haber más de una ruta óptima. Por ejemplo, deje que el peso de una ruta sea [matemática] \ izquierda (5,7 \ derecha) [/ matemática] y el peso de otra sea [matemática] \ izquierda (3,8 \ derecha) [/ matemática]. No puede saber cuál es “más óptimo” hasta que agregue alguna métrica adicional.
Entonces, aquí es donde entran los nuevos términos.
- ¿Cómo funciona el algoritmo OKCupid?
- ¿Cómo podemos verificar si un punto (digamos el origen) se encuentra en un casco convexo 6-D (o ND) y qué tan lejos está el punto de cualquiera de los lados (facetas) del casco convexo?
- ¿Qué área de finanzas NO se externalizará a computadoras y algoritmos en el futuro?
- Cómo insertar datos de matriz en una base de datos
- ¿Las personas aprenden algoritmos antes de aprender JavaScript?
Llamemos criterios de los componentes del vector de peso de la ruta y digamos que la ruta [math] \ gamma_1 [/ math] es mejor que la ruta [math] \ gamma_2 [/ math] por algún criterio si el componente de [math] \ gamma_1 [/ math] (correspondiente a ese criterio) es menor que el componente correspondiente de [math] \ gamma_2 [/ math]. (Supongo que esta es una terminología informal, pero hace que las cosas sean más fáciles de explicar).
Una ruta [matemática] \ gamma ^ 0 [/ matemática] se llama Slater óptimo si no hay una ruta que sea mejor que [matemática] \ gamma ^ 0 [/ matemática] en todos los criterios simultáneamente. Una ruta [math] \ gamma ^ * [/ math] se llama Pareto óptimo si cada ruta que es mejor que [math] \ gamma ^ * [/ math] por un criterio es peor por otro. Si un camino es óptimo de Pareto, también es óptimo Slater.
En la siguiente imagen, los pesos de los caminos óptimos de Pareto se muestran como puntos verdes, mientras que los pesos de Slater óptimos, pero no los caminos óptimos de Pareto, se muestran como puntos amarillos. Los puntos verdes forman el conjunto de Pareto, los puntos verdes y amarillos juntos forman el conjunto de Slater.
Los algoritmos que resuelven el problema de encontrar una ruta óptima en un gráfico con pesos vectoriales se pueden dividir en dos grupos: los que encuentran todas las decisiones óptimas y los que encuentran algunas de las decisiones óptimas.
Lo que otras respuestas sugieren se llama método de convolución (al menos en Rusia, donde estudio). Utilizándolo, puede encontrar algunas de las soluciones óptimas de Slater . Básicamente, selecciona una función que transforma los pesos de los vectores en pesos escalares. Luego, puede usar el algoritmo de Dijkstra con esos pesos escalares, como de costumbre. Dependiendo de los parámetros de la función, obtienes varias soluciones. Sin embargo, hay algunos matices.
En primer lugar, existe una regla general de que el método de convolución que seleccione debe corresponder con la forma en que calcula los criterios de una ruta conociendo los pesos de sus bordes. Dejame explicar.
Por ejemplo, si el significado de un criterio es la distancia total recorrida, entonces es un criterio adicional y se suman los pesos de los bordes (lo mismo para el tiempo total pasado en la carretera). Si todos los criterios son adicionales, el método correspondiente se llama convolución lineal : el peso escalar se calcula como una combinación lineal de los componentes del peso del vector. Hablando formalmente, si [math] W (\ gamma) \ in [/ math] [math] \ mathbb {R} ^ n [/ math] es el peso vectorial, entonces el peso escalar se calcula así:
[matemáticas] Q (\ gamma) = [/ matemáticas] [matemáticas] \ sum \ limits_ {i = 1} ^ n \ lambda_i W_i (\ gamma), ~ \ lambda_i \ ge [/ matemáticas] [matemáticas] 0, ~ [/ math] [math] \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1 [/ math].
Sin embargo, ¿qué sucede si desea elegir la ruta menos peligrosa, y los pesos de los bordes representan cuán peligrosa es esa parte de una ruta? Luego, en lugar de sumar pesos, debe seleccionar el más grande para representar todo el camino. Esto se llama criterio de tipo máximo . Si todos los criterios son de tipo máximo, la convolución correspondiente se ve así:
[matemáticas] Q (\ gamma) = \ max \ limits_ {i = 1,…, n} \ lambda_i W_i (\ gamma), ~ [/ matemáticas] [matemáticas] \ lambda_i \ ge [/ matemáticas] [matemáticas] 0 , ~ [/ math] [math] \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1 [/ math].
Si utiliza un método de convolución no correspondiente, el principio de optimización de Bellman, que utiliza el algoritmo de Dijkstra, no se cumplirá, y los resultados podrían no tener ningún sentido.
Otro problema es que, dependiendo del problema, puede haber soluciones óptimas (incluso óptimas de Pareto) que no podrá encontrar sin importar cómo elija los parámetros [math] \ lambda_i [/ math].
Ahora voy a hablar sobre una generalización del algoritmo de Dijkstra que encuentra todas las rutas óptimas de Pareto . Supongo que no es útil para la programación, ya que debe tener una complejidad ridícula (desafortunadamente, la fuente no lo menciona, así que no puedo decir exactamente cuán complejo es), por lo que si no te gustan las cosas teóricas, es posible que quieras para dejar de leer aquí (en ese caso, gracias por su atención).
UPD: En los comentarios, Timothy Johnson afirma que encontrar todas las rutas óptimas de Pareto en un problema NP-completo .
Esta generalización fue propuesta en 1996 por Stanislav Gorodetsky, PhD en Física y Matemáticas, quien ha trabajado como profesor asociado en la Universidad Estatal de Nizhny Novgorod (Rusia) desde 1993. No voy a dar una descripción formal (es difícil entender en un intento), pero en su lugar voy a decir qué hay que cambiar en el algoritmo clásico de Dijkstra para generalizarlo:
- En lugar de una marca escalar, cada vértice ahora tiene múltiples marcas vectoriales, cada una de las cuales es un peso de la ruta óptima de Pareto hacia ese vértice. Algunas partes de las marcas de vértice pueden ser finales, mientras que otras no.
- Para poder “recordar” las rutas óptimas, para cada marca (pero la inicial) uno necesita almacenar el borde que conduce a su vértice y la marca de un vértice anterior utilizado para calcularlo (suena un poco complicado, pero espere por ejemplo, aclarará las cosas).
- Las marcas se vuelven finales si están en el subconjunto Pareto del conjunto formado por todas las marcas no finales y todas las marcas de un vértice final. Todas las marcas “recientemente finales” se utilizan como punto de partida para la próxima iteración.
Bien, veamos un ejemplo, ¿de acuerdo? Este es nuestro gráfico (el vértice más a la izquierda es un punto de partida, el más a la derecha es un punto final):
Las marcas finales tendrán fondo gris, las marcas “recientemente finales” tendrán fondo rosa. El color de la marca es el mismo que el del borde que lo conduce, y el índice es su marca “principal”.
En la iteración cero , hacemos la marca inicial [math] \ left (0, 0 \ right) [/ math] y la marcamos como final. Esto es lo que sucede en la primera iteración :
Subconjunto de Pareto [math] \ mathscr {P} = \ {\ left (1,2 \ right), ~ \ left (5,1 \ right) \} [/ math], por lo que esas marcas se vuelven finales. Segunda iteración :
Observe cómo se olvida la marca [matemáticas] \ izquierda (4,6 \ derecha) [/ matemáticas] porque es peor que [matemáticas] \ izquierda (3,5 \ derecha) [/ matemáticas] por ambos criterios. Subconjunto de Pareto [matemáticas] \ mathscr {P} = \ {\ left (3,5 \ right), ~ \ left (4,4 \ right), ~ \ left (7,3 \ right) \} [/ math] . Tercera iteración:
Mark [math] \ left (7,3 \ right) [/ math] no forma uno nuevo, ya que será peor según todos los criterios que los existentes. Subconjunto de Pareto [math] \ mathscr {P} = \ {\ left (3,6 \ right) \} [/ math]. Cuarta iteración :
Mark [math] \ left (3,6 \ right) [/ math] tampoco forma uno nuevo. Después de esta iteración, todas las marcas son finales. Entonces tenemos 3 soluciones óptimas de Pareto:
Si tiene alguna pregunta, hágala en los comentarios y haré todo lo posible para responderle. ¡Gracias por leer!
