Это пример проблемы оптимизация . Это очень хорошо
изучил тип проблем с очень хорошими методами их решения. Читать
Программирование Коллективного Разума , которое объясняет это намного лучше
чем я.
В принципе, есть три части любой проблемы оптимизации.
- Вход в функцию решения проблем.
- Решение , выводимое функцией решения проблем.
- Функция оценки, которая оценивает, насколько оптимальным является решение
забив.
Теперь проблема может быть сформулирована как поиск решения, которое производит
самый высокий балл. Для этого сначала нужно придумать формат
представить возможное решение, что функция оценки может затем
Гол. Предполагая 6 человек (0-5) и 3 группы (0-2), эта структура данных Python
будет работать и будет возможным решением:
output = [
[0, 1],
[2, 3],
[4, 5]
]
Человек 0 и 1 помещен в группу 0, человек 2 и 3 в группу 1 и т. Д.
на. Чтобы оценить это решение, нам нужно знать входные данные и правила для
рассчитать выход. Входные данные могут быть представлены этими данными
структура:
input = [
[0, 4, 1, 3, 4, 1, 3, 1, 3],
[5, 0, 1, 2, 1, 5, 5, 2, 4],
[4, 1, 0, 1, 3, 2, 1, 1, 1],
[2, 4, 1, 0, 5, 4, 2, 3, 4],
[5, 5, 5, 5, 0, 5, 5, 5, 5],
[1, 2, 1, 4, 3, 0, 4, 5, 1]
]
Каждый список в списке представляет рейтинг, который дал человек. За
Например, в первом ряду человек 0 дал оценку 0 человеку 0 (вы
не может оценить себя), 4 к человеку 1, 1 к человеку 2, 3 к 3, 4 к 4 и
1 человеку 5. Затем он или она оценили группы 0-2 3, 1 и 3
соответственно.
Итак, выше приведен пример правильного решения для данного ввода. Как
мы забиваем это? Это не указано в вопросе, только то, что
«Лучшая» комбинация желательна, поэтому я произвольно решу, что
оценка для решения - сумма счастья каждого человека. каждый
счастье человека определяется добавлением его или ее рейтинга
группа со средним значением рейтинга для каждого человека в группе,
исключая самого человека.
Вот функция подсчета очков:
N_GROUPS = 3
N_PERSONS = 6
def score_solution(input, output):
tot_score = 0
for person, ratings in enumerate(input):
# Check what group the person is a member of.
for group, members in enumerate(output):
if person in members:
# Check what rating person gave the group.
group_rating = ratings[N_PERSONS + group]
# Check what rating the person gave the others.
others = list(members)
others.remove(person)
if not others:
# protect against zero division
person_rating = 0
else:
person_ratings = [ratings[o] for o in others]
person_rating = sum(person_ratings) / float(len(person_ratings))
tot_score += group_rating + person_rating
return tot_score
Должно быть получено 37,0 баллов за данное решение. Что теперь
мы сделаем, чтобы генерировать действительные результаты, отслеживая, какой из них
лучше, пока мы не удовлетворены:
from random import choice
def gen_solution():
groups = [[] for x in range(N_GROUPS)]
for person in range(N_PERSONS):
choice(groups).append(person)
return groups
# Generate 10000 solutions
solutions = [gen_solution() for x in range(10000)]
# Score them
solutions = [(score_solution(input, sol), sol) for sol in solutions]
# Sort by score, take the best.
best_score, best_solution = sorted(solutions)[-1]
print 'The best solution is %s with score %.2f' % (best_solution, best_score)
Запуск этого на моем компьютере выдает:
The best solution is [[0, 1], [3, 5], [2, 4]] with score 47.00
Очевидно, вы можете подумать, что это действительно глупая идея - случайным образом
генерировать решения, чтобы бросить на проблему, и это так. Есть много
более сложные методы для создания решений, таких как имитация
отжиг или генетическая оптимизация. Но все они основаны на том же
рамки, как указано выше.