Вдохновленный возможностями функционального программирования, в частности F#, и увидев на примере, что можно творить всего в несколько десяток строчек, решил реализовать простенькую версию самой сложной флеш-игры.
Задача о максимальном потоке является классической и имеет множество применений. Напомню постановку проблемы. Дан взвешенный ориентированный граф с неотрицательными весами (пропускными способностями). Выделены две вершины: исток S и сток T такие, что любая другая вершина лежит на пути из S в T. Потоком назовем функцию F: V x V с такими свойствами
Ограничение пропускной способности. Поток по ребру не может быть больше его (ребра) пропускной способности.
Антисимметричность. Для каждого ребра (u, v): F(u, v) = -F(v, u).
Сохранение потока. Для каждой вершины (кроме S и T), количество входящего потока (отрицательного) равен количеству исходящего потока (положительного). Тоесть, алгебраическая сумма потоков для каждой вершины (кроме S и T) равна нулю.
В этом посте вы можете ознакомиться с реализацией поставленной проблемы.
Перейдем непосредственно к типичным задачам, которые сводятся к алгоритму нахождения максимального потока в сети. Часто выявить в таких задачах поток очень не просто.
Для раскрытия темы, разберем вариацию известной игры Ним.
И так, на столе лежат несколько кучек камней. за один ход разрешается либо взять произвольное число камней из любой кучки, любо разделить любую кучку на две непустых. В обычных правилах игрок, который не может сделать ход, проигрывает. В поддавках же проигрывает тот, после чьего хода не останется камней на столе.
