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

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

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

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

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



Это сообщение отредактировал(а) dereyly - 27.3.2008, 15:34

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

Это сообщение отредактировал(а) maxdiver - 27.3.2008, 23:15

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


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

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

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

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

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

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

Это сообщение отредактировал(а) v2v - 29.3.2008, 00:35