algorithm - guia - ¿Cómo puedo encontrar una manera de minimizar el número de bordes?

guia qgis

Question

Estoy pensando en un algoritmo para resolver el problema a continuación:

Un gráfico dado compuesto de vértices y bordes.

Hay N clientes que desean viajar de un vértice a otro vértice. Y cada requisito del cliente necesita un borde dirigido para conectar dos vértices.

El problema es cómo encontrar el número mínimo de bordes para satisfacer todos los requisitos de los clientes.

Hay un ejemplo simple:

• El cliente 1 desea viajar del vértice a al vértice b.
• El cliente 2 quiere viajar del vértice b al vértice c.
• El cliente 3 quiere viajar del vértice a al vértice c.

La forma más simple es dar una ventaja para cada cliente:

• borde 1: vértice a -> vértice b
• borde 2: vértice b -> vértice c
• borde 3: vértice a -> vértice c

Pero en realidad solo necesita 2 bordes (es decir, borde 1 y borde 2) para satisfacer tres requisitos del cliente.

Si el número de clientes es grande, ¿cómo encontrar los bordes mínimos para satisfacer todos los requisitos del cliente?

¿Hay un algoritmo para resolver este problema?

Answer 1

Puede modelar el problema como un programa de enteros mixtos. Puede definir variables binarias para "arc a-> b se usa" y "el cliente c usa arc a -> b" y anote los requisitos como desigualdades lineales. Si su gráfico no es demasiado grande, puede resolver dichos modelos en un tiempo razonable mediante un solucionador de programa entero mixto (CPLEX, GUROBI, pero también hay alternativas gratuitas en la web).

Sé que esta solución requiere algo de trabajo si no está familiarizado con la programación lineal, pero garantiza encontrar las mejores soluciones en tiempo definido y probablemente pueda resolverla para (digamos) 1000 clientes y 1000 arcos.

Answer 2

Si tiene N vértices, siempre puede construir una solución con N (dirigidos) bordes. Simplemente cree un ciclo dirigido V_1 -> V_2 -> V_3 -> ... -> V_N -> V_1. Nunca se puede haber direccionado la ruta de cada vértice V_a a cada otro vértice V_b con menos aristas (porque tendría un árbol dirigido que necesariamente contiene una hoja). La hoja no es alcanzable (si el borde va de hoja afuera) o la hoja es un sumidero (no se puede conectar a otra cosa) si el borde es -> hoja.

Answer 3

No es necesario usar ningún algoritmo nuevo. Puede usar el algoritmo BFS / DFS.

Find if there exists any path between source and destination.
   if !true
      add a direct edge between source and destination
      count++;
return count; 

Aquí la parte clave es en lugar de un bucle a través del gráfico, tenemos que recorrer los bordes recién agregados.