Supongamos que se tiene un grafo dirigido y acíclico G, y cada vértice $v$ contiene un valor (positivo) $a_v$ . Además, dejemos que $r$ sea una constante. Para mis propósitos, $r>1$ pero esto podría no importar. Dejemos que $n$ sea el número de vértices de G y que $[n]:=\{1,2,\ldots, n\}$ .
Un tipo topológico de $G$ es una biyección $G\to[n]$ tal que si hay un camino desde $v$ a $w$ entonces $\tau(v)<\tau(w)$ . Alternativamente, si vemos $G$ como la definición de un ordenamiento parcial, un ordenamiento topológico es un ordenamiento total que extiende el ordenamiento parcial.
Me gustaría encontrar $\displaystyle\min_{\tau} \sum_v a_v r^{\tau (v)}$ donde estamos tomando el mínimo sobre todas las clases topológicas de G. Puede ayudar a generalizar el problema y a encontrar $\displaystyle\min_{\tau} \sum_v a_v p({\tau (v)})$ , donde $p:[n]\to \mathbb R$ es una función de penalización/ponderación (quizás se supone que toma valores positivos y es monótona).
Hay dos casos extremos. Si $G$ no tiene aristas, ordenaríamos las cosas en orden ascendente o descendente dependiendo de si $r<1$ o $r>1$ . Si $G$ ya es un orden lineal, no hay nada que hacer. Ya, el problema parece no trivial dado dos ordenamientos lineales disjuntos, donde el problema se reduce a la baraja óptima.
¿Existe un buen algoritmo para resolver esto? Conozco algunas heurísticas que ayudan en ciertos casos, y puedo usar un algoritmo tipo burbuja para obtener mínimos "locales", pero a menos que haya una manera de refundir el problema, no veo una buena manera de resolverlo.
Añadido más tarde: Quiero ampliar mi comentario y explicar por qué considero que la programación dinámica es insuficiente. En el mejor de los casos, esto aclarará lo que busco. En el peor de los casos, esto revelará una laguna en mi comprensión que alguien puede aclarar.
Para que haya una solución de programación dinámica, es necesario que haya subproblemas sobre los que se pueda construir una solución más amplia. Por ejemplo, al buscar un camino a través de un grafo con longitudes de aristas, si un camino de longitud mínima pasa por un vértice concreto, entonces el camino desde el inicio hasta ese vértice debe ser de longitud mínima. Si llevamos la cuenta de todos los vértices a los que se puede llegar en un tiempo inferior a $t$ entonces podemos ignorar todos los caminos a través de esos vértices cercanos que no comienzan con un camino mínimo, y por lo tanto necesitamos recordar a lo sumo un camino a cualquier vértice, y en cada etapa sólo necesitamos encontrar el camino más corto a un vértice no visitado que sea una extensión de un camino mínimo conocido. Esto da como resultado $O(n^2)$ los costes de almacenamiento y $O(nm)$ costes de tiempo en los que $n$ es el número de vértices y $m$ es el número de aristas.
El subproblema obvio para el problema que nos ocupa es que, si conocemos un segmento inicial/terminal para una solución óptima, la restricción al subgrafo que contiene sólo esos elementos producirá el mismo segmento inicial/terminal. No parece que podamos decir nada más fuerte. El algoritmo que se obtiene es el siguiente:
- Selecciona todos los vértices que no tengan predecesores y coloca cada uno de ellos en una lista de segmentos iniciales admisibles.
- (Definición) Para un segmento inicial admisible de longitud $n$ decimos que una extensión de longitud $n+1$ es admisible si satisface tanto las restricciones topológicas del grafo dirigido como si ninguna inserción topológicamente permitida del nuevo elemento tiene un valor total menor. De la colección de todas las extensiones admisibles de longitud $n+1$ .
- Dada la colección de todos los segmentos admisibles de longitud $n$ forman la colección de todas las extensiones admisibles de longitud $n+1$ .
- De la colección generada en (3), si dos extensiones admisibles utilizan exactamente la misma colección de vértices, elimine el segmento con un mayor coste asociado.
- Haz un bucle en (3) y (4) hasta que hayas encontrado el segmento inicial mínimo que contenga todos los vértices del gráfico.
Si la función de penalización es monótona creciente (por ejemplo, si $r>1$ ), podemos mejorar algo el tiempo de ejecución añadiendo una heurística (el coste total de añadir todo lo demás a la mínima distancia posible, ignorando que sólo puede haber un elemento en un punto concreto), pero incluso con esta mejora, tenemos el siguiente problema fundamental:
El algoritmo no requiere comprobar cada segmento inicial, pero sí requiere examinar cada colección de vértices que podrían formar un segmento inicial admisible. En el peor de los casos, esto es exponencial en el número de vértices (aunque se reduce significativamente cuando hay severas restricciones topológicas). Además, en el peor de los casos, los requisitos de espacio son del orden de $\binom{n}{n/2}$ donde hay $n$ vértices.
El algoritmo de programación dinámica sigue siendo una gran mejora con respecto a los algoritmos más ingenuos, pero me gustaría encontrar algo que se ejecute en tiempo polinómico, o bien demostrar que tal algoritmo no puede existir.
