Это может быть представлено как направленный граф , где узлы представляют людей, а ребра указывают, может ли человек переехать в дом другого человека.В общем случае вы можете использовать np.equal.outer для вычисления кандидатов на хост, а затем использовать networkx для создания соответствующего графика.Например:
home destination
Carole A C
Irvin A D
Kelvin C A
Stanley A D
Lazaro E C
Yong C A
Florentino B E
Jose C E
Bettye B E
Clinton A D
Georgia A D
Lon A E
Ezra C D
Tim A E
Mae A B
# Create the graph by feeding the edges.
graph = nx.DiGraph()
graph.add_edges_from(np.argwhere(np.equal.outer(df['destination'], df['home'])))
Некоторые атрибуты результирующего графа:
graph.number_of_nodes() # 15
graph.number_of_edges() # 31
list(graph.edges()) # [(0, 2), (0, 5), (0, 7), (0, 12), (2, 0), (2, 1), (2, 3), (2, 9), (2, 10), (2, 11), (2, 13), (2, 14), (5, 0), (5, 1), (5, 3), (5, 9), (5, 10), (5, 11), (5, 13), (5, 14), (7, 4), (11, 4), (13, 4), (14, 6), (14, 8), (4, 2), (4, 5), (4, 7), (4, 12), (6, 4), (8, 4)]
Поиск возможных кандидатов
Теперь мы можем получить наборы возможных кандидатов путем поиска циклов вэтот график (цикл означает, что каждый, кто переезжает в другой дом, также сдаст их в аренду);мы можем использовать nx.simple_cycles:
Найти простые циклы (элементарные цепи) ориентированного графа.
A simple cycle или elementary circuit - это замкнутый путь, где нетузел появляется дважды.Две элементарные схемы различны, если они не являются циклическими перестановками друг друга.
list(nx.simple_cycles(graph)) # [[0, 7, 4, 5], [0, 7, 4, 2], [0, 5, 14, 8, 4, 2], [0, 5, 14, 6, 4, 2], [0, 5, 13, 4, 2], [0, 5, 11, 4, 2], [0, 5], [0, 2, 14, 8, 4, 5], [0, 2, 14, 6, 4, 5], [0, 2, 13, 4, 5], [0, 2, 11, 4, 5], [0, 2], [2, 14, 8, 4], [2, 14, 6, 4], [2, 13, 4], [2, 11, 4], [4, 7], [4, 5, 14, 8], [4, 5, 14, 6], [4, 5, 13], [4, 5, 11]]
Поиск наилучшего отображения
Жадный подход
Для того, чтобы найтиОптимальное решение: мы можем рассматривать каждый цикл как набор узлов, и нам нужно найти комбинацию непересекающихся множеств, которая имеет наибольшую величину.Это сложная вычислительная задача, и поэтому может быть предпочтительным жадное решение (т.е. просто добавлять циклы один за другим и отбрасывать те, которые не пересекаются с накопленным множеством).Например:
# Greedy approach.
cycles = []
nodes = set()
for cycle in nx.simple_cycles(graph):
if nodes.isdisjoint(cycle):
cycles.append(cycle)
nodes.update(cycle)
Это дает cycles == [[0, 7, 4, 5]], что, однако, не является оптимальным решением.
Оптимальное решение
Если это выполнимо с вычислительной точки зрения, оно может быть найдено методом перебораиспользование другого графа, представляющего совместимые (т.е. непересекающиеся) множества;мы добавляем пустой набор, чтобы мы могли использовать величину других наборов (длину соответствующих циклов) в качестве веса ребер:
import itertools as it
all_cycles = list(nx.simple_cycles(graph))
disjoint = np.zeros((len(all_cycles),)*2 , dtype=bool)
disjoint[np.triu_indices(disjoint.shape[0], k=1)] = list(map(
lambda x: set.isdisjoint(*x),
it.combinations(map(set, all_cycles), 2)
))
# Add the empty set as a starting point, so we can use cycle length as edge weight.
disjoint = np.concatenate([np.ones((1, disjoint.shape[1]), dtype=bool), disjoint], axis=0)
disjoint = np.concatenate([np.zeros((disjoint.shape[0], 1), dtype=bool), disjoint], axis=1)
lengths = np.fromiter(map(len, [[]] + all_cycles), dtype=int)
indices = np.argwhere(disjoint)
c_graph = nx.DiGraph()
c_graph.add_edges_from(zip(indices[:, 0], indices[:, 1], ({'weight': l} for l in lengths)))
best_combination = nx.dag_longest_path(c_graph, 'weight')
Результат - [0, 7, 13].Обратите внимание, что это включает пустой набор в качестве 0-го индекса, поэтому нам нужно сместить каждый индекс на -1.Следовательно, окончательное решение представляет собой соединение циклов [[0, 5], [2, 14, 8, 4]], которые имеют общую длину 6. Фактически это означает, что
Carole должен переключаться с Yong, - и
Kelvin -> Mae -> Bettye -> Lazaro -> Kelvin.
Масштабируемость
Теперь все это вычислительно непросто, и для вашего примера 400 000 выборок это будет невозможно.Уже np.equal.outer имеет потребление памяти O (N ^ 2) и, следовательно, заканчивается ~ 20 ГиБ.Здесь вы также можете построить график постепенно, перебирая кадр данных строка за строкой.Тем не менее, результирующий график может быть настолько сложным, что все равно невозможно вычислить все циклы, например.
Другой вариант масштабирования этого для больших наборов данных - отказаться от гарантированной оптимальности путем случайного разбиения набора данных на подмножества.каждый из которых достаточно мал, чтобы алгоритм работал.Затем результаты получаются для каждого подмножества и объединяются в глобальный результат.Выполнив несколько таких случайных разбиений и сравнив отдельные результаты, можно еще улучшить решение.
Вместо разделения набора данных можно также выбрать подмножества, найти подмножество и затем вернуть этих людей в пул.которые не были сопоставлены.Точно так же в подходе разделения можно объединить всех непревзойденных людей после одного раунда разделения и затем продолжить итеративно.