[ALI]

Э-э-э-э-э, дружище, ты меня не понял. Или я плохо объяснил. Я не мог долго ответить, потому что был сильно занят. Сейчас расскажу поподробнее, как производятся расчеты. Таблица взаимоотношений выстраивается совершенно другим образом, а именно на основе социометрии, где все люди «раздают» друг другу оценки по пятибалльной шкале от -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]

вот,я предлагаю хитро сортировать таблицу №2 и сразу получить оптимальное разбиение У меня предчуствие, что ручной алгоритм это и делает, и что оно оптимально среди всех разбиений. Как считается КГ? щас строго докажем что зря мучаешься

[ALI]

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

не в том, чтобы получить наилучшее решение (это маловероятно), а задача состоит в том, чтобы получить как можно лучшее решение. »

я понимаю это как одно и то же тем более множество перестановок конечно, значит наилучшее решение достижимо

алгоритма, предложенным неким товарищем Поддубным »

доказательство алгоритма есть? Я так понимаю, что он даёт локальный минимум на множестве. Есть много методов улучшить такое решение (например на основе монте-карло)

КГ = (S(Cij) х 100) / (2 х n х(n-1)), где n - количество членов в подгруппе, а S(Cij) - сумма всех психологических связей в сформированной подгруппе (сумма всех значений соответствующих элементов в ТМ). »

n фиксировано для разбиения, для оптимизации независимые константы не имеют значения, поэтому достаточно максимизировать S(Cij) - смахивает на задачу линейного программирования. Даже проще - коммивояжёра. Может неправильно понимаю, КГ среднее - не зависит от разбиений? (сумма не зависит от прядка суммирования)

[ALI]

я понимаю это как одно и то же тем более множество перестановок конечно, значит наилучшее решение достижимо »

Дружище, сейчас речь идет о том, чтобы получить как можно лучшее решение с помощью РУЧНОГО алгоритма. Ручной алгоритм, в отличие от алгоритма перебора, дает единственное решение, которое маловероятно получить наилучшим. Поэтому передо мной и стоит задача "подкрутить" ручной алгоритм ТАКИМ ОБРАЗОМ, чтобы решени получилось наиболее оптимальным. А потом уже можно сравнивать это решение и результат работы алгоритма перебора. В переборе, конечно же, можно получить наилучшее решение.

доказательство алгоритма есть?»

Доказательства, к сожалению, нет. У моего алгоритма тем более.

так понимаю, что он даёт локальный минимум на множестве. Есть много методов улучшить такое решение (например на основе монте-карло) »

Так-так-так, а вот с этого момента, пожалуйста, поподробнее.

n фиксировано для разбиения, для оптимизации независимые константы не имеют значения, поэтому достаточно максимизировать S(Cij) - смахивает на задачу линейного программирования. Даже проще - коммивояжёра. »

Максимизировать нужно не КГ (а точнее S(Cij)), хотя его по возможности тожно нужно "вытягивать", а максимизировать необходимо КГср, то бишь КГ, характеризующее ВСЁ разбиение, т.е. несколько подгрупп. Нам ведь нужно получить не одну оптимальную подгруппу, а сразу несколько, образующих оптимальное разбиение.
Ферштейн?

[pva]

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

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

[ALI]

Спасибо за советы. Будем думать.