Uno de mis algoritmos favoritos es el algoritmo Ford-Fulkerson para calcular el flujo máximo en una red de flujo:
Algoritmo Ford – Fulkerson – Wikipedia
El algoritmo tiene varias propiedades interesantes:
- Después de que termina el programa de programación (estructuras de datos y algoritmo), ¿qué se les enseña a los estudiantes en CSE después de eso?
- ¿Puedes predecir la lotería con algoritmo?
- Cómo resolver el problema 144C en Codeforces
- ¿Cuáles son algunas aplicaciones del algoritmo de clasificación de burbujas?
- ¿Cuál es la diferencia entre los algoritmos FPgrowth y Apriori en términos de resultados?
- Primero, es satisfactorio implementarlo también porque es fácil visualizar el flujo en una red. Dado que el cuerpo humano consiste en gran medida en agua, también tenemos una fuerte relación física con dicha tarea.
- En segundo lugar, el algoritmo es una instancia de un enfoque muy general para resolver tareas de optimización lineal. En Operaciones de Investigación, el algoritmo se conoce como una instancia del método primal-dual . Esto resuelve el problema primario resolviendo iterativamente instancias del problema dual.
- El doble problema, en este caso, es muy simple y también satisfactorio de implementar: consiste en encontrar una llamada ruta de aumento . Esto también es bastante intuitivo: mejora la solución de forma incremental.
- No se detiene allí: para calcular una ruta de aumento, tiene varias opciones. Si lo haces ingenuamente, entonces tendrás que atravesar todos los caminos en general, y esto conduce a una desaceleración exponencial, ¡ aunque de hecho se puede calcular un flujo máximo en tiempo polinómico!
- Dependiendo de su elección de ruta de aumento, ¡el algoritmo Ford-Fulkerson puede ni siquiera converger en un flujo máximo !
- Una buena opción es utilizar una ruta de aumento más corta . Esta instancia del algoritmo Ford-Fulkerson se conoce como el algoritmo Edmonds-Karp y tiene un tiempo de ejecución polinómico.
- ¡A su vez, se puede calcular una ruta más corta con otra instancia del método primal-dual !
He usado el algoritmo Ford-Fulkerson en CLP (Z) , un solucionador de restricciones sobre enteros , donde se usa para razonar sobre el gráfico de valores inducido por restricciones importantes como global_cardinality/2 :
triska / clpz
Esto permite una poderosa propagación de restricciones. Considere, por ejemplo, el caso de 3 variables X, Y y Z, cada una de las cuales puede asumir los valores 0 y 1, con la restricción adicional de que dos de las variables son iguales a 0 y una es igual a 1. Usando CLP ( Z), podemos expresar esto con global_cardinality/2 siguiente manera:
? – global_cardinality ([X, Y, Z], [0-2,1-1])
Aquí, un par de la forma NK significa que el valor N debe aparecer K veces en la lista de variables. Por ejemplo, en este caso, 0 debe aparecer dos veces en [X,Y,Z] .
Ahora, si además declaramos que X no es igual a 0, entonces CLP (Z) deduce automáticamente que Y y Z deben ser 0, porque esta es la única forma posible de satisfacer las restricciones establecidas:
? – global_cardinality ([X, Y, Z], [0-2,1-1]), X # \ = 0.
X = 1
Y = Z, Z = 0.
Internamente, CLP (Z) usa el algoritmo Ford-Fulkerson para deducir esto.
Un algoritmo estrechamente relacionado, el algoritmo Hopcroft-Karp, también se utiliza en el solucionador de restricciones para calcular una coincidencia máxima en gráficos bipartitos. Esto se utiliza para determinar, por ejemplo, que no se pueden cumplir las siguientes restricciones:
? – [X, Y, Z] ins 0..1, all_distinct ([X, Y, Z]).
falso.
Esto se debe a que si hay tres variables que solo pueden asumir los valores 0 o 1, es imposible encontrar una asignación donde las variables sean distintas por pares.
También estoy usando el algoritmo Ford-Fulkerson en SWI-Prolog para resolver problemas de transporte y asignación con la library(simplex) :
SWI-Prolog – Manual
Aquí, todo el algoritmo se usa para resolver el dual en otro método primal-dual para resolver el problema de transporte, ¡de los cuales el problema de asignación es un caso especial! Entonces, es primal-dual todo el camino hacia abajo.
