Алгоритм разбиения на пары по тренеру/весу

Здравствуйте. Нужно разбить участников соревнований так, чтобы
1. Ни один ученик одного тренера не стоял с учеником того же тренера если это возможно (главный приоритет -тренер)
2. Разница в весе между участниками в парах должна быть минимальна и максимальная разница в весе между участниками должна быть минимальной, например вот такое разбиение
хуже чем такое
потому что в первом максимальная разница -10, а во втором 9. Если количество участников не равно пульке (2 в степени -2,4,8...) ,то создаются дополнительные бои - "тройки", например если участников 5 то есть один доп. бой-тройка (два дерутся - один ждет), остальные два участника уже в пульке
Если 6 участников - 2 тройки (4 дерутся в доп боях - 2 ждут в пульке, двоек нет),если 7 - одна тройка -один ждет, остальные в доп боях
Тройки тоже должны быть максимально близки по весу.
В сети не чего не нашел, пришлось самому изобретать велосипед. Сперва сортировал таблицу по тренерам от меньшинства к большинству по количеству учеников (снимок 1), а потом по порядку с первого искал самых подходящих по весу и сперва искал тройки, потому как если сначала искать двойки то на тройку меньшинства может не хватить, но все равно при таком алгоритме попадается куча вариантов списков, в которых не находится лучший вариант. Можно отсортировать по весу от меньшинства к большинству и там уже искать подходящих по тренеру -но это тоже ни к чему не приведет -потому как наилучший вариант разбиения может начинаться с поиска самого подходящего не к наименьшему по весу, а к кому нибудь другому. Мозг уже сломал и постоянно возникают не видимые условия, при которых идеальный вариант не получается.
//---------------------------------------------------------------------------------------------------------
Как вы думаете, при каком алгоритме можно найти идеальное разбиение, он существует? Что можете посоветовать?

Миниатюры

 

0

Мне кажется если и есть решение, то его надо искать в сортировке по весу - сортировать таблицу по увеличению веса и сперва найти максимальные скачки в разнице участников, например в сортировке 40.40.40.42.42.45.45.45 максимальный скачок происходит после веса 42 к 45 (то есть 3), и это возможно минимальная "максимальная разница" в весе среди участников и именно на это место в списке нужно обратить внимание (сн1,2). Если до скачка количество записей четное (не 5 как в нашем случае, а например 6), то этот скачок можно избежать (если в списке нет троек, если есть - то избежать скачок можно при нечетном количестве участников до него и не четном количестве троек вмещающихся до скачка). Короче чтобы избежать максимальный скачок, все записи до него нужно разбить на пары/тройки, но опять таки тройки и двойки можно расположить и после скачка (если есть возможность) и там они могут быть ближе по весу. Как определить где тройкам лучше находиться -до или после скачка? Потом максимальных скачков может быть несколько как в таком случае поступать? Мы упростили задачу до предела -все участники одного тренера (или у каждого тренера только один ученик), а мозг уже взорвался. Представьте что будет, если мы начнем рассматривать несколько тренеров с произвольным количеством учеников у каждого.
На ум приходит только один вариант -перебрать все варианты и выбрать самый подходящий, это хорошо если участников не больше десяти - 10! вариантов, а если их 40 - это 1*2*3...40 вариантов - жизни не хватит ни какому компу и перебрать.
Если действительно существует решение этой (на первый взгляд простой задачи), то как вы думаете -оно может быть относительно простым? Возможно все эти условия, которые я перечислил (и не перечислил) заменить каким то не большим количеством условий?

Миниатюры

   

0

И вообще, как найти все необходимые условия, выполняя которые можно прийти к данному решению? Этому где то учат?

0

По части главного приоритета (тренер) нашел такое условие, следуя которому ученик одного тренера не станет с учеником того же тренера. Например есть 4 тренера (столбца) по 3 ученика у каждого (12 участников)
Нужно разбить этот список на 4 группы по 3 элемента (участника) так, чтобы все элементы были разные (например группа т1,т2,т1 не подходит), вот один из верных вариантов разбиения
Возникает вопрос, когда это вообще возможно. Можно поставить другой вопрос - А когда элементы одного и того же столбца встают друг с другом? И ответ на этот вопрос оказывается очевидным -тогда , когда максимальное число элементов (одного из столбцов или нескольких) становится больше количества групп (в данном случае 4). Так например такой список
можно расставить, потому что максимальное число элементов <=4, а токой
уже нельзя, потому что в нем максимум -5, и в 4 группах хотя бы 2 его элемента все же встанут друг с другом. Но в данном случае нужно не только избежать совпадение элементов столбца (тренера), но чтобы и по весу между ними была минимальная разница и максимальный разброс этой разницы был тоже минимальный. И тут проблема в том, что чем больше учеников у тренера (даже с одинаковым весом), тем больше они могут создать разницу в весе при попытке встать с самыми ближними участниками других тренеров, потому как сами с собой они встать не могут, и не ясно с кем нужно ставить выбранного участника - с тем кто минимально меньше его весит, или минимально больше. А попытка сблизить их может увеличить максимальный разброс. Так же разброс может увеличиться из за главного приоритета (тренер), когда один из учеников тренера, число оставшихся учеников которого >количества оставшихся групп, должен присутствовать в группе не взирая на вес остальных учеников. И чем дальше копаешься в этом -тем больше новых условий возникает.

0