Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
В кратце, алгоритм следующий: Шаг 1 : сортируем числа по убыванию и распределяем их по множествам "зейкой". То есть для набора чисел 5 2 6 7 5 4 3 3 8 6 3 и четырёх множеств это будет следующим образом: Сортировка: 8 7 6 6 5 5 4 3 3 3 2 Распеределение: (8 3 3) = 14 (7 4 3) = 14 (6 5 2) = 13 (6 5 ) = 11 Шаг 2 : переносим минимальный элемент из одного множества в другое при условии что разница их сумм больше чем переносимый элемент. Этот шаг повторяем до тех пор, пока приведённое выше условие выполняется. Таким образом при распределении чисел "змейкой" на перовом шаге, этот шаг для данного набора чисел игнорируется. Для других наборов, в которых числа различаются на большие величины, этот шаг выполняется. Шаг 3 : выбираются два множества - с максимальной и минимальной суммой элементов. Выполняем проверку что разность их сумм больше 1 (исходим из того, что работаем с целыми числами). Если это условие не выполняется, то нашли оптимальное решение, в противном случае находим разность между элементами множества (каждый элемент с каждым). Полученные разности упорядочеваем по возрастанию и находим попадающие в интервал [1, CEILING((S1 - S2)/2)] (где S1 и S2 - суммы множеств, CEILING - округление в большую сторону). Из значений, удовлетворяющих этому неравенству выбираем максимальное. Пару элементов множества, удовлетворяющих приведённому условию, меняем местами. Этот шаг повторяем до тех пор, пока можем поменять элементы местами. Таким образом: итерация 1: (8 3 3) = 14 (6 5 ) = 11 S1 - S2 = 3 Пары элементов: (8 - 6 = 2) (3 - 6 = -3) (3 - 6 = -3) (8 - 5 = 3) (3 - 5 = -2) ( 3 - 5 = -2) 1 <= Xij <= CEILING(1.5) = 2 меняем местами элементы 8 и 6. Получаем: (6 3 3) = 12 (7 4 3) = 14 (6 5 2) = 13 (8 5 ) = 13 итерация 2: рассуждая аналогично меняем местами элементы первого и второго множества. Тут, однако, возможны варианты. Можно поменять местами 6 и 7, либо 3 и 4. Однако, это не имеет значение что мы будем менять местами. Если мы менем местами 7 и 6, то получаем: (7 3 3) = 13 (6 4 3) = 13 (6 5 2) = 13 (8 5 ) = 13 - искомый результат. Если мы меняем местами 3 и 4 то получаем: (6 4 3) = 13 (7 3 3) = 13 (6 5 2) = 13 (8 5 ) = 13 - искомы результат. Вот. В принципе, основную роль в алгоритме играет шаг 3. Используя только его можно получить ответ, однако шаг 1 и шаг 2 значительно сокращают количество итераций на шаге 3. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2005, 17:54 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
О! Спасибо большое за алгоритм. Так я хоть понял. Он по идее правльный Однако мне что то заело (чисто с теор. точки зрения). Часов с 6-ти голову ламаю. Вот как-то мне он не неравится Как минимум нету доказательства, что он правильный. Особенно действия описаные в Шаге 3. Который по сути главный. Вопрос к теоретикам (Они же тоже должы читать этот форум:) ): что скажете? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2005, 01:06 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Насколько помню такие алгоритмы называются обменно-итерационными. Известно, что в задаче разрезания графа (разбить множество вершин графа на 2 подмножества так, что бы сумма связей между подмножествами была минимальной) обменно-итерационный алгоритм дает лишь локально оптимальное решение. Хотя задача разрезания графа кажется более сложной, чем рассматриваемая за счет наличия связей между элементами, скорее всего аналогичная картина будет и здесь: варьируя начальное разбиение будем получать различные локальные минимумы, из который выберем наилучший. Что это будет глобальный минимум - не факт. Повторюсь еще раз, что это только мое предположение, но доказательство того, что обменно-итерационный алгоритм в этой задаче всегда сходится к глобальному минимуму действительно необходимо. В теории локального поиска есть предположение (однако такие вещи опасно обобщать), что "хорошие" алгоритмы слабо зависят от качества начального приближения и всегда находят локальные оптимумы определенной "силы". С этой точки зрения интересно посмотреть, дают ли шаги 1 и 2 преимущество по сравнению со случайным выбором начального разбиения. Если требуется найти точное решение, я бы поступил так. Ясно, что оптимум надо искать вблизи равномерных разбиений. В рассматриваемом примере общая сумма 52, идеальный случай 4 подмножества по 13. Находим все комбинации элементов, дающие в сумме 13 (это как раз одна из разновидностей задачи о рюкзаке). Далее смотрим существуют ли среди полученных комбинаций 4 таких, что: 1.Каждый элемент в них встречается ровно 1 раз. 2.Не существует элемента, который не встретился ни разу. В данном примере такое разбиение существует, но в общем случае его может и не быть. Тогда отступаем на шаг - 13,13,14,12 и повторяем процесс. Сколько итераций придется сделать в общем случае неясно, однако есть предположение, что конечное число :^) Способ хотя и не самый быстрый, но теоретически обоснованный: "правильность" конечного результата следует из "правильности" алгоритма решения задачи о рюкзаке, которую мы решаем на каждом шаге и которая известна. Кроме того, имея все комбинации элементов, дающие в сумме 13, можно искать не обязательно 4 подмножества , а также 3, 5 и т.д. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2005, 12:11 |
|
||
|
|

start [/forum/topic.php?fid=16&gotonew=1&tid=1347815]: |
0ms |
get settings: |
10ms |
get forum list: |
11ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
128ms |
get topic data: |
8ms |
get first new msg: |
5ms |
get forum data: |
2ms |
get page messages: |
35ms |
get tp. blocked users: |
1ms |
| others: | 243ms |
| total: | 447ms |

| 0 / 0 |
