Максимальный поток решения модифицированной проблемы перемещения Найта

Question

Вам дается шахматная доска nxn с k рыцарями (того же цвета).Кто-то пролил суперклей на k квадратов, и если рыцарь когда-либо закончит свой ход на одном из этих квадратов клея, он застрянет навсегда.Кроме того (и именно поэтому у нас не может быть хороших вещей), кто-то вырезал некоторые квадраты, чтобы на шахматной доске были отверстия.Вам дана начальная позиция рыцарей.Рыцари двигаются так же, как и в обычных шахматах, но в отличие от обычных шахмат, на каждом ходу все рыцари двигаются одновременно (кроме, конечно, застрявших).В конце каждого хода квадрат не может быть занят более чем одним рыцарем.Квадраты дырок также не могут быть заняты рыцарями (но они считаются квадратами, через которые рыцарь может перепрыгнуть).Дайте 0 (tx poly (n)) - алгоритм времени, чтобы определить, можете ли вы использовать

Моя первоначальная мысль - сформулировать эту проблему как задачу максимального потока и использовать алгоритм Форда-Фулкерсона для ее решения.Но я не уверен, какими должны быть мои узлы и ребра.Любая идея?Спасибо!

Answer 1

Описанная проблема может быть смоделирована как проблема многоуровневой сети следующим образом.Набор узлов сети состоит из искусственного начального узла s и искусственного оконечного узла t.Набор промежуточных узлов состоит из k копий шахматной доски n * n, что означает, что всего имеется

2 + k * n * n

узлов.Представьте себе s вверху, а затем k слоев копий шахматной доски.Терминальный узел t будет внизу.

Соедините s с начальными позициями коней на первой шахматной доске и подключите t ко всем желаемым концевым позициям коней в k -th шахматная доска.

Для каждого i in {1,...,k-1} соедините каждый квадрат на i -ой шахматной доске с каждым квадратом на i+1 шахматной доске, если и только если это может быть достигнуто ходом законного рыцаря.Наконец, удалите все ребра, которые выходят из склеенного квадрата (кроме случаев, когда t - его хвост), и удалите все ребра, которые ведут к отверстию.Кроме того, каждое ребро ограничено, чтобы разрешить поток по крайней мере 0 и максимум 1.В общей сложности сеть имеет не более

2 * k + k * n * n = k * ( 2 + n * n )

ребер.Кроме того, чтобы принять во внимание, что каждый квадрат должен быть занят не более чем одним рыцарем, поток в каждом промежуточном узле также должен быть ограничен 1.Это можно сделать, расширив каждый промежуточный узел на два узла и соединяя их дополнительным ребром, в котором поток ограничен 1, что приводит к увеличению набора узлов и ребер не более чем в 2.

Рыцари k могут быть перемещены из своих начальных положений в свои конечные положения тогда и только тогда, когда сеть допускает s - t -поток значения k, где последовательность рыцарейдвижения и реализующие сетевые потоки биективно соответствуют.