Это очень похоже на Assignment Problem, за исключением полного неориентированного графика, а не двудольного графа.Учитывая группу людей, где каждая пара имеет значение, как я могу найти конфигурацию пар с наименьшим общим значением?
неглупых, самая грубая сила-IEST решение что-то вроде этого:
Получить все возможные конфигурации пар ...
groups = people.combination(2).to_a.combination(people.size/2).to_a... отвергая все конфигурации, которые содержат одно и то же лицо более одного раза.
groups.reject! { |group| group.flatten.uniq.size < people.size }Затем найти конфигурацию с минимальным значением.
groups.min_by { |group| group.inject(0) { |pair| value_for(pair) }
Есть модификация ветвей и границ решения для Assignment Problem, который принимает во внимание, что здесь, то Работа и Person являются как люди?
Может ли быть другая проблема с комбинаторика, которая больше напоминает то, что я представил?
Как я могу получить наилучшее решение без жарки моего процессора?
Спасибо!
Извините, что вы педантичны, но если каждая пара * людей имеет значение, то поиск пары с наименьшим значением тривиален - по-видимому, вам просто нужно выбрать структуру, которая сохраняет это значение? Я предполагаю, что вы имеете в виду что-то еще. –
@ AndyJones Приношу свои извинения за то, что вы расплывчаты. Я не ищу пару с самым низким значением, я ищу, чтобы найти с надмножеством пар, имеет самое низкое общее значение. Скажем, у вас было десять человек, я хочу найти, какая из возможных конфигураций из 5 пар дает самое низкое общее количество. –
Спасибо за это - я, наверное, единственный человек, читающий это, что не сразу понял! –