Delphi - [решено] Помогите с комбинаторной задачей!

[pva]

ВОТ!!! совершенно другое дело! я поправлю условие:

есть симметричная таблица взаимоотншений 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 записей - сущая безделица, даже по трудному критерию.

[pva]

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

[pva]

Насчет того, насколько оптимален ручной алгоритм или нет, судить сложно, потому что этот алгоритм разработан мной на основе другого алгоритма, предложенным неким товарищем Поддубным. Но могу сказать одно: он НЕ дает наилучшего решения. Смысл-то как раз не в том, чтобы получить наилучшее решение (это маловероятно), а задача состоит в том, чтобы получить как можно лучшее решение.

А КГ считается следующим образом:

КГ = (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]

Цитата ALI:



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

Delphi - [решено] Помогите с комбинаторной задачей!

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


Цитата ALI:



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

Delphi - [решено] Помогите с комбинаторной задачей!

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



КГ = (S(Cij) х 100) / (2 х n х(n-1)),

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

Delphi - [решено] Помогите с комбинаторной задачей!

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

[ALI]

Цитата pva:



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

Delphi - [решено] Помогите с комбинаторной задачей!

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


Цитата pva:



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

Delphi - [решено] Помогите с комбинаторной задачей!

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


Цитата pva:



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

Delphi - [решено] Помогите с комбинаторной задачей!

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


Цитата pva:



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

Delphi - [решено] Помогите с комбинаторной задачей!

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

Ферштейн?

[pva]

Примение метода монте-карло:

1. Пусть есть итерационый метод, уточняющий некоторое начальное решение до локального оптимума вблизи этого начального решения.

2. Пусть доказано, что множество, на котором ищется решение ограничено и замкнуто, но содержит больше одного решения (иначе смысла нет, и так всё ясно)

3. Тогда можно случайно (с равномерным распределением) выбрать несколько начальных решений и уточнять их. Чем больше "постреляешь", тем вероятней найти глобально оптимальное решение



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

[ALI]

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