algorithm - problems - Trayectoria óptima en un gráfico para maximizar un valor

dynamic programming pdf

Question

Estoy tratando de encontrar un algoritmo razonable para este problema:

Digamos que tenemos muchos lugares. Conocemos las distancias entre cada par de ubicaciones. Cada ubicación también tiene un punto. El objetivo es maximizar la suma de puntos mientras se viaja desde una ubicación inicial a una ubicación de destino sin exceder una determinada cantidad de distancia.

Aquí hay un ejemplo simple: Ubicación inicial: C, Destino: B, Cantidad dada de distancia: 45

Solución: ruta CAB con 9 puntos

Solo tengo curiosidad por saber si hay algún tipo de algoritmo dinámico para este tipo de problema. ¿Cuál sería el mejor enfoque o más fácil para ese problema?

Cualquier ayuda es muy apreciada.

Editar: No tiene permitido visitar el mismo lugar muchas veces.

Answer 1

EDITAR: Bajo la restricción recién agregada de que cada nodo se puede visitar solo una vez, el problema es definitivamente NP-hard a través de la reducción a la ruta de Hamilton: para un gráfico general no dirigido, no ponderado, configure todos los pesos de borde a cero y cada peso de vértice a 1 Entonces, la puntuación máxima alcanzable es n si hay una ruta de Hamilton en el gráfico original.

Por lo tanto, podría ser una buena idea buscar solucionadores de programación lineal enteros , por ejemplo familias que no están específicamente diseñadas para ser difíciles.

La siguiente solución asume que un vértice se puede visitar más de una vez y hace uso del hecho de que los pesos de los nodos están limitados por una constante.

Sea p (x) el valor del punto para el vértice xyw (x, y) sea ​​el peso de la distancia del borde {x, y} o w (x, y) = ∞ si xey no son adyacentes.

Si se nos permite visitar un vértice varias veces y si podemos suponer que p (x) <= C para alguna C constante, podríamos salirse con la siguiente recurrencia: Sea f (x, y, P) la distancia mínima tenemos que ir de xay mientras recolectamos P puntos. Tenemos

f (x, y, P) = ∞ para todos P <0

f (x, x, p (x)) = 0 para todas las x

f (x, y, P) = MIN (z, w (x, z) + f (z, y, P - p (x)))

Podemos calcular f usando programación dinámica. Ahora solo tenemos que encontrar el P más grande que

f (inicio, final, P) <= límite superior de distancia

Esta P es la solución.

La complejidad de este algoritmo con una implementación ingenua es O (n ^ 4 * C) . Si el gráfico es escaso, podemos obtener O (n ^ 2 * m * C) utilizando listas de adyacencia para la agregación MIN .