Encuentra la ruta mínima en un árbol con nodos multivalor

Question

Mis clases de matemáticas están muy atrasadas, y actualmente estoy luchando por encontrar una solución decente para un problema que tengo: tengo un árbol, en el que los nodos son acciones, y están "ponderados". de acuerdo con múltiples criterios: el costo de dicha acción, el tiempo que tomará, los recursos necesarios, la perturbación, etc ...

Y quiero encontrar en este árbol el camino que minimice tanto el costo Y el tiempo, por ejemplo, como la perturbación, el costo Y el tiempo, etc. Mi problema es que no tengo idea de cómo hacerlo, excepto al crear una función de costo global F (costo, tiempo, recursos, ...), y aplicar un algoritmo de recorrido de árbol regular usando el resultado de F (...) como mi único peso. Pero entonces, ¿cómo se me ocurre F? Algo como " F (costo, tiempo, recursos) = a * cost + b * time + c * resources " se siente muy "no profesional" ...

Editar:

Quería evitar la palabra " summing " Como no estaba seguro de que fuera realmente el camino a seguir, pero en esencia, eso es lo que estoy haciendo: calcular el costo total para cada " ruta " o " rama " eso va desde ese nodo superior, a una de las hojas, y seleccionando la ruta " " o " rama " Eso minimiza el costo. El problema es que cada nodo tiene un peso basado en el tiempo necesario, en el costo financiero, en el uso de recursos, etc.

Parece inevitable tener que encontrar una fórmula, como dice Stephan, que reducirá todos estos parámetros a un costo global, por nodo, que luego puedo sumar a través de los nodos a medida que viajo por el árbol y selecciono el camino que minimiza el costo total.

Entonces, supongo que mi pregunta es realmente, ¿existe una metodología para elegir esa función?

Gracias por sus respuestas y comentarios, ahora estoy empezando a ser un poco más claro.

Answer 1

Digamos que tenemos cuatro pares (x, y) como (1, 4), (1, 5), (2, 3), (3, 3). Ahora desea minimizar " tanto x como y " ;. ¿Qué quieres decir? Si minimizas primero x y luego y terminas con (1, 4). Si minimizas primero y y luego x encuentras (2, 3).

A menos que elija una función de costo global F (x, y), como en su observación, no puedo ver ningún significado de " ambos " ;. (De todos modos, una vez que se elige F, todavía puede haber múltiples puntos mínimos). Por cierto, en mi opinión, una combinación lineal (los multiplicadores positivos a, b, c, entendidos como "pesos") no es "no profesional" en absoluto, al menos si no tiene idea de cuál podría ser una función de costo más adecuada.

Editar:

  

Parece inevitable tener que encontrar una fórmula, como dice Stephan, que reducirá todos estos parámetros a un costo global, por nodo, que luego puedo sumar a través de los nodos a medida que viajo por el árbol y selecciono el camino que minimiza el costo total.

Precaución. De hecho, esta estrategia tiene sentido solo si F es lineal. Seguramente el costo, el tiempo, los recursos, etc. son funciones aditivas, en el sentido de que tiempo (nodo1 - > nodo2 - > nodo3) = tiempo (nodo1) + tiempo (nodo2) + tiempo (nodo3), pero en general esto no es el caso de F, a menos que sea lineal. (es decir, F (costo (nodo1 - > nodo2)) = F (costo (nodo1) + costo (nodo2))! = F (costo (nodo1)) + F (costo (nodo2)).

Si elige una función de costo global no lineal, la estrategia correcta es calcular, para cada nodo, el costo total, el tiempo total, los recursos totales desde la raíz a ese nodo y calcular (y luego minimizar) F solo para el terminal nodos.

Answer 2

Subir con F es lo más importante. Si le puedo dar 6 costos y 5 veces o 5 veces y 6 costos, ¿cuál prefiere? Su función de costo debe tener eso en cuenta. Desafortunadamente, no hay un algoritmo que pueda resolver ese problema por usted. Lo negué durante una semana antes de sentarme y escribir F para una aplicación de optimización en la que estaba trabajando. En el peor de los casos, deje los parámetros para que el usuario juegue con ellos.

Answer 3

¿Por qué no funcionaría un algoritmo normal de búsqueda de gráficos como A * ?

Para la función de costo de ruta, podría usar la suma acumulada de los criterios relevantes. La distancia a la meta es más difícil ...

podría ser la distancia a la hoja más cercana, previamente calculada para todos o algunos nodos, aunque eso suene muy caro. Dependiendo de la estructura de su árbol, podría llegar a una subestimación más barata, si está perfectamente equilibrada, por ejemplo, es trivial.