Предыдущая тема :: Следующая тема |
Автор |
Сообщение |
vitek74
Зарегистрирован: 31.10.2007 Сообщения: 5
|
Добавлено: Ср Окт 31 2007 16:27 Заголовок сообщения: Как раскидать 1 числовой массив на 3 при условии... |
|
|
Всем откликнувшимся, ПРИВЕТ!
Помогите или направьте...
Нужно из 1-го числового массива создать 3 массива примерно равные по сумме значений.
Это необходимо для подсчета баланса мощностей в однофазной сети. Есть общая мощность которую нужно раскидать по фазам (А,В,С) так чтобы нагрузка на фазах была равномерной.
Что-то я сам не могу придумать алгоритм... (туплю наверное ) |
|
Вернуться к началу |
|
|
Bjorndalen
Зарегистрирован: 18.07.2007 Сообщения: 29
|
Добавлено: Чт Ноя 01 2007 08:27 Заголовок сообщения: |
|
|
3 новых массива должны быть равного размера? |
|
Вернуться к началу |
|
|
Alex_soldier
Зарегистрирован: 08.08.2007 Сообщения: 57 Откуда: Россия
|
Добавлено: Чт Ноя 01 2007 17:45 Заголовок сообщения: |
|
|
Поделить на 3 массива, посчитать суммы, а потом парными заменами попытаться выровнять их.
P.S. Если не изменяет память, это называется Метод Потенциалов! _________________ Мир Идей
Последний раз редактировалось: Alex_soldier (Вт Ноя 13 2007 10:16), всего редактировалось 1 раз |
|
Вернуться к началу |
|
|
b1ood
Зарегистрирован: 02.11.2007 Сообщения: 4
|
Добавлено: Пт Ноя 02 2007 02:46 Заголовок сообщения: |
|
|
Как вариант
массив 1: max_1 max_6 max_7 max_12 .....
массив 2: max_2 max_5 max_8 max_11 .....
массив 3: max_3 max_4 max_9 max_10 .....
max_1 - самое максимальное, max_2 - максимальное из оставшихся |
|
Вернуться к началу |
|
|
Kefir
Зарегистрирован: 16.04.2005 Сообщения: 443 Откуда: Пермь
|
Добавлено: Пт Ноя 02 2007 10:21 Заголовок сообщения: |
|
|
Вообще-то задача переборная. Т.е. в общем случае оптимальное решение можно найти только при помощи полного перебора. Так что, если нагрузок не много, то можно решать полным перебором. Если много, то не получится
Но, к счастью можно придумать много эвристических алгоритмов. Например, отсортировать массив по возрастанию и начиная с самых больших элементов распихивать по 3м массивам. Берется самый большой элемент из нераспределенных и помещается в тот массив, где меньше сего нагрузка.
Если же нагрузок много, качество решения должно быть высоким, а вычислительных ресурсов мало, то придется прибегнуть к генетическим алгоритмам. Хотя, это, как правило, лишнее... _________________ Самоловских Виталий aka Kefir |
|
Вернуться к началу |
|
|
vitek74
Зарегистрирован: 31.10.2007 Сообщения: 5
|
Добавлено: Пн Ноя 05 2007 14:39 Заголовок сообщения: |
|
|
Kefir писал(а): | Например, отсортировать массив по возрастанию и начиная с самых больших элементов распихивать по 3м массивам. Берется самый большой элемент из нераспределенных и помещается в тот массив, где меньше сего нагрузка.
|
Вот так и начал делать. Спасибо за помощь.
Хотя для меня понятия "эвристических" и "генетических" алгоритмов как черная дыра. Я не имею образования программиста... |
|
Вернуться к началу |
|
|
Kefir
Зарегистрирован: 16.04.2005 Сообщения: 443 Откуда: Пермь
|
Добавлено: Пн Ноя 05 2007 15:38 Заголовок сообщения: |
|
|
Эвристические алгоритмы не являются алгоритмами, приводящими к точному решению задачи. Они основаны на интуиции и опыте.
Генетические алгоритмы - это своего рода модель естественного отбора. На первом этапе получают ряд произвольных решений задачи. Из них отбираются наиболее удачные. Из них при помощи комбинирования признаков этих решений и внесения новых (мутаций) получают новые решения. Процесс повторяется много раз. _________________ Самоловских Виталий aka Kefir |
|
Вернуться к началу |
|
|
Yello
Зарегистрирован: 09.03.2006 Сообщения: 107
|
Добавлено: Вт Ноя 06 2007 15:05 Заголовок сообщения: |
|
|
Kefir, вопрос к Вам:
А сама задача случайно не является ли ЗАДАЧЕЙ ОПТИМИЗАЦИИ (раз уж Вы много знаете... )
Т.е нам ведь нужно минимизировать |s1-s2| + |s2-s3| + |s3-s1|?
(может, даже третье слагаемое можно выкинуть). |
|
Вернуться к началу |
|
|
Kefir
Зарегистрирован: 16.04.2005 Сообщения: 443 Откуда: Пермь
|
Добавлено: Вт Ноя 06 2007 15:16 Заголовок сообщения: |
|
|
Является.
Можно такой функционал:
max(s)-min(s)
предложить. _________________ Самоловских Виталий aka Kefir |
|
Вернуться к началу |
|
|
Alex_soldier
Зарегистрирован: 08.08.2007 Сообщения: 57 Откуда: Россия
|
Добавлено: Вт Ноя 13 2007 10:26 Заголовок сообщения: |
|
|
Да, самое главное: а каков размер задачи?
При некотором пороговом количестве элементов искать решение точными методами становится просто бессмысленно!
Уточню: каков порядок N = (количество элементов) _________________ Мир Идей
Последний раз редактировалось: Alex_soldier (Вт Ноя 13 2007 11:54), всего редактировалось 1 раз |
|
Вернуться к началу |
|
|
Kefir
Зарегистрирован: 16.04.2005 Сообщения: 443 Откуда: Пермь
|
Добавлено: Вт Ноя 13 2007 11:44 Заголовок сообщения: |
|
|
Очевидно m^n, гед m - число массивов, n - число нагрузок, ^ - степень числа. _________________ Самоловских Виталий aka Kefir |
|
Вернуться к началу |
|
|
|