Coste mínimo fuertemente conectado dígrafo

StackOverflow https://stackoverflow.com/questions/1536067

Pregunta

Tengo un dígrafo que está fuertemente conectado (es decir,hay un camino de i a j y j a i para cada par de nodos (i, j) en el gráfico G).Deseo encontrar un grafo fuertemente conectado fuera de este gráfico, tal que la suma de todas las aristas es lo de menos.

Para decirlo de otra manera, tengo que deshacerme de los bordes, de tal manera que después de la eliminación de ellos, el gráfico aún fuertemente conectados y de menor coste para la suma de los bordes.

Creo que es NP duro problema.Estoy en busca de una solución óptima, no aproximación, para un pequeño conjunto de datos como 20 nodos.

Editar

Una descripción más general:Dado un grap G(V,E) encontrar un grafo G'(V,E') tal que si existe un camino de v1 a v2 en G que también existe un camino entre v1 y v2, en G' y la suma de cada una de las ie en E' es la menos posible.así que sus similares a la búsqueda de un mínimo equivalente gráfico, sólo que aquí queremos minimizar la suma de borde de pesos más que la suma de los bordes.

Editar:

Mi enfoque hasta ahora:Pensé en la solución usando TSP con varias visitas, pero no es correcto.Mi objetivo aquí es para cubrir cada ciudad, pero con un coste mínimo de ruta.Así, se parece más a la cubierta de establecer problema, supongo, pero no estoy exactamente seguro.Estoy requerida para cubrir cada una y cada ciudad con las rutas cuyo costo total es mínimo, por lo que la visita ya visitó caminos varias veces no se suman a los costos.

¿Fue útil?

Solución

Su problema se conoce como expansión mínimo fuerte sub (di) gráfico (MSSS) o, más generalmente, un coste mínimo sub abarca (di) gráfico y es NP-duro de hecho . Ver también otro libro: página 501 y página 480

Me gustaría empezar con la eliminación de todos los bordes que no satisfacen la desigualdad triangular - se puede quitar un borde -> C si va a -> b -> c es más barato. Esto me recuerda a TSP, pero no sé si eso conduce a ninguna parte.

Mi respuesta anterior era utilizar el href="http://en.wikipedia.org/wiki/Edmonds%27s_algorithm" rel="nofollow noreferrer"> Chu-Liu algoritmo Arborescence problema; como Kazoom y ShreevatsaR señalaron, esto no ayuda.

Otros consejos

Me gustaría probar esto en una dinámica de programación tipo de camino.

0 - colocar el gráfico en una lista

1 - hacer una lista de los nuevos subdiagramas de cada gráfico en la lista anterior, donde se quita uno de borde diferentes para cada una de las nuevas subdiagramas

2 - eliminar duplicados en la lista de nuevo

3 - quitar todos los gráficos de la nueva lista que no están fuertemente conectados

4 - comparar la mejor gráfica de la nueva lista con el actual mejor, si es mejor, establecer nuevos actual mejor

5 - si la nueva lista está vacía, la mejor es la solución, de lo contrario, recurse/loop/goto 1

En Lisp, tal vez podría tener este aspecto:

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

Las definiciones de strongly-connected, list-subgraphs-1, digraph-equal, best, y better se deja como ejercicio para el lector.

Este problema es equivalente al problema descrito aquí: http: // www .facebook.com / carreras / puzzles.php? puzzle_id = 1

Pocas ideas que me ayudaron a resolver el famoso rompecabezas facebull:

paso de preprocesamiento:

  1. poda: eliminar todos los bordes a-b si hay más barato o que tiene el mismo costo camino, por ejemplo:. A-c-b

  2. descomposición Gráfico: se puede resolver subproblemas si el gráfico tiene puntos de articulación

  3. Combinar vértices en un vértice virtual si sólo hay un borde saliente.

paso de cálculo:

  1. Obtener solución aproximada usando el TSP dirigida con visitas repetidas. Utilice Floyd Warshall y luego resolver Asignación problema O (N ^ 3) utilizando el método húngaro. Si conseguimos una vez ciclo - que está dirigido solución de TSP, si no - rama de uso y TSP encuadernado. Después de que tenemos el valor límite superior -. El ciclo de los costes mínimos

  2. Solución exacta - rama y el enfoque ligado. Eliminamos los vértices de ciclo más corto y tratar de construir el gráfico fuertemente relacionado con un menor coste, que cota superior.

Eso es todo amigos. Si desea probar sus soluciones - probarlo aquí: http://codercharts.com/puzzle/caribbean-salesman

Parece que desea utilizar el Dijkstra algoritmo

Parece que lo que básicamente quiere es una solución óptima para el viajante, donde se permite que los nodos a visitar más de una vez.

Editar:

Hmm. ¿Podría resolver este iterando esencialmente sobre cada nodo i y luego hacer un árbol de expansión mínima de todos los bordes apuntando a que el nodo i, resultante de la unión con otro árbol de expansión mínima de todos los bordes apuntando distancia desde ese nodo?

A 2-aproximación a la mínimo conectados fuertemente subgrafo se obtiene tomando la unión de un mínimo en la ramificación y mínima fuera de ramificación, tanto con raíz en la misma (pero arbitrario) vértice.

Un fuera de ramificación , también conocido como arborescencia , es un árbol dirigido con raíz en un solo vértice que abarca todos los vértices. Un en-ramificación es la misma con los bordes inversa. Estos se pueden encontrar por Edmonds' algoritmo en el tiempo O (VE) , y hay aceleraciones a O (log e (V)) (ver la página wiki ). Hay incluso una implementación de código abierto .

La referencia original para el resultado 2-aproximación es la por JaJa y Frederickson , pero el papel no es de libre acceso.

Hay incluso una aproximación 3/2 por Adrian Vetta (PDF) , pero más complicado que el anterior.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top