Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Разделить набор точек на две группы

Автор: _Y_ 27.3.2008, 12:37

В простейшем случае имеется плоскость и на ней точки.
user posted image

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

Что-то у меня ничего кроме перебора не получается

Автор: Akina 27.3.2008, 13:43

Цитата(_Y_ @ 27.3.2008, 13:37

)

Что-то у меня ничего кроме перебора не получается

И не получится, если нет зависимости. Но предварительная сортировка по координатам снизит вычислительные затраты.

Автор: dereyly 27.3.2008, 14:56

Можно использовать принцип карт кохонена... т.е. множество точек итеративно притягивает "точку пересечения"...
user posted image

Автор: maxdiver 27.3.2008, 23:14

Извиняюсь, не совсем понял смысл "перебора".
Имеется в виду сортировка и последующее решение за O(N)?

Автор: SoWa 28.3.2008, 06:56

maxdiver, сортировка уже исключает О(н)

dereyly, можно поподробнее? Плюсик дам smile

Автор: Akina 28.3.2008, 08:56

Цитата(SoWa @ 28.3.2008, 07:56

)

сортировка уже исключает О(н)

Однозначно - но при правильном построении алгоритма - отсечение на сортированном множестве - сортировка и будет самым медленным этапом smile

Автор: dereyly 29.3.2008, 00:10

Суть метода обучения карт Кохонена (ну необязательно карт, ну кохонен для ээтого случая не причем просто навеяло) заключается в последовательном переборе точек и притягивания ближайших кластерных элементов.
Для данного случая алгоритм выглядит примерно так:

Код


n_epoсh=10;
koef=0.4;
dkoef=koef/(n_epoсh+1);
for (int k=0;k<n_epoсh;k++)
{
    for (int i=0;i<kol_tochek;i++)
    {
         classter.x+=koef*(point[i].x-classter.x);
         classter.y+=koef*(point[i].y-classter.y);
    }
   koef-=dkoef;
}

Автор: v2v 29.3.2008, 00:34

Карты Кохонена - штучная нейросеть, работа которой основывается на конкурентном принципе обучения : выходы нейронов конкурируют между собой за право перейти в состояние возбуждения: выходом сети считается нейрон победитель.

Если на данном примере, то это должно выглядеть, как то так:
выбирается некоторый критерий: например сумма расстояния ко всем точкам.
для каждой точки подсчитывается данное растояние.
точка победитель - через которую пройдут перпендикулярные прямые - точка с минимальной суммой.

для более точного подсчёта надо читать теорию по нейронным сетям...