Страницы: 1 2 След.
RSS
оптимальное размещение центров групп
 
Добрый вечер уважаемые!
есть задача
Исходные:
1. имеем на плоскости Н точек, заданных координатами Х и У
2. точки нужно сгруппировать в Г групп, так, чтобы сумма сумм расстояний от точек до центра группы была минимальной
3. с учетом, что количество точек в группе не может быть меньше чем 1 и не может быть больше чем Б
в приложенном файле:
количество точек н = 22
количество групп  г = 4
максимальное количество точек в группе Б = 6

аксиома:
сумма расстояний от точек группы до центра группы минимальна если координаты центра группы равны
х = срзнач(координат Х точек)
у = срзнач(координат У точек)
т.е. минимальной сумма растояний от точек до центра группы будет в случае, когда координаты центра группы равны среднему значению координат Х точек и ср. значению координат У точек всех точек группы

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

эта задача, аналог задач в Избушке формулистов, только она для программистов
не нужно публиковать полное решение задачи
достаточно написать сумму расстояний, и время в сек. за которое ваш код  его нашел
извините, а так же напишите №№ точек, относящиеся к этим центрам 1,2,3.4
победитель тот у кого сумма расстояний + время в сек/100 будет минимальной

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

уважаемые администраторы, тему моно перенести в "Избушку". в "Курилку", в "Работу" (на ваше усмотрение) но тут ее причитает больше людей и вероятность решения - тоже существенно больше, и кстати, присоединяйтесь, шанс есть у всех

ПЫСЫ:
возможно, у Вас еще нет готового решения, но есть интерес к теме, пожалуйста, обозначьте  его ответом: типа я угадаю это решение с 3-х байт  или за 2-3  недели
всем,кто дочитал до этой строки -  спасибо!
отдельное спасибо тем, кто открыл файл)
Изменено: Ігор Гончаренко - 15.04.2020 21:21:25
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Ігор Гончаренко, добрый день, я немного не понял условие
Цитата
2. точки нужно сгруппировать в Г групп, так, чтобы сумма сумм расстояний от точек до центра группы была минимальной
3. с учетом, что количество точек в группе не может быть меньше чем 1 и не может быть больше чем Б
то есть группа может быть из одной точки?
Цитата
в каждой группе получаем свою сумму расстояний от точек до центра группы
задача решена оптимально, когда сумма названых сумм минимальна
сумма расстояний от центра до точки в группе из 3 точек, будет больше чем в группе из любых 2 точек этого треугольника. Каким образом определять количество точек в группе
 
Доброе время суток
Цитата
msi2102 написал:
то есть группа может быть из одной точки?
Не может. Групп всего 4
Цитата
Ігор Гончаренко написал:
количество точек н = 22
количество групп  г = 4
Следовательно возможно только 6 + 6 + 6 + 4 = 22 точки, 6 + 6 + 5 + 5 = 22.  Попытка получить группу из 3 и менее точек приведёт к нарушению условия
Цитата
Ігор Гончаренко написал:
максимальное количество точек в группе Б = 6
Такой какой-то странно ограниченный кластерный анализ. Игорь, а можно ссылку на формульное решение?
 
Андрей VG, то есть обязательное условие, что участвуют все точки
 
в условиях задачи нет противоречий
каждая группа может содержать произвольное количество точек от 1 до Б
попытка получить группу из 3 и менее точек приводит к выводу, что при данных исходных НЕ ВОЗМОЖНО наличие групп, содержащих менее 4-х точек
формульного решения у меня нет, пока у меня нет никакого решения
и задача тут звучит так:
нужно из 22-х заданных точек укомплектовать 4 группы любым допустимым количеством точек, (но не более 6 в группе) так чтобы получить минимальную сумму расстояний (каких расстояний - я написал в первом сообщении)

извините, понятно, что интересует решение в общем виде
если для этих же 22 точек указать максимум в группе Б = 10
то вариантов составов групп становиться по-больше: 10 10 1 1, 10 9 2 1,  10 8 3 1, 10 8 2 2, 10 7 4 1, 10 7 3 2, 10 6 5 1 .... 6 6 5 5
.
и желательно что бы при исходных 1 тыс. точек, 50 групп, до 50 точек в группе результат вычислялся за несколько минут, а не за несколько лет непрерывных вычислений

спасибо за внимание
всем удачи!
Изменено: Ігор Гончаренко - 16.04.2020 13:27:20
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Цитата
Ігор Гончаренко написал:
то вариантов составов групп становиться по-больше: 10 10 1 1,
Значит группа из одной точки имеет место быть, тогда ее центр (как группы) равен 0?
 
да об этом сказано сначала: в группе может быть от 1 до Б точек. одна точка - это такая группа, состоящая из 1 точки.
координаты центра  такой группы равны координатам данной точки и вобщем-то не важны, а сумма растстояний от центра, до точки равна 0 - это важно!
т.е. группы состоящие из 1 точки никак не влияют на общую сумму расстояний, т.е. практически можно выбросить из расчетов некоторые аномально далекие от всех остальных точки, но это все часности этого общего решения.
общая задача собрать точки в группы так, чтобы общая сумма растояний была минимальной
количество точек и их координаты задано, количество групп - задано, есть 1 ограничение в группе не может быть более Б точек.
дальше вы вольны тусовать точки по любым группам - главное добиться минимальной общей суммы расстояний от центров группы, до каждой точки группы.
Изменено: Ігор Гончаренко - 16.04.2020 14:26:21
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
интересная задача, жалко я кодить не умею, но алгоритм разработать интересно было бы. Сразу лезут идеи стартовать от нуля-по сумме значений координат х и у найти в порядке возрастания все ближайшие к началу координат точки, объединив их в группу и исключив из списка  точек из оставшихся начать формировать вторую группу. А вот куда это приведет хз:) мне бы месяца хватило чтоб набросать вариант1 :)
Изменено: ПРОИЗВЕД - 16.04.2020 22:49:14
 
начало положено, пошел спать:)
 
если решите задачу, скажите пожалуйста потом-так или нет?:)
 
ПРОИЗВЕД, все три сообщения можно было уместить в одно.
 
Напоминает задачу по вычислению оптимальных координат для установки сотовых вышек.
Надо будет попробовать поломать голову. Самому интересно, PQ + PP сможет ли с таким справиться.
Вот горшок пустой, он предмет простой...
 
Ігор Гончаренко, расстояние от центра группы до точки в группе считаем в обычном порядке? Корень из сумм квадратов разностей координат?
Изменено: quasarrr - 17.04.2020 06:35:21
 
да все это безобразие происходит на плоскости
и в том файле, что выложен в первом сообщении, если поставить единичку на пересечении строки с точкой и колонки с ТОС - формулы уже начинают считать расстояния
понятно, что в строке (у точки) может быть ТОЛЬКО одна единичка, а в колонке ТОС их должно быть от 1 до Б шт. и то, что нарисовал ПРОИЗВЕД дало общую сумму 402.06

а в этом файле ниже вы можете посмотреть мои сумбурные попытки решить задачу хоть как-то...
файл полезен тем, что в нем формируется картинка решения, которая на много информативнее таблиц, где есть все та же информация.
при указанных координатах и 6 ТОС - все даже выглядит "как решение"
но стоит только написать 5 ТОС, и видно одно явно не логичное присвоение (одна точка явно не в том ТОСе)
а 4 ТОС таких точек видно шт.3-5, можете посмотреть в файле
Изменено: Ігор Гончаренко - 17.04.2020 14:26:15
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Задача очень интересная, когда решал задачу коммивояжера, хотел использовать подобную группировку точек для упрощения расчетов
Для исходных данных у меня получилось найти распределение по группам с суммарной длинной - 402,057599436519
Решал через Поиск Решения, поэтому метод не подходит как универсальный.

Для общей задачи думаю подойдет следующий алгоритм
Вначале распределяем точки по группам жадным алгоритмом:
1. Выбираем любую точку (первую или крайнюю) и заносим в первую группу
2. Далее выбираем наиболее отдаленную точку от первой группы и заносим ее во вторую
3. Выбираем свободную точку, которая наиболее отдалена от уже имеющихся групп и заносим как первую точку в новую группу
4. Повторяем шаг 3 пока не будут заполнены все группы по 1й точке
5. Перебираем все свободные точки и заносим в свободную групп ту точку, которая приводит к наименьшему увеличению суммарной длины
6. п.5 повторяем пока не закончатся все свободные точки

Жадный алгоритм уже может дать приемлемый результат, но вряд ли оптимальный
Далее улучшаем найденное решение (что то типа имитации отжига или 2-opt оптимизация применяемая в задаче коммивояжера)
Улучшение можно получить двумя способами: обменивая точки между группами либо перемещая точку из одной группы в другую, если в последней есть свободное место
На каждом этапе выбираем наилучший обмен и повторяем до тех пор пока улучшения больше невозможны

Не гарантировано, что будет найдено оптимальное решение, но должно быть приемлемым и за разумное время

Также можно подумать в сторону генетических алгоритмов или алгоритмов муравьиных колоний
 
Цитата
MCH написал:
5. Перебираем все свободные точки и заносим в свободную групп ту точку, которая приводит к наименьшему увеличению суммарной длины
Думается должно быть какое-то ограничение по удаленности, если уже известны координаты центров групп-то искомая точка находится не далее прямой, проведенной через соседствующие центры групп, находящиеся в секторе ограниченного угла, например 120 градусов, может меньше, смотреть надо
Изменено: ПРОИЗВЕД - 17.04.2020 14:20:45
 
Цитата
Ігор Гончаренко написал:
при указанных координатах и 6 ТОС - все даже выглядит "как решение"
У меня для 6 групп получилось следующее решение:
1,15
2,4,5,13,20,21
3,10,14
6,8,16
7,17,18
9,11,12,19,22
Суммарная длина - 270,77

Для 5 групп: 322,20
1,3,10,14,15
2,4,5,13,20,21
6,8,16
7,17,18
9,11,12,19,22

Для 4 групп: 402,06
1,3,10,14,15
2,4,5,13,20,21
6,7,8,16,17,18
9,11,12,19,22

Все решено не спортивно (через "Поиск Решения")
Попробую подумать над алгоритмом, который описал выше
 
MCH, спасибо!
я на основании выложенных идей уже от одной ошибки у себя в алгоритме избавился
что-то меня подтолкнуло  в блоке формирования начальных точек выбирать не точку, а пару точек (максимально близко расположенная пара, находящаяся на достаточном расстоянии от пар уже размещенных в группах)
а если точек меньше чем 2*Групп - то уже точно, что не все группы будут содержать 2 точки
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Цитата
MCH написал:
2. Далее выбираем наиболее отдаленную точку от первой группы и заносим ее во вторую
Михаил, а можно подробнее про такой критерий? Попробовал как точка, имеющая максимальную сумму расстояний до уже определённых точек группы одноточечных центров кластеризации на предполагаемом наборе в 1000 точек и 50 центров кластеризации. Но, по такому критерию одноточечные центры располагаются по "кругу" границе набора точек.
Изменено: Андрей VG - 18.04.2020 11:48:22
 
Получилось набросать макрос (см. вложение)
для 6ти групп нашлось решение лучше, чем указано в 17 сообщении, а вот для 5ти групп решение хуже

PS: На большом количестве точек не проверял, возможно будет долго считать и не совсем оптимально
Изменено: MCH - 18.04.2020 02:17:04
 
Сделал пример для 100 точек на 6 групп
Визуально вроде приемлемо, но все таки не оптимально, результат может меняться в зависимости от того, какую начальную точку мы выбираем
И считает уже заметно дольше
Изменено: MCH - 18.04.2020 10:35:33
 
MCH,
виглядит очень логично. похоже. на приемлемое решение
понятно, что минимальная сумма расстояний - это идеальный результат, но идеальный результат, который можно достичь за 5 суток расчетов - это фигня, по сравнению с не идельным, у которого эта самая сумма будет на 5% больше от идеальной, но получена за 5 минут (а лучше за 10 сек), который выглядит логично и не содержит явных проколов.
то, что я вижу в файле вигладит логично и очень убедительно!
я уже боюсь загадывать когда сделаю свой вариант, я уже 3-4 раз существенно меняю принцип сбора точек в группы, вроде нащупал идею и смогу дожать до рабочего макроса
 
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Странная какая-то аксиома.
Цитата
Ігор Гончаренко написал:
аксиома:сумма расстояний от точек группы до центра группы минимальна если координаты центра группы равны
х = срзнач(координат Х точек)
у = срзнач(координат У точек)
В общем всё свелось к k-means, c-means и вариациям на тему - и никакого тебе ограничения
Цитата
Ігор Гончаренко написал:
максимальное количество точек в группе Б = 6
:(
 
В коде из 21 сообщения нашел у себя небольшую ошибку, исправил ее, также внес правки в код, считать стало быстрее: 100 точек - пару секунд
 
Цитата
MCH написал:
Странная какая-то аксиома.
Может в таком случае сравнивать сумму квадратов расстояний (как раз добьемся минимизации суммарного квадратичного отклонения), при этом более удаленные точки имеют существенно худший результат
Выкладываю код с этим подходом, в ситуации 22/4, 22/5, 22/6 алгоритм решает более менее оптимально

UPD: Сделал пример на 200 точек и 6 групп, вроде получается нормально
Уверен что есть более оптимальное решение, но даже текущее может быть  использовано на практике
Изменено: MCH - 18.04.2020 11:46:55
 
Цитата
Андрей VG написал:
Странная какая-то аксиома.
я не привожу доказательства - поэтому это аксиома
если для группы точек есть точка, сумма расстояний от которой ко всем точкам группы меньше чем от сумма расстояний от геометрического центра этой группы, расскажите мне как определить ее координаты
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Добрый день! Андрей прав. Еще один пример. Рассмотрим систему из трех точек: (0,0), (1,0), (1,0). До точки (1,0) сумма расстояний равна 1, до остальных точек плоскости больше. Точку со средними координатами иногда еще определяют как центр тяжести системы материальных точек. Так что можно переформулировать условия задачи о разбиении точек на группы с целью минимизации сумм расстояний точек групп до центра тяжести групп.
Что касается определения точки плоскости, сумма расстояний от которой до заданных точек минимальна, то я не знаю, есть ли общее решение. Для треугольника эта точка называется точкой Ферма.

P.S. Оказывается, это классическая проблема.
Изменено: sokol92 - 18.04.2020 13:09:48
Владимир
 
sokol92,
спасибо! который раз.
Андрей VG,
не  приведено доказательств, потому что его нет и это не аксиома, это мое заблуждение(((
MCH,
извините,
геометрический центр группы точек - не есть точка сумма расстояний от которой до всех точек группы минимальна(((
но такая точка есть, и ее поиск - отдельная задача (похоже с не самыми простыми вычислениями)
можно поискать решение и этой  отдельной задачи, но похоже, что все там будет не просто с точки зрения количества вычислений

тут, пока остановимся на том, что  среднее из Х и среднее из У - и есть центр группы точек, т.е. условия не меняются (появилось только понимание того что я ошибся и что точка среднее из Х и среднее из У - не определяет положение оптимальной точки, с точки зрения суммы расстояний)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
sokol92, огромное спасибо за исследование вопроса!
Ігор Гончаренко, иногда, как расширение подхода, в качестве определения центра кластера используют не среднее по координатам его точек, а медиану координат - метод k-медиан.
Изменено: Андрей VG - 18.04.2020 17:46:32
 
Игорь, мое решение (например из 25 поста) подошло или нужно еще что то придумывать?

Относительно центра группы (чтобы расстояние для каждой точки группы было минимальным), которое будет отличатся от точки о средними координатами, так его можно найти позже, когда группы уже сформированы, используя "поиск решения", на тестируемых данных получается немного улучшить результат.

По скорости моего алгоритма, на 100-200 точек он работает относительно быстро, на 1000 точек не проверял, но думаю, что можно немного ускорить алгоритм, за счет другого хранения данных в группах (правда это потребует существенно изменения кода).
Либо можно алгоритм переписать на другой более быстрый ЯП (С++ или Freebasic), на Freebasic немного придется переделывать, при этом можно разбить алгоритм на потоки, что ускорит вычисления в разы
Изменено: MCH - 20.04.2020 13:50:53
Страницы: 1 2 След.
Наверх