![]() |
Помогите с комбинаторной задачей!
Народ, подскажите, пожалуйста, как лучше создать и реализовать алгоритм. Может быть, кто-то уже сталкивался с подобной комбинаторной задачей. Суть в следующем: есть N людей в группе. Их надо разбить на m подгрупп по k людей в каждой. Например: 16=8x2, или 16=4х4, 15=3х5 и т.д. Передо мной стоит задача вывести на экран все возможные разбиения начальной группы. Формула для количества всевозможных вариантов (I) мной уже выведена. Выглядеть это должно примерно следующим образом (выводим в StringGrid или в DBGrid):
Разбиение 8=2х4: _____________________________ | № | Подгруппа 1 | Подгруппа 2 | ----------------------------------------------- | 1 | (1, 2, 3, 4) | (5, 6, 7, 8) | | 2 | (1, 5, 3, 4) | (2, 6, 7, 8) | | 3 | (1, 2, 5, 4) | (3, 6, 7, 8) | | 35 | (1, 3, 5, 6) | (2, 4, 7, 8) | ----------------------------------------------| Всего для данного конкретного разбиения существует 35 вариантов. Как не сложно догадаться есть некоторые ограничения, значительно усложняющие на первый взгляд простенькую задачу: 1. Перестановки внутри подгруппы нас не интересуют, то есть: (1, 2, 3, 4) = (2, 1, 3, 4) 2. Перестановки подгрупп между собой тоже: [(1, 2), (3, 4)] = [(3, 4), (1, 2)] 3. Один и тот же человек не может входить сразу в две подгруппы, например: [(1, 2), (1, 3)] Я решил для себя, что задачу проще всего будет организовать через трехмерный массив, где заполнение элементов будет осуществляться через 3 цикла (по количеству людей в подгруппе (1..k), по количеству подгрупп (1..m) и по количеству всевозможных вариантов (1..I)). Или, если быть точным, нужно составить двумерную матрицу, элементами которой являются одномерные массивы-строки (состав подгруппы). А потом полученные элементы "внешнего" массива я запишу в DBGrid, как показано в таблице. |
пока не понятно, что именно собираешься реализовывать, попробую показать как я это вижу
1. рассмотрим все перестановки (алгоритм) 1.1. выбрали один элемент 1.2. из оставшихся следующий 1.3. из оставшихся следующий и т.д... 2. рассмотрим перестановки с учётом групп. Чтобы внутри групп не получилось таких, которые из группы получаются перестановкой, будем всегда выбирать так, чтобы следующий элемент был больше предыдущего, то есть группа должна быть всегда отсортирована по возрастанию. 3. чтобы не стало так чтобы группа i+1 получалась из группы i перестановкой, первые элементы групп должны быть так же отсортированы по возрастанию. То есть выбираем только из тех оставшихся, которые больше, чем первый элемент в предыдущей группе. 4. в качестве элементов используем изначально упорядоченный массив чисел 1..N*K, т.к. для них применима операция сравнения. Пример для 4-х элементов: Код:
a b c d a<b, c<d, a<c 1. выбирать первые элементы групп лучше с начала списка (и не трогать последние K-1) 2. выбирать остальные элементы групп лучше с конца списка, чтобы хватило для заполнения самых последних групп Таким образом переберёшь все и ни разу не повторишься |
Добрый день, дамы и господа! Некоторое время назад я задавал вопрос по поводу комплектования малых подгрупп.
Задачу выполнил с помощью pva и используя данный алгоритм (функция формирования перестановок). Но! Дело в том, что при количестве людей большем 12, алгоритм перебора начинает захлебываться, то есть жутко тормозить или зависать. Поэтому встает вопрос: как можно ускорить процесс? Вкратце опишу суть того, что я делаю: формирую всевозможные перестановки N людей. На определенном шаге отсекаю все варианты, начинающиеся с 2. Варианты, начинающиеся с 3, 4 и т.д. уходят автоматически. Таким образом, количество перестановок резко сокращается. На каждом шаге формирования перестановки я осуществляю проверку на невозрастание внутри подгруппы и невозрастание первых людей подгрупп в соотвествии с алгоритмом, предложенным pva, . Если все ОК, то записываю перестановку в поток (TStream). После записи всех "правильных" перестановок (c учетом подгрупп) в поток я считываю данные из потока в ClientDataSet и далее они автоматически переносятся в DBGrid. Понятно, что промежуточные звенья (TStream и ClientDataSet) значительно тормозят процесс, но даже если их отключить и оставить алгоритм формирования перестановок работающим "вхолостую", то процесс все равно захлебывается. Что делать? Как выкрутиться из этой непростой ситуации? |
ALI, вот код, который я использовал для проверки (Metrowerks codewarrior 8.0):
Код:
#include <windows.h> использование памяти 384 МБ, в памяти: система, qip, winamp, IDE компилятора, файловый менеджер, браузер, справочная литература, антивирь и диспетчер задач.. ну и программа конечно. параметры: 4x3 (итого 12 чел) сборка debug: 127805 вариантов за 10.359 секунд сборка release: 127805 вариантов за 2.61 секунд не захлебнулось ;-) output: |
Как файл скачать-то?
Дык, с 12-ю людьми и у меня все нормально, а вот если речь заходит о 16 и более, то там начинаются проблемы. |
у меня случались какие-то глюки, когда я его засылал. Проще собери и получи за 2 секунды результат. Прошу прощения, не заметил "больше". Попробовал на большем числе - действительно уходит в большую обработку. Причём память использует на прежднем уровне. Я заметил, что на один результат в среднем уходит 100 байт. 120 тыс. комбинаций даёт 1.2 меговый файл. Когда запустил 4х4, подождал 30 минут, получил 1.5 гиговый файл и дальше ждать не стал. Вся проблема в том, что слишком большое число комбинаций. Я даже боюсь что может не хватить 32-разрядного регистра чтобы подсчитать их количество. Задача приобретает нерешаемый в силу временных ограничений характер.
Если всё-же хочешь ускорить процесс, предлагаю ввести распараллеливание (сейчас в моде многоядерные машины). Написаный выше мной код это сделать позволяет, т.к. на каждом следующем этапе используется своя независимая копия памяти. А вообще советую пересмотреть задачу |
Я, скорее всего, переделаю задачу через сочетания:
http://forum.algolist.ru/algorithm-m...-podgrupp.html Как там написал один товарисч, сочетаний значительно меньше, чем перестановок, посему алгоритм времени будет жрать меньше. |
Цитата:
|
Как ты представляешь себе смену постановки на попроще, а?
Смысл вот в чем: у меня есть "ручной" алгоритм, разработанный, кстати говоря, мной, в котором люди разбиваются на подгруппы за конечное число шагов на основе социометрии. Но проблема в чем? Проблема состоит в том, чтобы разбить этих людей ТАК, чтобы получить оптимальное решение с точки зрения взаимоотношений в исходной группе. Т.е. надо получить ТАКИЕ подгруппы, где люди меньше всего конфликтуют между собой. Получив решение на основе "ручного" алгоритма, я хочу посмотреть какое место оно будет занимать в "иерархии" разбиений, полученных методом перебора. Иерархия выстраивается по КГср (средний коэффициент когерентности). Пояснение: КГ (коэффициент когерентности) - мера связанности подгруппы, лежащая в пределах от -100 до 100. То бишь подгруппа с КГ=-100 - это самая худшая группа, которая только может существовать. Соответственно, подгруппа с КГ = 100 - это идеальная подгруппа. В каждом разбиении считаются КГi (КГ для каждой подгруппы), КГср, а далее они выстраиваются по возрастанию, т.е. наверху таблицы находятся разбиения с максимальным КГср, а внизу - с минимальным. Эта таблица и есть результат работы алгоритма перебора. Потом я ищу в общей массе разбиение, полученное ручным методом и смотрю, насколько высоко или низко оно находится с точки зрения КГср. В зависимости от полученного результата, я буду "подкручивать" ручной алгоритм, чтобы он поднялся как можно выше. Поэтому, так или иначе, но мне приходится просматривать ВСЕ разбиения. Если ты когда-нибудь сталкивался с транспортной задачей, задачей о рюкзаке, теорией графов, СМО и др. подобными задачками, то это из этой оперы. :) |
ВОТ!!! совершенно другое дело! я поправлю условие:
есть симметричная таблица взаимоотншений m(i,j) из диапазона [-100,100], причём m(i,i)=0 найти такие перестановки столбцов (и строк соответсвенно), чтобы функция среднего взаимоотношения во всех группах КГср была максимальной Код:
1 2 3 4 5 6 |
Э-э-э-э-э, дружище, ты меня не понял. Или я плохо объяснил. Я не мог долго ответить, потому что был сильно занят. Сейчас расскажу поподробнее, как производятся расчеты. Таблица взаимоотношений выстраивается совершенно другим образом, а именно на основе социометрии, где все люди «раздают» друг другу оценки по пятибалльной шкале от -2 до 2 (от полного негатива до полного позитива). К примеру, для группы из 6 человек матрица взаимных оценок будет выглядеть следующим образом:
![]() Потом на основе этой таблицы я строю матрицу взаимных психологических связей (ТМ): ![]() Далее, совершая определенные манипуляции с ТМ, я получаю оптимальное решение (разбиение), например, для 6 = 2х3: (1, 3, 5), (2, 4, 6) И уже для этих разбиений я считаю по определенной формуле КГ на основе ТМ, а затем КГср: КГ(1, 3, 5) = 57 КГ(2, 4, 6) = 65 Кгср. = 61 На этом работа «ручного» алгоритма заканчивается и начинается работа алгоритма перебора. Далее я ищу ВСЕ возможные разбиения. Для разбиения вида 2х3 их количество составит 10. Итак, что же мы имеем, выстраивая разбиения по возрастанию по КГср, то бишь вверху будут находиться разбиения с максимальным КГср, а внизу с минимальным: ![]() Красным цветом я выделил искомое разбиение. И вот теперь-то я могу судить об эффективности или неэффективности «ручного» алгоритма, видя занимаемую позицию найденного разбиения. |
вот,я предлагаю хитро сортировать таблицу №2 и сразу получить оптимальное разбиение :) У меня предчуствие, что ручной алгоритм это и делает, и что оно оптимально среди всех разбиений. Как считается КГ? щас строго докажем что зря мучаешься
|
Насчет того, насколько оптимален ручной алгоритм или нет, судить сложно, потому что этот алгоритм разработан мной на основе другого алгоритма, предложенным неким товарищем Поддубным. Но могу сказать одно: он НЕ дает наилучшего решения. Смысл-то как раз не в том, чтобы получить наилучшее решение (это маловероятно), а задача состоит в том, чтобы получить как можно лучшее решение.
А КГ считается следующим образом: КГ = (S(Cij) х 100) / (2 х n х(n-1)), где n - количество членов в подгруппе, а S(Cij) - сумма всех психологических связей в сформированной подгруппе (сумма всех значений соответствующих элементов в ТМ). Например: КГ(1, 2, 3) = (2 + 2 + 1) * 100 / (2 * 3 * (3-1)) = 41,6 Кстати говоря, в предыдущем посте КГ я брал от балды, так что не обращай внимания. Лень было считать врукопашную. :) Ну, а КГср считается, как среднее арфметическое от всех КГi по подгруппам. В нашем случае (6=2х3) это: КГср = (КГ1 + КГ2) / 2 |
Цитата:
Цитата:
Цитата:
|
Цитата:
Цитата:
Цитата:
Цитата:
Ферштейн? ;) |
Примение метода монте-карло:
1. Пусть есть итерационый метод, уточняющий некоторое начальное решение до локального оптимума вблизи этого начального решения. 2. Пусть доказано, что множество, на котором ищется решение ограничено и замкнуто, но содержит больше одного решения (иначе смысла нет, и так всё ясно) 3. Тогда можно случайно (с равномерным распределением) выбрать несколько начальных решений и уточнять их. Чем больше "постреляешь", тем вероятней найти глобально оптимальное решение Всё-таки я склоняю к тому, чтобы сортировать по общей сумме |
Спасибо за советы. Будем думать.
|
Время: 09:49. |
Время: 09:49.
© OSzone.net 2001-