Другой ответ в порядке, но вам не нужно задействовать поток, так как он может быть сведен к обычному максимальному двойному согласованию:
- Для каждой плоскости добавьте еще одну вспомогательную плоскость к плоское разбиение с ребрами того же пилота, что и первая плоскость.
- Найти максимальное двойное соответствие M .
- Теперь ответ верен тогда и только тогда, когда M = 2 N .
Если хотите, вы можете думать об этом как о том, что каждому самолету нужен пилот и второй пилот, и два вершины, связанные с каждой плоскостью, теперь представляют эти две роли.
Приведение к максимальному двустороннему соответствию - это линейное время, поэтому, используя, например, алгоритм Хопкрофта-Карпа , чтобы найти соответствие, вы можете решить проблема в O (| E | √ | V |), где E - количество ребер между разделами, а V = T + N .
На практике улучшение Кроме того, использование подхода, основанного на максимальном потоке, должно зависеть от качества ваших реализаций, а также от конкретного выбора представления графа, но есть вероятность, что вам будет лучше.
Пример реализации
Чтобы проиллюстрировать последний пункт, давайте дадим представление о том, как эти два сокращения могут выглядеть на практике. Одним из представлений графа, который часто полезен из-за его встроенной памяти, является матрица CSR , поэтому давайте предположим, что вход представляет собой такую матрицу, строки которой соответствуют плоскостям, и чьи столбцы соответствуют пилот-сигналам.
Мы будем использовать библиотеку SciPy Python, которая поставляется с алгоритмами как для максимального двустороннего соответствия, так и для максимального потока, и которая работает с представлениями матрицы CSR для графов в капот.
В приведенном выше алгоритме нам потребуется построить матрицу двунаправленности графа с добавлением дополнительных вершин. Это не что иное, как результат размещения входной матрицы поверх самого себя, что легко выразить словами в терминах структур данных CSR: следуя нотации Википедии, COL_INDEX следует просто повторить, а ROW_INDEX следует заменить на ROW_INDEX, соединенный с копией ROW_INDEX, в котором все элементы увеличиваются на последний элемент ROW_INDEX.
В SciPy полная реализация, которая отвечает да или нет на проблему в OP, будет выглядеть следующим образом:
import numpy as np
from scipy.sparse.csgraph import maximum_bipartite_matching
def reduce_to_max_matching(a):
i, j = a.shape
data = np.ones(a.nnz * 2, dtype=bool)
indices = np.concatenate([a.indices, a.indices])
indptr = np.concatenate([a.indptr, a.indptr[1:] + a.indptr[-1]])
graph = csr_matrix((data, indices, indptr), shape=(2*i, j))
return (maximum_bipartite_matching(graph) != -1).sum() == 2 * i
В подходе максимального потока, заданном ответом @ HeatherGuarnera, нам нужно будет установить полную матрицу смежности нового графа. Это также относительно просто; входная матрица будет отображаться в виде определенной подматрицы матрицы смежности, и нам нужно добавить строку для исходной вершины и столбец для цели. пример раздела документации для решателя максимального потока SciPy фактически содержит иллюстрацию того, как это выглядит на практике. Принимая это, полное решение выглядит следующим образом:
import numpy as np
from scipy.sparse.csgraph import maximum_flow
def reduce_to_max_flow(a):
i, j = a.shape
n = a.nnz
data = np.concatenate([2*np.ones(i, dtype=int), np.ones(n + j, dtype=int)])
indices = np.concatenate([np.arange(1, i + 1),
a.indices + i + 1,
np.repeat(i + j + 1, j)])
indptr = np.concatenate([[0],
a.indptr + i,
np.arange(n + i + 1, n + i + j + 1),
[n + i + j]])
graph = csr_matrix((data, indices, indptr), shape=(2+i+j, 2+i+j))
flow = maximum_flow(graph, 0, graph.shape[0]-1)
return flow.flow_value == 2*i
Давайте сравним время двух подходов на одном примере, состоящем из 40 плоскостей и 100 пилот-сигналов, на графике, граничная плотность которого равна 0,1:
from scipy.sparse import random
inp = random(40, 100, density=.1, format='csr', dtype=bool)
%timeit reduce_to_max_matching(inp) # 191 µs ± 3.57 µs per loop
%timeit reduce_to_max_flow(inp) # 1.29 ms ± 20.1 µs per loop
Подход, основанный на сопоставлении, быстрее, но не безумно. В более крупных задачах мы начнем видеть преимущества использования сопоставления; с 400 самолетами и 1000 пилотами:
inp = random(400, 1000, density=.1, format='csr', dtype=bool)
%timeit reduce_to_max_matching(inp) # 473 µs ± 5.52 µs per loop
%timeit reduce_to_max_flow(inp) # 68.9 ms ± 555 µs per loop
Опять же, это точное сравнение опирается на использование заданных c предопределенных решателей из SciPy и как они реализованы, но если ничего другого, это намекает на то, что проще лучше.