Подскажите алгоритм или в какую сторону копать
Сортируем, берем первых M?
В смысле сортируем?
Странный вопрос..
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%...
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%...
Кого и как сортировать?
В тупую засуммировать все балы и отстортировать строки по этим балам что ли?
В тупую засуммировать все балы и отстортировать строки по этим балам что ли?
Да, или уточняй тогда, что ты подразумеваешь под общей суммой.
Если были выбраны M участников, то общая сумма для них сумма всех результатов только между ними. Разве как то иначе можно было понять? 
Разве как то иначе можно было понять?Ага, берем M участников - смотрим сумму набранных ими баллов, находим минимальную.
"Нужно выбрать из таблицы подтаблицу для M игроков с минимальной общей суммой баллов." - вот как-то так правильнее
"Нужно выбрать из таблицы подтаблицу для M игроков с минимальной общей суммой баллов." - вот как-то так правильнееNP-трудно вроде бы
Берем граф, составляем таблицу: игроки - вершины графа, результат равен 10, если ребра между вершинами нет, 0 - если есть.
Минимальная сумма для M участников равна 0 <=> есть клика из M вершин
Да. похоже на правду. Так что полным перебором с оптимизациями. Кстати рекурсия возможно будет полезна. То есть подсчет частных сумм сильно разгрузит счет, но тут следить надо чтоб стека хватило на M вложений.
ага для решения np-полной задачи будет полезна рекурсия 
это блин прорыв в теории сложности!
полезнее не оптимизациями заниматься, а переосмыслить постановку задачи. так ли уж нужно чтобы именно минимальное значение было, или подойдет отличие от минимума на 1%? или скажем находить минимум с 99% вероятностью. да куча есть всяких ослаблений, которые позволяют от np-полноты уйти.
это блин прорыв в теории сложности!полезнее не оптимизациями заниматься, а переосмыслить постановку задачи. так ли уж нужно чтобы именно минимальное значение было, или подойдет отличие от минимума на 1%? или скажем находить минимум с 99% вероятностью. да куча есть всяких ослаблений, которые позволяют от np-полноты уйти.
Пойдет и околоминимум, то что сейчас - вообще плохо работает 
Так что полным перебором с оптимизациями.
Количество вариантов прикинь. Если я все правильно путаю, то для выбора 300 игроков из 1000 (т.е. в 10 раз меньшего кол-ва) нужно перебрать 5*10^263 вариантов. Если хорошо соптимизирует, то переберет за 10^250 лет.
А для 10000 маткад даже таких чисел не знает.
на правах бреда.
можно взять эту матрицу их игр (она похожа на матрицу "смежности" для неориентированного графа с кратными ребрами, каждая клеточка матрицы --- число ребер между вершинами) и повозводить ее во всякие степени k. это будет похоже на нахождение числа путей длины k.
простое наблюдение: для M = 2 нам надо найти просто минимум по матрице, эта клеточка укажет на двоих искомых чуваков.
может быть, если посмотреть повнимательней, то не лишено смысла возвести матрицу в степень M-1, найти минимум, занести в искомое множество игрока с номером строки i, в которой мы нашли минимум.
далее, перестроить исходную матрицу, исключив из нее строку и столбец i, уменьшить M на единицу и повторять эту процедуру, пока M != 2. для M = 2 см. наблюдение выше.
непонятно, почему это минимальное число путей определенной длины как-то соотносится с принадлежностью к искомому множеству, но может, кого это натолкнет на правильную мысль.
можно взять эту матрицу их игр (она похожа на матрицу "смежности" для неориентированного графа с кратными ребрами, каждая клеточка матрицы --- число ребер между вершинами) и повозводить ее во всякие степени k. это будет похоже на нахождение числа путей длины k.
простое наблюдение: для M = 2 нам надо найти просто минимум по матрице, эта клеточка укажет на двоих искомых чуваков.
может быть, если посмотреть повнимательней, то не лишено смысла возвести матрицу в степень M-1, найти минимум, занести в искомое множество игрока с номером строки i, в которой мы нашли минимум.
далее, перестроить исходную матрицу, исключив из нее строку и столбец i, уменьшить M на единицу и повторять эту процедуру, пока M != 2. для M = 2 см. наблюдение выше.
непонятно, почему это минимальное число путей определенной длины как-то соотносится с принадлежностью к искомому множеству, но может, кого это натолкнет на правильную мысль.
Я бы попробовал начать с жадного алгоритма (ну то есть на каждом шаге добавляем того участника, который вносит наименьший вклад в общую сумму).
посмори как оптимизируют перебор при поиске максимальных клик, тут что-то такое-же подойдёт.
[], на мысль пока не натолкнуло, т.к. не совсем понял, что имелось в виду Надо будет вкрурить. Давно с графами не сталкивался.
, жадный буду пробовать - уже предложили.
, спасибо, гляну что можно получить.
Надо будет вкрурить. Давно с графами не сталкивался., жадный буду пробовать - уже предложили.
, спасибо, гляну что можно получить.
генетические алгоритмы
Оставить комментарий
0000
Допустим проводятся соревнования между N участниками (N ~10 000, каждый участник имеет свой уникальный номер от 1 до N). Каждый играет с каждым один раз. Результат записывается в виде натурального числа от 1 до 10 для обоих участников в таблицу, т.е. если играли второй и третий с результатом 4, то у обоих будет 4 в соответсвующих клеточках.Требуется выбрать M (~100-300) участников, таким образом, чтобы общая сумма очков была минимальна для заданного M. Т.к. возможно выбрать неоднозначно, пойдет любой набор на котором достигается минимум.