Задача следующая: по определенному периметру расположено n-точек(допустим 108, кратное 8ми - рисунок прилагаю), необходимо разбить их на подгруппы по 8 так, чтобы расстояние между точками было минимальным. Есть ли пути решения и какие? Пардон, если повтор, но на форуме не нашел=(

Это сообщение отредактировал(а) hamelleon - 20.1.2012, 14:54

Присоединённый файл ( Кол-во скачиваний: 19 )
 ______.jpg 760,46 Kb

Аплодирую стоя 

Что есть периметр на картинке?
Расстояние между какими точками должно быть минимальным?

Да и в целом вопрос не понятен. Можно сделать пример поменьше (точек на 16 - 24) и показать какое разбиение должно получиться?

Вам нужено гуглить на K-algorithm. Вариантов у него множество. Вот в Википедии описание. Там есть и русский вариант, но он менее полный.

Вариантов алгоритма немеряно - выбирай какой не лень. 

В большинстве описаний одним из основных недостатков будет названа необходимость априори задавать на сколько кластеров (групп) надо делить все множество точек. Но в Вашем случае это не проблема. Просто делите количество точек на 8 и получаете количество групп.

ЗЫ: Пишите если что непонятно. Я когда-то в древности по этому алгоритму что-то считал.

Это сообщение отредактировал(а) _Y_ - 20.1.2012, 21:18