AXT> Симуляцию отжига пробовал?
Даже не слышал. Я, вообще, не зная в какую сторону копать, пробовал сам велосипедить.
Первый вариант, который обкатывал — имитация «резины». По мере удаления объектов от «стандартного удаления» притяжение их линейно (квадратично) растёт, по мере приближения — квадратично (линейно, экспоненциально и т.п., по-разному пробовал) растёт отталкивание. Схема работала отвратительно — поскольку пользователи, никак не высказавшие отношение тоже имеют учитываемую нулевую взаимную репутацию, получалось так, что, вроде, и надо бы подтянуть кого-то в одну сторону, но его не пускают силы отталкивания от промежуточных пользователей. Плюс из-за изначально случайного распределения в среднем каждого пользователя «тащит» в разные стороны...
Только сейчас (вот она сила изложения мыслей по теме в письменном виде — случалось не раз, что промучившись с какой-то проблемой несколько дней, лез на форум (тот же LOR) с описанием проблемы, а пока писал мысли по теме находил сам оптимальное решение — и текст стирал, так и не отправив
) пришла в голову мысль — можно было попробовать добавлять пользователей по одному. Например, взять пару самых активных по отношениям пользователей, уравновесить. Добавить третьего, уравновесить. Добавить четвёртого... Система будет перестраиваться, но в рамках уже изначально формирующейся кластеризации.
Второй вариант — «гравитационный» с поиском потенциального минимума. Выложил грубую сетку (размерность не помню, что-то типа 50x50 или 100x100), «высыпал» туда пользователей и для каждой сетки прописал её потенциал аналогично варианту с «резиной». Т.е. близко от пользователя — высокий барьерный уровень, потом по радиусу он падает, потом начинает снова расти. Считаем такой рельеф по всем юзерам (всё это в отношении одного целевого), потом ищем на рельефе минимум, туда и перемещаем нового пользователя. Точнее, даже не перемещаем, а направляем (я за одну итерацию перемещал не полностью, а с имитацией инерции).
Аналогично искал варианты и с цветом, только что раскладывал уже в трёхмерном пространстве. И куб в случае сетки был более грубым, 8x8x8, ЕМНИП, иначе производительности не хватало — скажем, 2000x2000 юзеров — это уже 4 млн. циклов на каждой итерации.
Сейчас думаю, что вариант с гравитационной сеткой и поочерёдным добавлением юзеров должен быть лучшим из мной рассмотренного. Надо будет попробовать. Заодно и с вычислительной точки будет проще, т.к. расти нагрузка будет поэтапно, по мере добавления юзеров.