повышение эффективности соответствующего алгоритма


Я пытаюсь создать алгоритм, который будет соответствовать один набор объектов с другой. Каждый из объектов из одной группы могут быть сопоставлены с некоторыми объектами из другой группы. После того, как товар был подобран, он не может быть сопоставлен другой элемент. Моя текущая реализация выполняет итерации по каждому из объектов и попыток найти решение там, где каждый объект имеет матч. Я сделал это рекурсивно, но этот метод быстро становится непригодным, так как время обработки увеличивается в геометрической прогрессии. Вот тривиальный пример того, что я написал:

def demo_match():
    possible_matches = {
        "x": {1, 2},
        "y": {2, 3},
        "z": {1, 2}
    }

    used_numbers = set()

    matched = {}

    def match_items(remaining_items_to_match):

        for letter in remaining_items_to_match:
            possible_numbers = possible_matches[letter]
            available_numbers = possible_numbers.difference(used_numbers)
            print(f"can match '{letter}' with {available_numbers}")
            if not available_numbers:
                raise ValueError(f"there are no possible matches for {letter}")
            for possible_match in available_numbers:
                try:
                    used_numbers.add(possible_match)
                    matched[letter] = possible_match
                    print(f"'{letter}' has been matched with {possible_match}")
                    if len(remaining_items_to_match) is 1:
                        return matched
                    # remove this item and process the remaining
                    next_remaining_items = remaining_items_to_match[1:]
                    return match_items(next_remaining_items)
                except ValueError:
                    print(f"***** found a dead end, unmatching '{letter}' and {possible_match} *****")
                    used_numbers.remove(possible_match)
                    del matched[letter]
            raise ValueError("ran out of available numbers to match")

    print(f"\nMatch Solution: {match_items(list(possible_matches.keys()))}")

Фактическая реализация присваивается весовой коэффициент возможных совпадений, это означает, что согласование 1 пункт будет предпочтительнее, но если это приводит в тупик, он пытается на следующий матч. Я чувствую, что есть лучше реализации этого там, может быть, с привлечением наборы, где детали накладываются и определения критического пути. Я просто не смог придумать достойной альтернативы это перебор.

------- Обновление ------

После изучения алгоритмов, предложенных в ответах, я решил пойти с munkres алгоритм. Это позволяет взвешивание предметов на вершину.

Он принимает матрицу элементов, где строки представляют 1 пункта столбцы другом, и где они пересекаются-это стоимость, когда эти элементы работают в паре. Типичным примером использует людей и рабочих мест, как элементы. Этот алгоритм будет находить пары предметов с наименьшими затратами. Чтобы предотвратить продукт от быть в паре, установить стоимость в матрицу float('inf') например:

         Janitor     Teacher     Doctor
Bob       9           5          1
Dick      1           4          6 
Sally     5           3          7

будут представлены:

[
[9,5,1],
[1,4,6],
[5,3,7]
]

и вернется [0,1,2], [2,0,1], где в первом списке представлены индексы строки и второй список представляет индекс столбцов, которые будут сопоставлены с рядами Я в конечном итоге преобразование двух списков в словарь людей, их соответствующее задание через

>>> def match():
    from munkres import Munkres
    people = ["bob", "dick", "sally"]
    jobs = ["janitor", "teacher", "doctor"]
    matrix = [
               [9,5,1],
               [1,4,6],
               [5,3,7]
              ]

    m = Munkres()
    indexes = m.compute(matrix)

    matches = {}
    for p, j in indexes:
        person = people[p]
        job = jobs[j]
        matches[person] = job
    return matches

>>> match()
{'bob': 'doctor', 'dick': 'janitor', 'sally': 'teacher'}

matches будет словарь людей, в их подобраны задания



321
4
задан 26 января 2018 в 07:01 Источник Поделиться
Комментарии
2 ответа

1. В Хопкрофт–Карп алгоритм

Проблему вы пытаетесь решить здесь найти максимальное паросочетание в взвешенный двудольный граф. Это может быть решена в \О(\корень V е)\ долл Хопкрофт–Карп алгоритм.

Вот эскиз, как Хопкрофт–Карп алгоритм работы. Предположим, что мы имеем двудольный взвешенный граф, как тот, который вы использовать в качестве примера в посте:

Bipartite graph with vertices x,y,z,1,2,3

Потому что он двудольный, есть два набора вершин, которые мы будем называть \У $\$ и $\\в$:

U contains vertices x,y,z and V contains vertices 1,2,3

В Хопкрофт–Карп алгоритм работает, неоднократно увеличивая соответствуя, увеличивая количество ребер в соответствие с одного. Предположим, что мы добавили один край к комбинационной до сих пор, между \$г\$ и \2$\$, нарисованный красным краем:

y matched with 2

Алгоритм теперь ищет пути увеличения. Это путь, который начинается в непревзойденной вершиной в \у\$, кресты \$в\$ на равных (черный) края, кресты обратно в \У\ на мой взгляд, не соответствует (красный) край, и так далее, наконец, заканчивающийся в \$в\$. Вот приумножения путь, начиная с \х$\$, после непревзойденной края \2$\$, после совпали края \$г\$, а следующие непревзойденный края \3$\$:

Augmenting path x-2-y-3

В дополнение путь имеет нечетное количество ребер (потому что она начинается в \У\$ и заканчивается в \$\ В$) и края на пути чередуются между непринятые. Это означает, что если мы поменяем все ребра на пути увеличения (совпавшие становится непревзойденной и наоборот), мы получим новое паросочетание с еще одного края, Вот так:

x matched with 2 and y matched with 3

Теперь с алгоритмом, есть еще один путь увеличения, \$З\$–\2$\$–\$х\$–\1$\$:

Augmenting path z-2-x-1

Замена ребер на этом пути, мы снова увеличить сопоставления:

x matched with 1, y with 3 and z with 2

Теперь больше нет пути увеличения (потому что нет равных вершин в \У$\$) и мы сделали.

Как мы можем найти пути приумножения? Ну, мы используем сочетание поиска в ширину и глубину. На каждом этапе мы делаем поиск в ширину для разделения вершин на слои в соответствии с их кратчайшее расстояние от непревзойденной вершине вдоль приумножения пути. Предположим, что мы находимся на этом этапе алгоритма, где \$г\$ был согласован с \$2\$:

y matched with 2

Теперь поиск в ширину делит вершины на следующие слои:

Four layers

Используя эту структуру, пути увеличения может быть найдено эффективно (линейного времени), путем поиска в глубину, которая только следует за края из меньшего числа слоев с более высоким номером слоев.

2. Реализация

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

from collections import deque

def maximum_matching(graph):
"""Find a maximum unweighted matching in a bipartite graph. The input
must be a dictionary mapping vertices in one partition to sets of
vertices in the other partition. Return a dictionary mapping
vertices in one partition to their matched vertex in the other.

"""
# The two partitions of the graph.
U = set(graph.keys())
V = set.union(*graph.values())

# A distinguished vertex not belonging to the graph.
nil = object()

# Current pairing for vertices in each partition.
pair_u = dict.fromkeys(U, nil)
pair_v = dict.fromkeys(V, nil)

# Distance to each vertex along augmenting paths.
dist = {}
inf = float('inf')

def bfs():
# Breadth-first search of the graph starting with unmatched
# vertices in U and following "augmenting paths" alternating
# between edges from U->V not in the matching and edges from
# V->U in the matching. This partitions the vertexes into
# layers according to their distance along augmenting paths.
queue = deque()
for u in U:
if pair_u[u] is nil:
dist[u] = 0
queue.append(u)
else:
dist[u] = inf
dist[nil] = inf
while queue:
u = queue.pop()
if dist[u] < dist[nil]:
# Follow edges from U->V not in the matching.
for v in graph[u]:
# Follow edge from V->U in the matching, if any.
uu = pair_v[v]
if dist[uu] == inf:
dist[uu] = dist[u] + 1
queue.append(uu)
return dist[nil] is not inf

def dfs(u):
# Depth-first search along "augmenting paths" starting at
# u. If we can find such a path that goes all the way from
# u to nil, then we can swap matched/unmatched edges all
# along the path, getting one additional matched edge
# (since the path must have an odd number of edges).
if u is not nil:
for v in graph[u]:
uu = pair_v[v]
if dist[uu] == dist[u] + 1: # uu in next layer
if dfs(uu):
# Found augmenting path all the way to nil. In
# this path v was matched with uu, so after
# swapping v must now be matched with u.
pair_v[v] = u
pair_u[u] = v
return True
dist[u] = inf
return False
return True

while bfs():
for u in U:
if pair_u[u] is nil:
dfs(u)
return {u: v for u, v in pair_u.items() if v is not nil}

4
ответ дан 27 января 2018 в 11:01 Источник Поделиться

Сразу, это происходит со мной:


  • Построить карту частоты возможные значения совпадают:

    freqs = collections.Counter()

    for k,v in possible_matches.items():
    freqs.update(v)


  • Вес ключи совпадают по сумме всех возможных замен:

    weights = {k: sum(freqs[replacement] for replacement in v) 
    for k,v in possible_matches.items() }

  • Используйте весы на заказ с минимальным весом в первую очередь. Это будут матчи с наименьшим количеством возможностей:

    order_to_try = sorted(possible_matches.keys(), key=lambda k: weights[k])

  • Сортировать remaining_items_to_match используя порядок выше. Это, как правило, назначают наиболее подходят замены первого, поэтому он должен подрезать начале:

    ritm = sorted(remaining_items_to_match, key=lambda k: weights[k])

Обратите внимание, что технически, когда вы "выделит" Матч изменяется динамика веса. Так что вы могли передать измененную таблицу замены рекурсивно, так привыкли восстановительной стоимости будут удалены из расчета веса:

new_freqs = collections.Counter()
for k,v in possible_matches.items():
new_freqs.update(v - used_numbers) # Discarding used numbers

И если это важно, вы должны быть пересекающиеся ваш possible_matches С набором входов (remaining_items_to_match), чтобы убедиться, что вы не несете никакой дополнительный багаж...

3
ответ дан 26 января 2018 в 08:01 Источник Поделиться