[ALI]

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

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

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

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

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

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

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

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