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

Страницы: 1 2 3 4 5 6 7 8 9 10 11 ... 121 След.
Найти комбинацию в матрице
 
Grantorino, можете обозначить исходную задачу (вариантов транспортных задач достаточно много)
Может быть найдется альтернативное решение, в т. ч. через "Поиск решения" или другим способом
Опишите исходную задачу, с указанием реальных данных
График изготовления деталей по сменам
 
Как то так
Заменить буквы числовыми значениями и получить сумму
 
Цитата
Степкина написал:
А как получить промежуточный числовой код слова из которого мы получаем сумму?
Зачем нужно промежуточное число, если потом все равно сумму считаем?
=СУММПРОИЗВ(10^(ДЛСТР(B1)-СТРОКА(ДВССЫЛ("1:"&ДЛСТР(B1))))*(ОСТАТ(ПОИСК(ПСТР(B1;СТРОКА(ДВССЫЛ("1:"&ДЛСТР(B1)));1);"абвгдеёжзийклмнопрстуфхцчшщъыьэюя")-1;9)+1))

Цитата
Hugo написал:
А зачем это всё?
Скорее всего нумерология, ссылку на формулы buchlotnik уже давал
Изменено: MCH - 18 Май 2020 14:00:35
Заменить буквы числовыми значениями и получить сумму
 
=СУММПРОИЗВ(ОСТАТ(ПОИСК(ПСТР(B1;СТРОКА(ДВССЫЛ("1:"&ДЛСТР(B1)));1);"абвгдеёжзийклмнопрстуфхцчшщъыьэюя")-1;9)+1)
Изменено: MCH - 18 Май 2020 13:34:58
Подбор количества под нужную сумму
 
Количество вариантов набора суммы может быть большим (приложил пример из нескольких вариантов), какой из них выбирать?
А может и не получится разбить указанную сумму на целочисленное количество с точностью до копеек
Для нахождения разбиения использовал надстройку "Поиск решения"
Но можно сделать все и на макросах
Изменено: MCH - 18 Май 2020 13:10:17
оптимальное размещение центров групп
 
Немного доработал алгоритм k-средних, стартовую инициализацию центров групп делаю случайным образом по принципу k-means++
Получается относительно быстро, но каждый раз по разному, т.к. начальные точки выбираются случайным образом
Изменено: MCH - 15 Май 2020 17:11:13
оптимальное размещение центров групп
 
Реализовал алгоритм кластеризации методом k-средних (как его понял и в своей интерпретации)
Работает очень быстро, начальную точку задаю случайным образом, поэтому решения могут быть различными при каждом запуске
В методе (и в реализации) нет ограничения на количество точек в кластере, поэтому может не подойти под исходную задачу
Изменено: MCH - 13 Май 2020 08:38:20
Количество цветов в произвольном диапазоне R+G+B
 
Цитата
bedvit написал:
382,5 - магическое число?
255 * 3 / 2 = 765 / 2 = 382,5
График симметричен, поэтому правую его часть рассчитываем также как и левую, для этого и считаем 382,5-ABS(A2-382,5)
Чтобы значения 0 и 765 (1 и 764 и т.д.) рассчитывались одинаково, возможно есть более простое решение
оптимальное размещение центров групп
 
Цитата
bedvit написал:
Вот  пример . Точного математического решения так и не было найдено
Отписался в указанно теме, задача имеет математическое решение и оно имеет математическое доказательство
Зачастую с помощью простого перебора быстрее найти решения на подобные вопросы, но задача может масштабироваться, и тогда вычислительных мощностей не хватит и нужна математика либо математическое упрощение задачи и уменьшение вычислений.
Количество цветов в произвольном диапазоне R+G+B
 
Чуть короче:
Код
=ЧИСЛКОМБ(382,5-ABS(A2-382,5)+2;2)-ЕСЛИОШИБКА(ЧИСЛКОМБ(382,5-ABS(A2-382,5)-254;2)*3;)

или так, формула массива:
Код
=СУММ(ЕСЛИОШИБКА(ЧИСЛКОМБ(382,5-ABS(A2-382,5)+{2;-254};2);)*{1;-3})


PS: жаль что вопрос мимо "Избушки" прошел, можно было бы посоревноваться
Изменено: MCH - 1 Май 2020 12:07:43
Количество цветов в произвольном диапазоне R+G+B
 
Может такое решение подойдет?
оптимальное размещение центров групп
 
Взял 500 случайных точек, которые находятся внутри окружности и распределил их от 3 до 10 групп, получился интересный эффект распределения по группам
https://yadi.sk/i/LwBhGqFums835A
оптимальное размещение центров групп
 
Цитата
Ігор Гончаренко написал:
а я все еще пишу свой (5-6 вариант)
Надеюсь мы увидим реализацию
оптимальное размещение центров групп
 
Цитата
Ігор Гончаренко написал:
на практике 100-200 обьектов, 10-15 сервисных центров, ресурс сервисного центра 32 объекта.
Сейчас мой алгоритм рассчитывает такие данные за секунды, с более менее нормальным результатом
оптимальное размещение центров групп
 
Игорь, хотелось бы узнать, какова конечная задача, в которой необходимо группировать точки?
оптимальное размещение центров групп
 
Реализовал расчет в FreeBasic, версия на 64-бит считает быстрее, чем 32-бит
при этом параллельно решается несколько вариантов и выбирается лучшее решение

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

PS: Запустил алгоритм на 1000 случайных точках, 50 групп с не более чем 50 точек в группе, считалось минут 20
Так это на VBA, если перенести алгоритм на Freebasic да еще разбить его на потоки, можно 1000 точек за пару минут расчитать
Изменено: MCH - 21 Апр 2020 21:47:49
оптимальное размещение центров групп
 
Игорь, мое решение (например из 25 поста) подошло или нужно еще что то придумывать?

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

По скорости моего алгоритма, на 100-200 точек он работает относительно быстро, на 1000 точек не проверял, но думаю, что можно немного ускорить алгоритм, за счет другого хранения данных в группах (правда это потребует существенно изменения кода).
Либо можно алгоритм переписать на другой более быстрый ЯП (С++ или Freebasic), на Freebasic немного придется переделывать, при этом можно разбить алгоритм на потоки, что ускорит вычисления в разы
Изменено: MCH - 20 Апр 2020 13:50:53
оптимальное размещение центров групп
 
Цитата
MCH написал:
Странная какая-то аксиома.
Может в таком случае сравнивать сумму квадратов расстояний (как раз добьемся минимизации суммарного квадратичного отклонения), при этом более удаленные точки имеют существенно худший результат
Выкладываю код с этим подходом, в ситуации 22/4, 22/5, 22/6 алгоритм решает более менее оптимально

UPD: Сделал пример на 200 точек и 6 групп, вроде получается нормально
Уверен что есть более оптимальное решение, но даже текущее может быть  использовано на практике
Изменено: MCH - 18 Апр 2020 11:46:55
оптимальное размещение центров групп
 
В коде из 21 сообщения нашел у себя небольшую ошибку, исправил ее, также внес правки в код, считать стало быстрее: 100 точек - пару секунд
оптимальное размещение центров групп
 
Сделал пример для 100 точек на 6 групп
Визуально вроде приемлемо, но все таки не оптимально, результат может меняться в зависимости от того, какую начальную точку мы выбираем
И считает уже заметно дольше
Изменено: MCH - 18 Апр 2020 10:35:33
оптимальное размещение центров групп
 
Получилось набросать макрос (см. вложение)
для 6ти групп нашлось решение лучше, чем указано в 17 сообщении, а вот для 5ти групп решение хуже

PS: На большом количестве точек не проверял, возможно будет долго считать и не совсем оптимально
Изменено: MCH - 18 Апр 2020 02:17:04
оптимальное размещение центров групп
 
Цитата
Ігор Гончаренко написал:
при указанных координатах и 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

Все решено не спортивно (через "Поиск Решения")
Попробую подумать над алгоритмом, который описал выше
оптимальное размещение центров групп
 
Задача очень интересная, когда решал задачу коммивояжера, хотел использовать подобную группировку точек для упрощения расчетов
Для исходных данных у меня получилось найти распределение по группам с суммарной длинной - 402,057599436519
Решал через Поиск Решения, поэтому метод не подходит как универсальный.

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

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

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

Также можно подумать в сторону генетических алгоритмов или алгоритмов муравьиных колоний
Поиск решения на 34к строк
 
DonPеdro3x, опишите задачу, что нужно реализовать?
На вскидку очень похоже на нахождение кратчайшего пути в графе, решающийся алгоритмом Дейкстры
http://www.excelworld.ru/forum/3-6656-1
Из всех вариантов, которые располагаться в столбцах, сгенерировало полную комбинацию от 1-10
 
Цитата
БМВ написал:
Что-то MCH не спешит
Цитата
Андрей VG написал:
Странно, что  MCH  так и не развил тему.
Не было времени вникнуть в задачу, сразу не понял ее смысл, сейчас посмотрел решения, стало понятно что нужно.
Задача мне напомнило тему: https://www.planetaexcel.ru/forum/index.php?PAGE_NAME=message&FID=1&TID=58223
Но там искалось только одно решение и для большого кол-ва вариантов сочетания чисел
Из всех вариантов, которые располагаться в столбцах, сгенерировало полную комбинацию от 1-10
 
Скорее всего нужны сочетания из 10 по 4
http://www.excelworld.ru/forum/3-36449-1
https://excel2.ru/articles/sochetaniya-bez-povtoreniy-kombinatorika-v-ms-excel
Подбор арифметических действий с использованием различных знаков.
 
Решал схожую задачу (или схожими методами) здесь:
http://www.excelworld.ru/forum/7-1962-1

Поэтому и возник вопрос, для чего это все нужно?
Подбор арифметических действий с использованием различных знаков.
 
Цитата
wholesander написал:
хочу реализовать возможность использования подбора  арифметических действий как выше указанном примере, но используя разные знаки во всех их возможных комбинациях
wholesander, опишите задачу подробнее, что нужно сделать?
Страницы: 1 2 3 4 5 6 7 8 9 10 11 ... 121 След.
Наверх