Что может быть лучше, чем цикл for для реализации алгоритма, который включает наборы? - PullRequest
Новая
       19

Что может быть лучше, чем цикл for для реализации алгоритма, который включает наборы?

0 голосов
/ 17 апреля 2019

Я пытаюсь создать алгоритм по следующим направлениям:

-Создать 8 участников

-Каждый участник имеет набор интересов

-Пар их с другимучастник с наименьшим количеством интересов

Итак, что я до сих пор делал, это создал 2 класса, Участник и Интерес, где Интерес является Хасируемым, чтобы я мог создать Набор с ним.Я вручную создал 8 участников с разными именами и интересами.

Я сделал массив выбранных участников и использовал базовый цикл in, чтобы несколько спарить их вместе с помощью функции intersection () наборов.Каким-то образом мой индекс всегда выходит за пределы допустимого диапазона, и я уверен, что есть лучший способ сделать это, но он настолько грязный, и я не знаю, с чего начать. 

for i in 0..<participantsSelected.count {
    if participantsSelected[i].interest.intersection(participantsSelected[i+1].interest) == [] {
        participantsSelected.remove(at: i)
        participantsSelected.remove(at: i+1)
        print (participantsSelected.count)
    }
}

Так что моя другая проблемаиспользование цикла for для этого конкретного алгоритма также кажется немного неэффективным, поскольку если все они имеют 1 одинаковый интерес, и он не будет равен [] / nil.

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

РЕДАКТИРОВАТЬ: обновленный код,вот моя попытка улучшить мою логику алгоритма 

for participant in 0..<participantsSelected {
    var maxInterestIndex = 10
    var currentIndex = 1
    for _ in 0..<participantsSelected {
        print (participant)
        print (currentIndex)
        let score = participantsAvailable[participant].interest.intersection(participantsAvailable[currentIndex].interest)
        print ("testing score, \(score.count)")
        if score.count < maxInterestIndex {
            maxInterestIndex = score.count
            print ("test, \(maxInterestIndex)")
        } else {
            pairsCreated.append(participantsAvailable[participant])
            pairsCreated.append(participantsAvailable[currentIndex])
            break
//            participantsAvailable.remove(at: participant)
//            participantsAvailable.remove(at: pairing)
        }
        currentIndex = currentIndex + 1
    }
}

for i in 0..<pairsCreated.count {
    print (pairsCreated[i].name)
}

1 Ответ

0 голосов
/ 17 апреля 2019

Вот решение в том случае, если вы ищете оптимальное сочетание ваших участников (всех) по вашим критериям:
Тогда нужно найти идеальное соответствие в графе участников.
Создайте график с n вершинами, n - количество участников. Мы можем обозначить u_p вершину, соответствующую участнику p.
Затем создайте взвешенные ребра следующим образом:
Для каждой пары участников p, q (p! = Q) создайте ребро (u_p, u_q) и сравните его с количеством интересов, общих для этих двух участников.
Затем запустите алгоритм идеального соответствия минимального веса на вашем графике, и работа завершена. Вы получите оптимальный результат (т. Е. Наилучший из возможных или один из наилучших возможных соответствий) за полиномиальное время.

Алгоритм идеального сопоставления минимального веса: задача строго эквивалентна алгоритму сопоставления максимального веса. Найдите ребро максимального веса (обозначим C его вес). Затем замените вес w каждого ребра на C-w и запустите алгоритм согласования максимального веса на полученном графике.

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

Еще одна возможность: если вы уверены, что число участников будет небольшим (вы упомянули 8), вы также можете использовать алгоритм перебора, то есть проверить все возможные способы объединения участников. Тогда алгоритм будет выглядеть так: 

find_best_matching(participants, interests, pairs):
    if all participants have been paired:
        return sum(cost(p1, p2) for p1, p2 in pairs), pairs  // cost(p1, p2) = number of interests in common
    else:
        p = some participant which is not paired yet
        best_sum = + infinite
        best_pairs = empty_set
        for all participants q which have not been paired, q != p:
            add (p, q) to pairs
            current_sum, current_pairs = find_best_matching(participants, interests, pairs)
            if current_sum < best_sum:
                best_sum = current_sum
                best_pairs = current_pairs
            remove (p, q) from pairs
        return best_sum, best_pairs

Сначала позвоните по номеру find_best_matching(participants, interests, empty_set_of_pairs), чтобы получить наилучший способ подбора участников.

...