Puntuación alta: problemas de flujo de red

1. Introducción

El algoritmo de flujo de red es un algoritmo eficiente y práctico. En comparación con otros algoritmos de teoría de grafos, su modelo es más complejo y la complejidad de la programación es mayor. Sin embargo, integra algunos otros algoritmos en la teoría de grafos (como la ruta más corta y el algoritmo de búsqueda de ancho), por lo que su alcance de aplicación es más amplio y, a menudo, puede resolver algunos problemas no NP que no pueden resolverse mediante búsqueda y programación dinámica.

La parte más desafiante de aplicar el flujo de red a problemas específicos es la construcción del modelo. No existe un modelo listo para usar que pueda aplicarse. Necesitamos conocer la naturaleza de varios flujos de red (como. Dianyou) Capacidad, la capacidad tiene límites superior e inferior, múltiples aristas, etc.), y utilizamos nuestra creatividad de acuerdo con problemas específicos. A menudo se pueden crear varios modelos para un problema, y ​​diferentes modelos tienen diferentes impactos en la eficiencia de la resolución de problemas. Este artículo utiliza ejemplos para explorar cómo determinar el modelo apropiado y mejorar la eficiencia del algoritmo de flujo de red.

2. Eficiencia temporal del algoritmo de flujo de red

Después de determinar que el problema se puede resolver utilizando el algoritmo de flujo máximo, lo resolveremos de acuerdo con el etiquetado Ford-Fulkerson comúnmente utilizado. método; y el costo mínimo (grande) El problema del flujo máximo también se puede resolver mediante un algoritmo dual similar al método de etiquetado. El tiempo de ejecución del método de etiquetado Ford-Fulkerson es o(ve2), y el tiempo de ejecución del método dual para encontrar el flujo de costo mínimo es aproximadamente o(v3e2).

Obviamente, los principales factores que afectan la eficiencia temporal del algoritmo de flujo de red son el número de vértices y el número de aristas en la red. Estos dos factores no son independientes entre sí, sino que están interrelacionados, son contradictorios y unificados. Al construir un modelo de red, a veces, cuando se optimiza un factor, también se optimiza otro factor; a veces, cuando se optimiza un factor, otro factor se incrementa a expensas; Por tanto, a la hora de resolver problemas específicos, debemos adherirnos a la "visión general" y lograr un equilibrio entre ambas.

3. Optimización y selección de modelos

(1) Reducir el número de vértices y aristas del modelo y optimizar el modelo

Si se puede basar En algunas propiedades especiales del problema, reducir el número de vértices y aristas en el modelo de red puede mejorar en gran medida la eficiencia del algoritmo.

Ejemplo 1: Control mínimo de la reina

En ajedrez, la reina puede atacar en ocho direcciones (como se muestra en la Figura 1(a), los puntos negros en la imagen son la posición de la reina , la cuadrícula marcada con k es la cuadrícula que la reina puede atacar). Ahora, dado un tablero de ajedrez m*n (ni n ni m es mayor que 50), hay obstáculos en algunas casillas del tablero. Cada reina se coloca en una cuadrícula libre de obstáculos y controla esta cuadrícula. Además, puede elegir una cuadrícula para controlar entre el máximo de 8 cuadrículas que puede atacar, como se muestra en la Figura 1 (b), denominada El cuadrado con 1. está controlado por una reina.

Escribe un programa para calcular el número mínimo de reinas necesarias para controlar completamente todo el tablero de ajedrez.

Figura 1(a) Figura 1(b)

Formato de entrada:

La primera línea del archivo de entrada tiene dos números enteros myn, que representan el tablero de ajedrez El número de filas y columnas. A continuación, m filas yn columnas son una matriz de caracteres, con los símbolos ''.'' que representan cuadrículas en blanco y ''x'' que representan cuadrículas con obstáculos.

Formato de salida:

La primera línea del archivo de salida tiene solo un número s, que indica el número de reinas necesarias.

entrada de muestra

3 4

x...

x.x.

.x.. p>

salida de muestra

5

Análisis del problema]

Si este problema se resuelve mediante una búsqueda simple, ya que el tablero de ajedrez dado en la pregunta es muy grande, es difícil para los algoritmos de búsqueda encontrar soluciones en poco tiempo. Dado que una reina sólo puede controlar hasta dos casillas en el tablero de ajedrez, el límite inferior del número mínimo de reinas requeridas es [n*m/2]. Para minimizar el número de reinas, tantas reinas como sea posible deben controlar dos cuadrículas. Si agregamos un arco dirigido entre cada dos cuadrículas que pueden atacarse entre sí, el problema es muy similar al problema de máxima coincidencia de un gráfico bipartito.

[Modelo 1]

1. Numere cada cuadrícula sin obstáculos en prioridad de fila (0~m*n-1).

2． Doble cada cuadrícula i de arriba en dos cuadrículas i'' e i'''', que se utilizan como vértices en el modelo de red.

3． Si la cuadrícula i puede atacar la cuadrícula j y ilt;j, entonces agregue un arco dirigido entre los vértices i'' a j'''' en el modelo con una capacidad de 1.

4. Agregue un punto de origen s y agregue un arco desde el punto s a todos los vértices i''; agregue un punto sumidero t y agregue un arco desde todos los vértices j'''' a t, con una capacidad de 1.

Para el tablero de ajedrez que se muestra en la Figura 1(b), el modelo correspondiente es:

Figura 2

Obviamente, cualquier solución corresponde a un máximo de las anteriores. coincidencia de modelo. Y en la coincidencia máxima, el número de coincidencias debe ser par. Por lo tanto, el número mínimo de caballos requerido es m*n-número de obstáculos-número máximo de partidos/2.

[Modelo 2]

Si pintamos el tablero de ajedrez en una cuadrícula en blanco y negro, entonces una de las dos cuadrículas controladas por una reina debe ser una cuadrícula negra y la otra es una cuadrícula blanca (como se muestra en la Figura 3), también podría asumir que la reina en estas dos cuadrículas está en la cuadrícula blanca. Entonces, dividimos las cuadrículas n*m en dos partes: cuadrícula blanca y cuadrícula negra. Por tanto, podemos optimizar el modelo 1 como:

Figura 3

1. Divida todas las cuadrículas del tablero de ajedrez en dos partes, numere todas las cuadrículas y agregue un arco desde la cuadrícula blanca a la cuadrícula negra entre cada cuadrícula blanca y la cuadrícula negra que puede atacar (excepto los obstáculos) para formar una imagen de bisección. .

2． Agregue un punto de origen s y agregue un arco desde el punto s a todas las celdas blancas sin obstáculos, agregue un punto de sumidero t y agregue un arco desde todas las celdas negras sin obstáculos a t;

3． Establezca el caudal de todos los arcos en 1.

El tablero de ajedrez que se muestra en la Figura 1(b), el modelo correspondiente es:

Figura 4

[Comparación de los dos modelos]

Obviamente, el número de vértices y aristas del modelo dos es aproximadamente la mitad que el del modelo uno. La siguiente es una comparación de la eficiencia de tiempo de los dos modelos en el entorno bp (p166/32m):

Modelo 1 y Modelo 2

La escalabilidad no es fácil de imprimir en una solución , fácil de imprimir una solución

El modelo 2 se basa en la particularidad del problema (es decir, la forma en que se mueve el caballo), dividiendo los puntos de la cuadrícula en dos categorías: blanco y negro, y estipulando que el caballo solo puede saltar de la cuadrícula blanca a la cuadrícula negra, evitando así dividir cada punto de la cuadrícula en dos puntos, reduciendo la cantidad de vértices del modelo y también reduciendo en gran medida la cantidad de aristas. Se lograron buenos resultados de optimización.

(2) Combinar las ventajas de varios modelos y seleccionar modelos inteligentemente

A veces, varios modelos para el mismo problema tienen sus propias características y tienen sus propias ventajas y desventajas. En este caso, debemos considerar exhaustivamente las ventajas y desventajas de varios modelos y seleccionar inteligentemente el modelo del problema en función de los datos de prueba.

Ejemplo 2 Mars Rover (ioi97)

Hay un módulo de aterrizaje (pod) que contiene muchos vehículos de detección de obstáculos (MEV), que aterrizarán en la superficie de Marte. Después del aterrizaje, el rover abandona el módulo de aterrizaje y avanza hacia el transmisor que llegó no muy lejos. El MEV recolecta muestras de rocas mientras se mueve. La roca es recolectada por el primer MEV que lo visita. Una roca solo se puede recolectar una vez. Pero después de eso, otros mevs pueden pasar. El rover MEV no puede atravesar obstáculos en el suelo.

Esta pregunta limita el movimiento del rover mev hacia el sur o el este a lo largo de la cuadrícula desde el punto de aterrizaje hasta el transmisor, lo que permite que varios rover mev ocupen la misma posición al mismo tiempo.

Tarea: Calcular las trayectorias de movimiento de todos los vehículos rover para que puedan enviar la mayor cantidad de muestras de roca al transportador, y todos los vehículos rover deben llegar al transportador.

Entrada:

La posición entre el módulo de aterrizaje y el transmisor en la superficie de Marte está representada por la red p y q. La posición del módulo de aterrizaje es (1). , 1) punto, La posición del transmisor está en el punto (p, q).

Las diferentes superficies de Marte están representadas por tres símbolos numéricos diferentes:

0 significa plano y sin obstáculos

1 significa obstáculos

2 representa piedras.

El archivo de entrada se compone de la siguiente manera:

númerodevehículos

p

q

(x1y1)( x2y1) (x3, y1)…(xp-1y1)(xpy1)

(x1y2)(x2y2)(x3, y2)…(xp-1y1)(xpy2)

(x1y3 )(x2y3)(x3, y3)…(xp-1y3)(xpy3)

(x1yq-1)(x2yq-1)(x3, yq- 1) …(xp-1yq-1)(xpyq-1)

(x1yq)(x2yq)(x3,yq)…(xp-1yq)(xpyq)

p y q es el tamaño de la red; el número de vehículos es un número entero menor que 1000, que indica el número de vehículos sonda conducidos por el módulo de aterrizaje. ***Hay q filas de datos, cada fila representa un conjunto de datos en la superficie de Marte y ni p ni q exceden 128.

[Modelo 1]

Es natural que tomemos la ubicación del módulo de aterrizaje como punto de origen y la ubicación del teletransportador como punto de hundimiento. Al mismo tiempo, el primer mev que accede a ella recolecta una determinada roca. Cada roca solo se puede recolectar una vez. Pero después de eso, otros MEV pueden pasar, lo que permite que varios MEV móviles ocupen la misma posición al mismo tiempo. Entonces dividimos cada punto del mapa en dos puntos, a saber (x, y) à (x, y, 0) y (x, y, 1). La estructura del modelo de red específico que describe un mapa de Marte es la siguiente:

1. Divida cada punto sin obstáculos en la cuadrícula en (x, y) dos puntos (x, y, 0) y (x, y, 1), donde el punto fuente s = v(1, 1, 0) y el punto sumidero Punto t = v(maxx, maxy, 1).

2． Agregue los siguientes tres tipos de aristas e1, e2 y e3 a los vértices anteriores. Las capacidades y costos correspondientes se registran como c1, c2, c3 y w1, w2, w3 respectivamente:

u e1 =. v(x, y, 0) -gt; v(x, y, 1), c1 = maxint, w1 = 0.

u e2 = v(x, y, 0) -gt; v(x, y, 1), c2 = 1, w2 = -1 (aquí se requiere que (x, y) debe ser mineral)

u e3 = v(x, y, 1) -gt; v(x'', y'', 0), c3 = maxint, w3 = 0.

Donde x''=x 1 y''=y o x''=x y''=y 1, 1 lt = x'' lt; , y (x'' y'') no es un obstáculo.

Como se puede ver en el modelo anterior, durante el proceso de construcción, un punto en el mapa se "divide" en dos nodos de la red. Agregar bordes de tipo e1 permite visitar cada punto varias veces, mientras que agregar bordes de tipo e2 hace que el mineral esté en un punto determinado. Para esta red, una ruta de s a t puede considerarse como la ruta de acción de un rover. El costo del camino es la cantidad de minerales recolectados por el rover. Para la red g, encuentre el flujo de costo mínimo fijo con el número de flujo de vehículos y podrá obtener la solución al problema.

[Modelo 2]

De hecho, si solo consideramos qué minerales se cargan en cada uno de los vehículos por turno. Entonces, el mineral que pasa por cada vehículo es un flujo, por lo que usamos el mineral en la cuadrícula como el vértice de la red para establecer el siguiente modelo de flujo de red.

1. Divida el punto mineral (x, y) en la cuadrícula al que se puede llegar desde cada punto inicial (esquina superior izquierda de la cuadrícula) y al que se puede llegar al punto final (esquina inferior derecha) desde él. en el punto izquierdo (x, y, 0) y el punto derecho (x, y, 1), y suma el punto fuente s y el punto sumidero t.

2. Agregue los siguientes cinco tipos de aristas e1, e2 y e3 a los vértices anteriores. Las capacidades y costos correspondientes se registran como c1, c2, c3 y w1, w2 y w3 respectivamente:

u e1 = v(x, y, 0) -gt; v(x, y, 1), c1 = 1, w1 = -1.

u e2 = v(x, y, 1) -gt; v(x'', y'', 0), c2 = 1, w2 = 0 (el punto mineral (x, y) puede alcanzar el punto de mineral (x'', y'')).

u e3 = s -gt; v(x, y, 0), c3 = 1, w3 = 0.

u e4 = v(x, y, 1)-gt;

u e5=s-gt;t, c5=maxint, w5=0.

Dado que cada piedra está doblada en dos puntos y tiene una capacidad de 1, se garantiza que cada piedra solo se puede quitar una vez, y quitar una piedra al mismo tiempo resultará en un costo de -1. . Por lo tanto, para el modelo anterior, podemos obtener la solución encontrando el flujo de costo mínimo con el número de flujo de vehículos.

[Comparación de los dos modelos]

1. El modelo 1 usa la cuadrícula como vértice y el modelo 2 usa el mineral como vértice. Por lo tanto, el modelo 2 es obviamente mejor. que el modelo en términos del número de vértices. En primer lugar, para algunos datos con minerales escasos y cuadrículas relativamente grandes, el modelo dos es más eficiente que el modelo uno. Y siempre que la cantidad de minerales no exceda un cierto número, el modelo dos puede manejar datos con p y q grandes, pero el modelo uno no.

2． El número de aristas en el modelo uno es como máximo 3*p*q, mientras que el número de aristas en el modelo dos es aproximadamente p*q*(p 1)*(q 1)/4-p*q en el peor de los casos. Por lo tanto, en este problema, para algunos datos con minerales relativamente densos y cuadrículas relativamente grandes, el número de aristas del modelo dos será mucho mayor que el del modelo uno, lo que dará como resultado una eficiencia de tiempo mucho menor que la del modelo uno.

La siguiente es una comparación de la situación en la que la red está llena de minerales (piii700/128m, modo de protección bp7.0):

numberofvehicles=10 Model One Model Two

A través de los datos anteriores, se puede ver que para el caso en que pyq no excedan 60, el modelo 1 puede resolver el problema en 10 segundos. El modelo 2 es muy lento en el peor de los casos cuando p y q = 30, y cuando p y q exceden 30, se produce un desbordamiento de memoria y no se puede resolver.

Por lo tanto, para esta pregunta, los dos modelos anteriores tienen sus propias ventajas y desventajas. Podemos decidir qué modelo construir en función de la escasez de minerales en los datos de prueba. Si el mineral es relativamente escaso, puede considerar establecer un modelo de red como el Modelo 2; si el mineral es relativamente denso, establezca un modelo de red como se muestra en el Modelo 1. Luego, aplique el algoritmo de flujo máximo de costo mínimo para resolver el problema. Para p, q>60 y hay muchos minerales, el algoritmo de flujo de red de ambos modelos no puede resolver el problema. En aplicaciones prácticas, los problemas a menudo solo requieren soluciones aproximadas. En este momento, también se pueden utilizar otros algoritmos para resolver el problema.

IV.Conclusión

En resumen, la optimización del modelo en el algoritmo de flujo de red es la base para mejorar la eficiencia del algoritmo de flujo de red. Con base en problemas reales, debemos considerar de manera integral cómo optimizar el modelo desde la perspectiva de reducir los vértices y aristas, y seleccionar un modelo apropiado para mejorar la eficiencia del algoritmo. Para algunos problemas, cuando varios modelos para resolver problemas tienen sus propias ventajas y desventajas, los datos de prueba también se pueden analizar automáticamente a través del programa para decidir qué modelo usar y en qué circunstancias, y aprovechar al máximo las ventajas de varios modelos para optimizar. Eficiencia del programa.