Страницы: Пред. 1 2
RSS
оптимальное размещение центров групп
 
Исправил код своей программы, алгоритм не менял, изменил метод хранения данных, что уменьшило расчеты
100 точек считает менее секунды, 200 точек - 2-3 секунды

PS: Запустил алгоритм на 1000 случайных точках, 50 групп с не более чем 50 точек в группе, считалось минут 20
Так это на VBA, если перенести алгоритм на Freebasic да еще разбить его на потоки, можно 1000 точек за пару минут расчитать
Изменено: MCH - 21.04.2020 21:47:49
 
Всем привет! Интересная тема и обсуждения. Сейчас нет времени вникать, но если будет необходимость, могу перенести расчет в xll или dll.
«Бритва Оккама» или «Принцип Калашникова»?
 
MCH,
100 точек за секунду - это то, что хотелось получить
спасибо!
куда отправить деньги? ага, вижу
Изменено: Ігор Гончаренко - 21.04.2020 12:24:00
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
MCH, у Вас при максимальном количестве точек 50 (количество групп 6) сумма составляет 3088,2, а при количестве точек 40 (количество групп 6) сумма составляет 3087,2. При большем количестве точек в группе увеличивается количество вариантов и вариант с меньшим количеством должен войти в их число, а следовательно и сумма не должна превышать вариант с меньшим количеством точек.
 
Цитата
msi2102 написал:
а следовательно и сумма не должна превышать вариант с меньшим количеством точек
Алгоритм построен на основе жадного алгоритма с последующей оптимизацией найденного решения, поэтому он не находит абсолютный минимум а сводится к локальному минимум.
На решение влияет - какую начальную точку мы выбираем и как первоначально распределяем точки по группам, поэтому можно несколько раз запустить решение с выбором разных начальных точек и выбрать наилучшее решение.
Если реализовывать более сложную оптимизацию, то это замедлит решение в десятки/сотни/тысячи раз
 
Реализовал расчет в FreeBasic, версия на 64-бит считает быстрее, чем 32-бит
при этом параллельно решается несколько вариантов и выбирается лучшее решение

У меня 500 точек (10 групп не более 60 точек) считает менее 10 секунд
1000 точек (10 групп не более 120 точек) - около минуты
1000 точек (50 групп не более 50 точек) - 5 минут
Ссылка для скачивания: https://yadi.sk/d/9655fZJ9z5J_aQ
Изменено: MCH - 23.04.2020 16:40:30
 
хорошо, спасибо!
странно, что не зацепило никого больше(((
тут на самом деле хорошее поле не для поиска строгой математики и перевода ее в код, а для нахождения чего-то  интересного, что может из хаоса случайных точек найти способ их логичного группирования
при 15-20 точках и 3-5 группах очень часто эти решения визуально бросаются в глаза и очевидны, замечательно, когда алгоритм на таких данных повторяет увиденный вами способ группировка, или вдруг найдет что-то поинтереснее)
а при исходных несколько сотен точек и 15-20 центров - решение совершенно перестает быть очевидным и тут точно нужен алгоритм
еще раз - странно, что никого не зацепило, а могли бы появиться неожиданные решения. все равно ведь по домам сидите, самое время ударить серым веществом по нестандартной задаче.
могли бы потом на каком-то случайном наборе точек, и таких же от балды заданных количестве групп и максимуме в группе написать полученную сумму, затраченное время и результат в конце концов.

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

и самое главное: решение может быть не самым оптимальным, но должно быть получено по возможности быстро
алгоритм, в котором сумма расстояние окажется на 1-3% больше, чем у более строгого решения гораздо привлекательнее если он может выдать это решение за несколько минут, а не за несколько дней расчетов
Изменено: Ігор Гончаренко - 23.04.2020 01:01:31
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Игорь, хотелось бы узнать, какова конечная задача, в которой необходимо группировать точки?
 
конечная цель учебно практическая
есть К координат "Обьектов" на местности, есть все необходимое для разворачивания С "Сервисных центров", сервисный центр может обслуживать не более Б Обьектов
задача разместить сервисные центры так чтобы сумма расстояний от всех Сервисных центров к всем обслуживаемым ими Обьектам была минимальной

- в теории МОЖНО найти наилучшее решение
- в учебных целях можно потратить на расчеты несколько дней и получить что-то близкое к наилучшему решению
- на практике  - решение нужно сейчас, как только получены координаты последнего обьекта, нужно определить координаты и приступить к разворачиванию СЦ
на практике 100-200 обьектов, 10-15 сервисных центров, ресурс сервисного центра 32 обьекта.
Изменено: Ігор Гончаренко - 23.04.2020 11:53:19
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Цитата
Ігор Гончаренко написал:
на практике 100-200 обьектов, 10-15 сервисных центров, ресурс сервисного центра 32 объекта.
Сейчас мой алгоритм рассчитывает такие данные за секунды, с более менее нормальным результатом
 
а я все еще пишу свой (5-6 вариант) и мне инетересен соревновательный момент
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Цитата
Ігор Гончаренко написал:
а я все еще пишу свой (5-6 вариант)
Надеюсь мы увидим реализацию
 
Взял 500 случайных точек, которые находятся внутри окружности и распределил их от 3 до 10 групп, получился интересный эффект распределения по группам
https://yadi.sk/i/LwBhGqFums835A
 
Цитата
MCH написал:
Надеюсь мы увидим реализацию
обязательно, я свободное время провожу строго с этой задачей)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Какая прекрасная задача!
Ігор Гончаренко, я с ней не справлюсь, к сожалению никак.
Уже голова не та. Но с удовольствием прослежу за решением.
Задача почти как у Эрдиша. Класс
Изменено: Akropochev - 26.04.2020 00:20:35
 
Ігор Гончаренко, добрый день.
У меня к Вам пара вопросов. Первый это, что такое ТОС - территориальный орган самоуправления, или ТОС - Солнцепек? Просто для Территориального органа скорее актуальна длина пути до объекта с учетом препятствий (дорог, школ, закрытых территорий и т.д.), а для Солнцепека как раз идеально подходит как радиус поражения  ;) . И второй вопрос решение должно быть полностью в VBA или допускается часть расчетов в EXCEL. Просто задача конечно интересная, но быстро ее решить не получается. Только придумал один механизм расчета в голову лезет ещё пара идей, и чем больше идей тем больше проблем. Да я думаю, что механизм решения у всех будет практически одинаковый. Сейчас алгоритм действий разложил в EXCEL надо перетаскивать в VBA, а время нет.
Изменено: msi2102 - 29.04.2020 08:46:55
 
я не знаю что такое ТОС, если мы назовем это ЦГ (центр группы) ничего от этого в задаче не поменяется
решение может быть комбинировано с чем угодно
лишь бы на выходе БЫСТРО получить точки собранные в группы так, чтобы в группе было не более заданного количества точек а общая сумма расстояний от всех центров групп ко всем точкам обслуживаемым этим центром была как можно меньшей
Цитата
msi2102 написал:
Только придумал один механизм расчета в голову лезет ещё пара идей
а вот это мне очень знакомо. я уже месяц ношусь с этой задачей. Запал уже не тот что было в начале, но идеи как уменьшить общее количество вычислений - все еще появляются, на начальных этапах 2-3 новых подхода просто полностью зачеркивали предыдущий вариант, который больше рассчитан не на оптимальный алгоритм а полагается на вычислительную мощью компьютера.
как говорит один мой знакомый математик:
там где к вычислению результата привлекается компьютер - там заканчивается математика!
человек вместо того чтобы искать эффективное математическое решение, пишет простой (или относительно простой) код, который решает задачу не за счет точного и короткого решения, а чисто за счет быстродействия компьютера, понимаете?
возможно это байка и я сейчас причастен к ее распространению, но ее рассказывают о Гауссе (Карл Фридрих), когда класс получил задачу сосчитать сумму чисел от 1 до 100, дети стали добросовестно последовательно складывать числа и аккуратно накапливать сумму, а он подумал: если сложить 100 и 1, а потом 99 и 2,, 98 и 3 .... 50 и 51, каждая пара в сумме дает 101, таких пар 50, и тут же устно сосчитал, что сумма = 101*50 = 5050
понимаете, 1+2+3+.. +99+100 = 5050 - это компьютер, а 101*50 = 5050 - это математика! это подмечана простая закономерность и получена элементарная формула
Изменено: Ігор Гончаренко - 30.04.2020 01:08:25
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Цитата
Ігор Гончаренко написал:
это подмечана простая закономерность и получена элементарная формула
Цитата
Ігор Гончаренко написал:
там где к вычислению результата привлекается компьютер - там заканчивается математика!
Не везде можно написать простую и понятную формулу, иногда быстрее "привлечь компьютер".
Вот пример. Точного математического решения так и не было найдено.
Скрытый текст
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit,
пока могу сказать что для того, чтобы определить сколько вариантов цвета можно получить для суммы RGB меньшей 256
не обязательно вычислять 16 777 216 цветов чтобы выяснить равна ли сумма  R+G+B, данного цвета заданному числу RGB, достаточно 1 раз вычислить
(RGB^2 + 3*RGB + 2)/2
повторюсь, это строго для суммы RGB меньшей 256, например, для суммы RGB = 250 получим 31626 вариантов цвета
для RGB от 256 до 510 будет такая же формула минус поправка (пока у меня нет формулы для поправки) (RGB^2 + 3*RGB + 2)/2 - Поправка1
для RGB больше 510 тоже минус другая поправка (формулы для этой поправки тоже пока нет) (RGB^2 + 3*RGB + 2)/2- Поправка2
Изменено: Ігор Гончаренко - 30.04.2020 20:20:48
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Цитата
bedvit написал:
Вот  пример . Точного математического решения так и не было найдено
Отписался в указанно теме, задача имеет математическое решение и оно имеет математическое доказательство
Зачастую с помощью простого перебора быстрее найти решения на подобные вопросы, но задача может масштабироваться, и тогда вычислительных мощностей не хватит и нужна математика либо математическое упрощение задачи и уменьшение вычислений.
 
Ігор Гончаренко,
Добрый вечер. Маленький вопрос, больше теоретический. А расстояние между центрами может быть меньше, чем расстояние между центром и 6ю точками его окружающих?
 
расстояние между центрами групп никак не лимитировано (и не влияет на конечную сумму всех расстояний между всеми центрами и точками групп)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Реализовал алгоритм кластеризации методом k-средних (как его понял и в своей интерпретации)
Работает очень быстро, начальную точку задаю случайным образом, поэтому решения могут быть различными при каждом запуске
В методе (и в реализации) нет ограничения на количество точек в кластере, поэтому может не подойти под исходную задачу
Изменено: MCH - 13.05.2020 08:38:20
 
Цитата
MCH написал:
Реализовал алгоритм кластеризации  методом k-средних  
Оказывается, эта задача была актуальной ещё в 50-х годах.  8)
MCH, хорошее решение. Я остановился на определении начальных точек. Вначале хотел разбивать на группы по 3. Точки в группе с минимальной суммой центров заменяются на одну точку, центра группы. И в таком режиме пока не кончатся все точки и не образуется нужное количество центров. Но потом решил брать не три точки, а группу из большего количества, например, если общее количество точек в группе 15 то принять количество равное 10, в результате чего сократится количество расчетов. Остальные точки должны были присоединяться имеющимся группам. При определении групп решил учитывать угловые точки и центральную, так как они могут оказаться самыми проблемными. Следующий тормоз оказался в определении начального количества точек. При моей подборке оказалось, что самое оптимальное решение это не 10, а 9 точек при учете центральной точки и угловых. При других наборах может быть и восемь и т.д. Скорее всего нужно возвращаться к первой версии по три точки, но уже запал остыл, да и ремонт на балконе не дает этим заняться. Файл с расчетами выложу позже может, что-то кому-то пригодится. Файл получился большой и тяжёлый, но это не решение, а анализ алгоритма, постарался его сделать нагляднее (по крайней мере для меня). В нем много лишнего, но это либо остатки от предыдущих идей, либо задел для дальнейших расчетов, и ещё подтормаживает из-за пользовательских функций и условного форматирования, но у меня это не критично.
Изменено: msi2102 - 13.05.2020 10:03:47
 
Цитата
msi2102 написал:
Вначале хотел разбивать на группы по 3. Точки
я в начале стартовал с 2-х точек (по 2 ближайшие, не совпадающие с теми, что уже определены)
потом отбросил этот метод - группа может состоять и из одной точки
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Дело в том, что я не планировал заменять все точки, только с группы с наименьшим расстоянием до центра. И постепенно точки расположенные близко друг к другу будут заменяться на их центры, а точки которые могут быть отдельной группой останутся в самом конце. Я выложу файл там будет видно, как я планировал это делать.
PS можно также начинать с наименьшего расстояния между точками, после замены его на центр расстояние до остальных точек увеличится. Принимаем следующее наименьшее расстояние и постепенно будет произведена замена всех точек и они сами присоединятся к группам которые расположены близко друг к другу. Но это может затянуться на долго.
Изменено: msi2102 - 13.05.2020 12:03:25
 
Изменил файл, закралась ошибка  :(
Файл на Яндекс диске, ссылка: https://yadi.sk/d/hbsfRUZdDydvzw
Изменено: msi2102 - 13.05.2020 12:18:17
 
Немного доработал алгоритм k-средних, стартовую инициализацию центров групп делаю случайным образом по принципу k-means++
Получается относительно быстро, но каждый раз по разному, т.к. начальные точки выбираются случайным образом
Изменено: MCH - 15.05.2020 17:11:13
Страницы: Пред. 1 2
Наверх