¿Cómo encontrar los ciclos que, juntos, involucran el mayor número de aristas no compartidas en un gráfico dirigido?

26

No soy un teórico de la informática, pero creo que este problema del mundo real pertenece aquí.

El problema

Mi compañía tiene varias unidades en todo el país.

Ofrecimos a los empleados la posibilidad de trabajar en otra unidad. Pero hay una condición: el número total de trabajadores en una unidad no puede cambiar.

Eso significa: permitiremos que un empleado abandone su unidad si alguien quiere su lugar.

Ejemplo de datos de solicitud (ficticios):

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

Lo anterior, trazado: Visualización de los datos anteriores.

¿Ves cómo tenemos que elegir entre las opciones rojo, azul o negro?

El verdadero problema es un poco más complejo, porque tenemos 27 unidades y 751 solicitudes. Por favor, eche un vistazo a la visualización

La meta

Habiendo recogido todas las solicitudes, ¿cómo satisfacer la mayoría de ellas?

Aplicación de la teoría (?)

Teniendo el gráfico , deje que cada unidad sea un vértice V y una solicitud sea un borde dirigido E , un intercambio exitoso tomará la forma de un ciclo dirigido.G(V,E)VE

Cada ciclo debe usar solo una vez ( un trabajador no puede abandonar su unidad dos veces ), pero puede visitar V varias veces ( una unidad puede tener muchos trabajadores que quieran irse ).EV

La pregunta

Si este problema se expresa como

"¿Cómo encontrar los ciclos que, juntos, involucran el mayor número de aristas no compartidas en un gráfico dirigido"?

¿Satisfaceremos a la mayoría de los solicitantes?

Siendo cierto, ¿hay un algoritmo para encontrar ese conjunto óptimo de ciclos?

¿Este enfoque de greddy resolverá el problema?

  1. Encuentra el ciclo dirigido más grande en ;G
  2. Quite sus bordes de ;G
  3. Repita 1 hasta que no haya un ciclo dirigido en ;G

¿Me puedes ayudar?

¿Conoces otra forma de describir el problema original (haciendo felices a la mayoría de los solicitantes)?

Editar : se cambió el departamento a la unidad, para describir mejor el problema.

motobói
fuente
3
¿Estás seguro de que solo quieres evitar usar el mismo borde más de una vez? Según su descripción de la aplicación, me parece que debe evitar usar el mismo vértice más de una vez, lo cual es una condición más fuerte.
Tsuyoshi Ito
3
@TsuyoshiIto: Como entiendo por la descripción, la condición es que en cada vértice el grado debe ser igual al grado de salida. Por lo tanto, no se necesita la desunión de vértices.
Yoshio Okamoto
77
Por cierto, si mi comprensión es correcta, el problema debería resolverse en tiempo polinómico por medio del flujo de red. Es decir, si damos una unidad de ganancia por una unidad de flujo a lo largo de un borde, y le damos una unidad de capacidad en cada borde, el problema es encontrar una circulación de ganancia máxima.
Yoshio Okamoto
3
Esta publicación discute una generalización de su problema okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html (piense en cada persona como teniendo un artículo para intercambiar, es decir, su colocación laboral).
Radu GRIGore
44
Impresionante pregunta, nos hace sentir que lo que hacemos realmente se puede usar en la vida real :).
Gopi

Respuestas:

9

OK, leí el código de TradeMaximizer y creo que resuelve el siguiente problema más general.

PROBLEMA: Dado es un gráfico dirigido cuyos arcos tienen costos. Encuentre un conjunto de ciclos vértice-disjuntos que maximice primero la cantidad de vértices cubiertos y minimice el costo total en segundo lugar.

xyxyyz

Solución:

  1. xxLxRxLxRxyxLyR

  2. Encuentre una coincidencia perfecta de costo mínimo en el gráfico bipartito.

>1

(De hecho, TradeMaximizer itera sobre todas las soluciones óptimas, de acuerdo con los dos criterios anteriores, para optimizar heurísticamente otras cosas, como la duración del ciclo más grande. Los ciclos grandes aumentan la posibilidad de que un "acuerdo" no funcione porque uno la persona cambia de opinión.)

PD: El autor, Chris Okasaki, confirmó que esto es lo que hace el código, en la publicación del blog .

Radu GRIGore
fuente
Logré encontrar una solución al problema original usando TradeMaximizer. Publicaré detais mañana.
motobói
@ motobói, pero todo lo que necesitas hacer es lo que escribí en el segundo párrafo ...
Radu GRIGore
He encontrado esta explicación sobre el algoritmo: boardgamegeek.com/wiki/page/TradeMaximizer
motobói
¿Podría explicar o señalar una explicación sobre por qué es necesario eliminar los arcos entre los Componentes de conexión fuerte?
motobói
@ motobói, es una optimización (para el caso promedio). Los pasos (1) y (2) deberían ser suficientes.
Radu GRIGore
22

11

Debido a que todos los costos y capacidades están limitados por constantes, un simple algoritmo de cancelación de ciclo encontrará la circulación requerida en el tiempo polinómico. Esto es casi lo mismo que el algoritmo codicioso obvio:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

O(VE)0EEO(VE2)

Este no es el algoritmo más rápido conocido.

Jeffε
fuente
cree que esto funciona mientras una persona no quiera trabajar en más de una "unidad", ¿verdad? usando la redacción de la pregunta original. pero si la gente quiere trabajar en más de una unidad, sospeche que esta abstracción se rompe. OP declaró el problema en términos de una sola unidad, pero esto me parece bastante artificialmente restrictivo. [¿Qué humano tiene una sola preferencia ...?]
vzn
1
¿Qué es una "persona" y una "unidad"? Esta es una pregunta sobre gráficos.
Jeff el
Estoy desconcertado: ¿Mi ejemplo no es un contraejemplo para este algoritmo? Después de elegir C, los ciclos C_1 y C_2 ya no son ciclos (porque cada ciclo tiene un borde invertido); C no se volverá a utilizar porque tiene un costo positivo después de invertir sus bordes y no se introducen nuevos ciclos. ¿Estamos hablando del mismo problema? Me encantaría tener una formulación matemática del problema.
FiB
3
CCC1C2CCC1C2C=C1+C2C
aparentemente una "unidad" es algo así como un "departamento" y los usuarios están registrando solicitudes de transferencias entre departamentos [¿no son exactamente posiciones específicas en los departamentos]? El diagrama FIB parece tener unidades como vértices y aristas como solicitudes empl entre unidades. FiB-- "me encantaría tener una formulación matemática del problema" ... realmente depende de usted proporcionar una formulación precisa ... parece estar a medio camino ...
vzn
4

Este enfoque codicioso no siempre dará la mejor solución.

Cn{(v1,v2),,(vn,v1)}C1C2n1C

CnC1C2

C1C22(n1)=2n2

n2

Mentira
fuente
-3

Probablemente haya una forma / formulación de la teoría de grafos para resolver esto, pero este problema me suena más como un problema de permutación donde algunas de las permutaciones son rechazadas y otras son válidas. las permutaciones son empleados y los puestos son "puestos" en la empresa. una permutación se rechaza si no cumple con los requisitos de "persona [x] quiere posición [y]". La distinción de unidades / departamentos / límites de la organización es aparentemente algo superflua para la solución en este caso.

Este tipo de problema de permutación con restricciones se puede convertir fácilmente en una instancia de problema SAT (satisfacción). las asignaciones de variables booleanas representan empleados, y las cláusulas de restricción representan las restricciones de "persona [x] quiere posición [y]". hay ejemplos clásicos cercanos de esto, uno generalmente llamado el problema de la "mesa de la cena" en el que tiene asientos e invitados y no todos los invitados quieren sentarse uno al lado del otro (o de manera muy similar, algunos invitados quieren sentarse al lado de otros invitados).

y, por supuesto, hay solucionadores de SAT sofisticados para instancias bastante grandes que involucran aproximadamente hasta cientos de variables y cláusulas, en PC, y si el problema no es "difícil", en miles.

ver, por ejemplo, [1] para una referencia profesional y [2] para un ejercicio de clase. También hay cierta similitud estructural con lo que se conoce como "problemas de casilleros", que se estudian bien en los círculos SAT, donde las palomas se asignan a los casilleros y usted tiene más o menos agujeros que las palomas. en ese caso, sin embargo, las palomas generalmente se consideran intercambiables. en otras palabras, el problema de la mesa de la cena es como el problema del palomar con restricciones más fuertes y los invitados / palomas tienen las preferencias requeridas.

tenga en cuenta que, por supuesto, tenga en cuenta que para este tipo de problemas, dependiendo de las restricciones, la respuesta puede ser "no existe tal solución limitada".

[1] el algoritmo de la mesa, por crato

[2] CS402 princeton HW SAT

[3] Problema de satisfacción, wikipedia

vzn
fuente
Probé la permutación usando trademaximizer. Establecer un empleado como un usuario que desee cambiar su unidad de X para la unidad de Y . Pero el software no permitirá que más de un usuario intercambie el mismo artículo (su unidad). Cada artículo tiene que ser único. Para acomodar esto, debería haber tenido, por ejemplo, [(Jones) quiere cambiar la Unidad-C-James por la Unidad-D-Laura o la Unidad-D-Sergio o la Unidad-D-Mary]
motobói