Поиск  Пользователи  Правила 
Закрыть
Логин:
Пароль:
Забыли свой пароль?
Регистрация
Войти
 
Выбрать дату в календареВыбрать дату в календаре

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

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

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

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

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

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

ПЫСЫ:
возможно, у Вас еще нет готового решения, но есть интерес к теме, пожалуйста, обозначьте  его ответом: типа я угадаю это решение с 3-х байт  или за 2-3  недели
всем,кто дочитал до этой строки -  спасибо!
отдельное спасибо тем, кто открыл файл)
Изменено: Ігор Гончаренко - 15 Апр 2020 21:21:25
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
сумма значений разделенных пробелами
 
В ячейке есть некоторое количество (2 или более) целых чисел разделенных пробелами
можно в соседней ячейке формулой получить сумму этих чисел?
Изменено: Игорь Гончаренко - 21 Июл 2016 18:03:08
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
Страницы: 1
Наверх