Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   [решено] Помогите с комбинаторной задачей! (http://forum.oszone.net/showthread.php?t=121284)

ALI 28-10-2008 15:56 936098
Помогите с комбинаторной задачей!
 
Народ, подскажите, пожалуйста, как лучше создать и реализовать алгоритм. Может быть, кто-то уже сталкивался с подобной комбинаторной задачей. Суть в следующем: есть 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, как показано в таблице.

pva 28-10-2008 23:24 936593
пока не понятно, что именно собираешься реализовывать, попробую показать как я это вижу
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
a c  b d    a<c, b<d, a<b
a d  b c    a<d, b<c, a<d
алгоритм перебора: последовательно выбираем все элементыв сортированном списке и помечае отобранные
1. выбирать первые элементы групп лучше с начала списка (и не трогать последние K-1)
2. выбирать остальные элементы групп лучше с конца списка, чтобы хватило для заполнения самых последних групп
Таким образом переберёшь все и ни разу не повторишься

ALI 05-12-2008 15:13 973199
Добрый день, дамы и господа! Некоторое время назад я задавал вопрос по поводу комплектования малых подгрупп.
Задачу выполнил с помощью pva и используя данный алгоритм (функция формирования перестановок).
Но! Дело в том, что при количестве людей большем 12, алгоритм перебора начинает захлебываться, то есть жутко тормозить или зависать. Поэтому встает вопрос: как можно ускорить процесс? Вкратце опишу суть того, что я делаю: формирую всевозможные перестановки N людей. На определенном шаге отсекаю все варианты, начинающиеся с 2. Варианты, начинающиеся с 3, 4 и т.д. уходят автоматически. Таким образом, количество перестановок резко сокращается. На каждом шаге формирования перестановки я осуществляю проверку на невозрастание внутри подгруппы и невозрастание первых людей подгрупп в соотвествии с алгоритмом, предложенным pva, . Если все ОК, то записываю перестановку в поток (TStream). После записи всех "правильных" перестановок (c учетом подгрупп) в поток я считываю данные из потока в ClientDataSet и далее они автоматически переносятся в DBGrid.
Понятно, что промежуточные звенья (TStream и ClientDataSet) значительно тормозят процесс, но даже если их отключить и оставить алгоритм формирования перестановок работающим "вхолостую", то процесс все равно захлебывается. Что делать? Как выкрутиться из этой непростой ситуации?

pva 06-12-2008 21:40 974116
ALI, вот код, который я использовал для проверки (Metrowerks codewarrior 8.0):
Код:
#include <windows.h>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
//------------------------------------

class permutation1
{
    vector<int> _current;
    vector<int> _avaible;
    unsigned _stack_level;

    static vector<pair<unsigned,unsigned> > _program;
    static unsigned _gp_count, _gp_size, _stats;

    permutation1(unsigned size);

    permutation1(
            const permutation1& prev,
            unsigned value_avaible,
            unsigned value_permuted);

    void exec();

public:

    static void main(unsigned gp_count, unsigned gp_size);
};

vector<pair<unsigned,unsigned> > permutation1::_program;
unsigned permutation1::_gp_count, permutation1::_gp_size, permutation1::_stats;

void permutation1::main(unsigned gp_count, unsigned gp_size)
{
    if (gp_size && gp_count)
    {
        _gp_count = gp_count;
        _gp_size  = gp_size;
        _stats    = 0;

        // составляем программу выборок
        _program.reserve(gp_count*gp_size);

        unsigned long time1 = GetTickCount();

        for (unsigned group1=0; group1<gp_count; ++group1)
        {
            _program.push_back(make_pair(-1, group1*gp_size));
        }

        for (unsigned group1=gp_count; 0<group1--; )
        {
            for (unsigned element1=gp_size; 0<--element1; )
            {
                unsigned offset1 = group1*gp_size;
                _program.push_back(make_pair(offset1, offset1 + element1));
            }
        }

        permutation1(gp_count*gp_size).exec();

        unsigned long time2 = GetTickCount();

        cout << "permutation count: " << _stats << "\n"
            "finished in: " << double(time2-time1)/1000. << " seconds\n";
    }
    else
    {
        throw invalid_argument("permutation1::main nonzero both count and size expected");
    }
}

permutation1::permutation1(unsigned size) :
    _current(size),
    _avaible(size),
    _stack_level()
{
    for (unsigned n=0; n<size; ++n)
    {
        _avaible[n] = n;
    }
}

permutation1::permutation1(
        const permutation1& prev,
        unsigned value_avaible,
        unsigned value_permuted) :
    _current(prev._current),
    _avaible(prev._avaible.size()-1),
    _stack_level(prev._stack_level+1)
{
    copy(prev._avaible.begin() + value_avaible + 1, prev._avaible.end(),
            copy(prev._avaible.begin(), prev._avaible.begin() + value_avaible, _avaible.begin()));

    _current[value_permuted] = prev._avaible[value_avaible];
}


void permutation1::exec()
{
    if (_stack_level < _program.size())
    {
        pair<unsigned,unsigned>& instr1(_program[_stack_level]);

        if (instr1.first != -1)
        {
            unsigned left_to_fill = instr1.second-instr1.first;

            // выбор элементов
            for (unsigned element1 = _avaible.size();
                    left_to_fill <= element1 &&
                    _current[instr1.first]<_avaible[(--element1)-left_to_fill]; )
            {
                permutation1(*this,
                    /*доступный элемент*/ element1,
                    /*что заменить*/ instr1.second).exec();
            }
        }
        else
        {
            // выбор групп
            unsigned group1=0;

            for (; group1<_avaible.size() && _avaible[group1]<=int(instr1.second); ++group1)
            {
                permutation1(*this, group1, instr1.second).exec();
            }

            if (_avaible.size()<=group1) throw logic_error("bug found: permutation1::avaible no group candidate");
        }
    }
    else
    {
        for ( unsigned g=0; g<_gp_count; ++g)
        {
            cout << "group ";
            cout.width(3);
            cout << g << ": ";

            for ( unsigned f=0; f<_gp_size; ++f)
            {
                cout.width(4);
                cout << _current[g*_gp_size + f];
            }

            cout << "\n";
        }

        cout << "\n";

        ++_stats;
    }
}
//------------------------------------

int main()
{
    filebuf outbuf;
    outbuf.open("output.txt", ios::out|ios::app);
    streambuf* coutbuf = cout.rdbuf(&outbuf);

    try
    {
        permutation1::main(7,3);
    }
    catch(exception& e)
    {
        clog << e.what() << "\n";
    }

    cout.rdbuf(coutbuf);
    return 0;
}
//------------------------------------
На машинке pentium-4, 1600 МГц, 768 МБ ОЗУ, WinXP sp2 результаты следующие:
использование памяти 384 МБ, в памяти:
система, qip, winamp, IDE компилятора, файловый менеджер, браузер, справочная литература, антивирь и диспетчер задач.. ну и программа конечно.
параметры: 4x3 (итого 12 чел)
сборка debug: 127805 вариантов за 10.359 секунд
сборка release: 127805 вариантов за 2.61 секунд
не захлебнулось ;-)
output:

ALI 07-12-2008 16:37 974634
Как файл скачать-то?
Дык, с 12-ю людьми и у меня все нормально, а вот если речь заходит о 16 и более, то там начинаются проблемы.

pva 07-12-2008 20:50 974886
у меня случались какие-то глюки, когда я его засылал. Проще собери и получи за 2 секунды результат. Прошу прощения, не заметил "больше". Попробовал на большем числе - действительно уходит в большую обработку. Причём память использует на прежднем уровне. Я заметил, что на один результат в среднем уходит 100 байт. 120 тыс. комбинаций даёт 1.2 меговый файл. Когда запустил 4х4, подождал 30 минут, получил 1.5 гиговый файл и дальше ждать не стал. Вся проблема в том, что слишком большое число комбинаций. Я даже боюсь что может не хватить 32-разрядного регистра чтобы подсчитать их количество. Задача приобретает нерешаемый в силу временных ограничений характер.
Если всё-же хочешь ускорить процесс, предлагаю ввести распараллеливание (сейчас в моде многоядерные машины). Написаный выше мной код это сделать позволяет, т.к. на каждом следующем этапе используется своя независимая копия памяти. А вообще советую пересмотреть задачу

ALI 08-12-2008 12:56 975414
Я, скорее всего, переделаю задачу через сочетания:
http://forum.algolist.ru/algorithm-m...-podgrupp.html
Как там написал один товарисч, сочетаний значительно меньше, чем перестановок, посему алгоритм времени будет жрать меньше.

pva 09-12-2008 10:12 976158
Цитата:
сочетаний значительно меньше
Задача детерминированная, количество решений не зависит от метода. Лучше меняй постановку на попроще

ALI 09-12-2008 19:23 976617
Как ты представляешь себе смену постановки на попроще, а?
Смысл вот в чем: у меня есть "ручной" алгоритм, разработанный, кстати говоря, мной, в котором люди разбиваются на подгруппы за конечное число шагов на основе социометрии. Но проблема в чем? Проблема состоит в том, чтобы разбить этих людей ТАК, чтобы получить оптимальное решение с точки зрения взаимоотношений в исходной группе. Т.е. надо получить ТАКИЕ подгруппы, где люди меньше всего конфликтуют между собой.
Получив решение на основе "ручного" алгоритма, я хочу посмотреть какое место оно будет занимать в "иерархии" разбиений, полученных методом перебора. Иерархия выстраивается по КГср (средний коэффициент когерентности).
Пояснение: КГ (коэффициент когерентности) - мера связанности подгруппы, лежащая в пределах от -100 до 100. То бишь подгруппа с КГ=-100 - это самая худшая группа, которая только может существовать. Соответственно, подгруппа с КГ = 100 - это идеальная подгруппа.
В каждом разбиении считаются КГi (КГ для каждой подгруппы), КГср, а далее они выстраиваются по возрастанию, т.е. наверху таблицы находятся разбиения с максимальным КГср, а внизу - с минимальным. Эта таблица и есть результат работы алгоритма перебора. Потом я ищу в общей массе разбиение, полученное ручным методом и смотрю, насколько высоко или низко оно находится с точки зрения КГср. В зависимости от полученного результата, я буду "подкручивать" ручной алгоритм, чтобы он поднялся как можно выше. Поэтому, так или иначе, но мне приходится просматривать ВСЕ разбиения.
Если ты когда-нибудь сталкивался с транспортной задачей, задачей о рюкзаке, теорией графов, СМО и др. подобными задачками, то это из этой оперы. :)

pva 09-12-2008 20:34 976675
ВОТ!!! совершенно другое дело! я поправлю условие:
есть симметричная таблица взаимоотншений m(i,j) из диапазона [-100,100], причём m(i,i)=0
найти такие перестановки столбцов (и строк соответсвенно), чтобы функция среднего взаимоотношения во всех группах КГср была максимальной
Код:
  1 2 3 4 5 6
1 А A A - - -
2 А А A - - -
3 А А А - - -
4 - - - Б Б Б
5 - - - Б Б Б
6 - - - Б Б Б
Вот теперь совершенно дикая идея: пусть ГКi линейно относительно ГК. написать критерий и отсортировать список по возрастанию шаблоном std::sort (пузырьковой сортировкой). Критерий: один элемент считается больше другого, если он при перестановке местами даёт больший вклад в ГКi. Может я туманно выразился :SCRATCH:, но по идее компьютеру отсортировать 100 записей - сущая безделица, даже по трудному критерию.

ALI 26-12-2008 18:10 990974
Э-э-э-э-э, дружище, ты меня не понял. Или я плохо объяснил. Я не мог долго ответить, потому что был сильно занят. Сейчас расскажу поподробнее, как производятся расчеты. Таблица взаимоотношений выстраивается совершенно другим образом, а именно на основе социометрии, где все люди «раздают» друг другу оценки по пятибалльной шкале от -2 до 2 (от полного негатива до полного позитива). К примеру, для группы из 6 человек матрица взаимных оценок будет выглядеть следующим образом:



Потом на основе этой таблицы я строю матрицу взаимных психологических связей (ТМ):



Далее, совершая определенные манипуляции с ТМ, я получаю оптимальное решение (разбиение), например, для 6 = 2х3:
(1, 3, 5), (2, 4, 6)
И уже для этих разбиений я считаю по определенной формуле КГ на основе ТМ, а затем КГср:
КГ(1, 3, 5) = 57
КГ(2, 4, 6) = 65
Кгср. = 61
На этом работа «ручного» алгоритма заканчивается и начинается работа алгоритма перебора.
Далее я ищу ВСЕ возможные разбиения. Для разбиения вида 2х3 их количество составит 10. Итак, что же мы имеем, выстраивая разбиения по возрастанию по КГср, то бишь вверху будут находиться разбиения с максимальным КГср, а внизу с минимальным:



Красным цветом я выделил искомое разбиение. И вот теперь-то я могу судить об эффективности или неэффективности «ручного» алгоритма, видя занимаемую позицию найденного разбиения.

pva 27-12-2008 19:14 991680
вот,я предлагаю хитро сортировать таблицу №2 и сразу получить оптимальное разбиение :) У меня предчуствие, что ручной алгоритм это и делает, и что оно оптимально среди всех разбиений. Как считается КГ? щас строго докажем что зря мучаешься

ALI 27-12-2008 20:43 991741
Насчет того, насколько оптимален ручной алгоритм или нет, судить сложно, потому что этот алгоритм разработан мной на основе другого алгоритма, предложенным неким товарищем Поддубным. Но могу сказать одно: он НЕ дает наилучшего решения. Смысл-то как раз не в том, чтобы получить наилучшее решение (это маловероятно), а задача состоит в том, чтобы получить как можно лучшее решение.
А КГ считается следующим образом:
КГ = (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

pva 28-12-2008 21:54 992489
Цитата:
Цитата ALI
не в том, чтобы получить наилучшее решение (это маловероятно), а задача состоит в том, чтобы получить как можно лучшее решение. »
я понимаю это как одно и то же :) тем более множество перестановок конечно, значит наилучшее решение достижимо
Цитата:
Цитата ALI
алгоритма, предложенным неким товарищем Поддубным »
доказательство алгоритма есть? Я так понимаю, что он даёт локальный минимум на множестве. Есть много методов улучшить такое решение (например на основе монте-карло)
Цитата:
Цитата ALI
КГ = (S(Cij) х 100) / (2 х n х(n-1)),
где n - количество членов в подгруппе, а S(Cij) - сумма всех психологических связей в сформированной подгруппе (сумма всех значений соответствующих элементов в ТМ). »
n фиксировано для разбиения, для оптимизации независимые константы не имеют значения, поэтому достаточно максимизировать S(Cij) - смахивает на задачу линейного программирования. Даже проще - коммивояжёра. Может неправильно понимаю, КГ среднее - не зависит от разбиений? (сумма не зависит от прядка суммирования)

ALI 30-12-2008 16:53 993829
Цитата:
Цитата pva
я понимаю это как одно и то же тем более множество перестановок конечно, значит наилучшее решение достижимо »
Дружище, сейчас речь идет о том, чтобы получить как можно лучшее решение с помощью РУЧНОГО алгоритма. Ручной алгоритм, в отличие от алгоритма перебора, дает единственное решение, которое маловероятно получить наилучшим. Поэтому передо мной и стоит задача "подкрутить" ручной алгоритм ТАКИМ ОБРАЗОМ, чтобы решени получилось наиболее оптимальным. А потом уже можно сравнивать это решение и результат работы алгоритма перебора. В переборе, конечно же, можно получить наилучшее решение.
Цитата:
Цитата pva
доказательство алгоритма есть?»
Доказательства, к сожалению, нет. У моего алгоритма тем более. :)
Цитата:
Цитата pva
так понимаю, что он даёт локальный минимум на множестве. Есть много методов улучшить такое решение (например на основе монте-карло) »
Так-так-так, а вот с этого момента, пожалуйста, поподробнее.
Цитата:
Цитата pva
n фиксировано для разбиения, для оптимизации независимые константы не имеют значения, поэтому достаточно максимизировать S(Cij) - смахивает на задачу линейного программирования. Даже проще - коммивояжёра. »
Максимизировать нужно не КГ (а точнее S(Cij)), хотя его по возможности тожно нужно "вытягивать", а максимизировать необходимо КГср, то бишь КГ, характеризующее ВСЁ разбиение, т.е. несколько подгрупп. Нам ведь нужно получить не одну оптимальную подгруппу, а сразу несколько, образующих оптимальное разбиение.
Ферштейн? ;)

pva 31-12-2008 11:01 994378
Примение метода монте-карло:
1. Пусть есть итерационый метод, уточняющий некоторое начальное решение до локального оптимума вблизи этого начального решения.
2. Пусть доказано, что множество, на котором ищется решение ограничено и замкнуто, но содержит больше одного решения (иначе смысла нет, и так всё ясно)
3. Тогда можно случайно (с равномерным распределением) выбрать несколько начальных решений и уточнять их. Чем больше "постреляешь", тем вероятней найти глобально оптимальное решение

Всё-таки я склоняю к тому, чтобы сортировать по общей сумме

ALI 01-01-2009 14:10 994992
Спасибо за советы. Будем думать.


Время: 19:08.

Время: 19:08.
© OSzone.net 2001-