ОБ  ОДНОМ  ПОДХОДЕ  К  РЕШЕНИЮ  ЗАДАЧИ  РАЗБИЕНИЯ  МНОЖЕСТВА

Жданова  Елена  Григорьевна

доцент  кафедры  автоматизированных  систем  обработки  информации  и  управления  Национального  технического  университета  Украины  «КПИ»,  кандидат  технических  наук,  Украина,  г.  Киев

E-mail:  

Ковальова  Дар’я  Артуровна

студент  Национального  технического  университета  Украины  «КПИ»,  Украина,  г.  Киев

E -mail:  bardgelock @yandex.ru

Артеменко  Кирилл  Валериевич

студент  Национального  технического  университета  Украины  «КПИ»,  Украина,  г.  Киев

E -mail:  kirkary @ukr.net

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

Вступление

Задача  разбиения  множества  заключается  в  разбиении  множества  на  подмножества  так,  что  бы  разница  между  подмножествами  была  минимальной.  Она  относится  к  NP-полным  задачам.  В  теории  алгоритмов  NP-полная  задача  —  задача  из  класса  NP,  к  которой  можно  свести  любую  другую  задачу  из  этого  класса  за  полиномиальное  время.  Таким  образом,  NP-полные  задачи  образуют  в  некотором  смысле  подмножество  «типовых»  задач  в  классе  NP:  если  для  какой-то  из  них  найден  «полиномиально-быстрый»  алгоритм  решения,  то  и  любая  другая  задача  из  класса  NP  может  быть  решена  так  же  «быстро»  [3]. 

Существует  ряд  задач,  которые,  так  или  иначе  связаны  с  рассматриваемой  задачей  разбиения  множества.  Рассмотрим  некоторые  из  них:

1.  Задача  о  разбиении  на  два  подмножества.  Имеется  множество  ,  состоящее  из    положительных  целочисленных  элементов  .  Необходимо  разбить  это  множество  на  два  максимально  близких  подмножества  ,  т.  е.чтобы  разница    была  минимальна  [4].

2.  Задача  сумм  подмножеств  (Subset  sum  problem).  Заключается  в  следующем:  имея  множество  целых  чисел  разного  знака  определить,  можно  ли  выделить  в  нем  непустое  подмножество,  сумма  элементов  которого  равна  нулю.  Используется  в  теории  сложности  и  криптографии  [6,  c.  105].

3.  Задача  о  ранце  [1,  с.  232].

4.  Задача  разбиения  на  k  подмножеств  (The  k-partition  problem).  Состоит  в  разбиении  множества  целочисленных  элементов  на    подмножества  с  равными  сумами  [5,  с.  97].

5.  Классическая  задача  о  камнях.  Суть  ее  в  следующем:  имеется    камней  с  разными  весами,  необходимо  разложить  их  на    групп  (куч)  таким  образом,  чтобы  вес  самой  большой  кучи  был  минимальным  [2,  с.  124].

Постановка  задачи

Имеется  множество  целочисленных  положительных  элементов  .  Весом  множества    будем  называть  величину  .  Необходимо  разбить  множество    на    подмножеств    таких,  что  и  ,  чтобы  сумма  попарных  разниц  между  весами    всех  подмножеств    стремилась  к  минимуму,  т.  е.  .

Анализ  последних  исследований  и  публикаций

Задача  разбиения  множества  относится  к  классу  NP  и  гарантировано  получить  ее  оптимальное  решение  можно  лишь  с  помощью  полного  перебора,  который  требует  экспоненциального  времени  работы.  В  связи  с  этим,  разработаны  также  такие  алгоритмы,  которые  позволяют  получить  приемлемое  решение  данной  задачи  за  полиномиальное  время  [4].  Приведем  некоторые  из  них:

1.  Псевдо-полиномиальный  алгоритм. 

2.  Аппроксимирующие  алгоритмы.

a.   Жадный  алгоритм.  Сложность  .

b.  Разностный  алгоритм  (Differencing  algorithm)  или  метод  Кармаркара  и  Карпа.  Сложность  .

c.   Эвристические  алгоритмы.

Алгоритм  для  задачи  разбиения  множества

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

·       —  входное  множество  чисел; 

·       —  количество  элементов  множества  ;

·       —  количество  подмножеств  ,  на  которое  будет  разбито  множество  ; 

·       —  вес  множества  ; 

·       —  количество  элементов  в  подмножестве  ;

·       —  идеальный  вес  каждого  из    подмножеств:  ; 

·     –  вес  подмножеств  ;

·       –  величина  отклонения  веса  подмножества  от  идеального  веса:  ,.

Схема  алгоритма

1.  Упорядочить  элементы  множества    по  возрастанию.

2.  Определить  вес  множества  :  . 

3.  Определить  идеальный  вес    для  каждого  из    подмножеств:  .

4.  Определить  предварительное  количество  элементов  в  каждом  подмножестве  :  . 

5.  Разбить  множество    на    подмножеств  ,  по    элементов  в  каждом.

6.  Произвести  проверку  на  количество  элементов  в  каждом  подмножестве.  Если  в  некотором  подмножестве  остается  один  элемент,  то  это  подмножество  исключить  из  обработки.  После  чего  пересчитать    для    количества  подмножеств.  Перейти  на  п.  7.

7.  Определить  вес  каждого  подмножества  :  .

8.  Определить  подмножество    с  максимальным  весом:    (  —  индекс  множества,  которому  соответствует  подмножество  с  максимальным  весом).

9.  Для  подмножества    определить:  .

10.                ЕСЛИ  среди  элементов  подмножества    есть  такой  элемент  ,  что:   

ТО 

Определить  подмножество    с  минимальным  весом  (  —  индекс  множества,  которому  соответствует  подмножество  с  минимальным  весом)  и  перенести  элемент    в  подмножество  .  ИНАЧЕ 

a.   Определить  минимальный  элемент    в  подмножестве  .

b.  Определить  подмножество    с  минимальным  весом  .

c.   Определить  во  множестве    такой  элемент    такой,  для  которого  разность 

d.  Поменять  элементы    и    местами.

11.                Если  в  некотором  подмножестве  остается  один  элемент,  то  это  подмножество  исключить  из  обработки.  После  чего  пересчитать    для    количества  подмножеств.  Перейти  на  п.  7.

12.                Остановить  алгоритм  при  выполнении  условия  останова.

Условия  останова  могут  быть: 

·     количество  итераций  превышает  заданное  число;

·     будет  достигнуто  «идеальное»  решение,  т.е.  веса  подмножеств    равны  эталонному  весу  ;

·     на  протяжении  заданного  количества  итераций  величина    не  изменяется.

Экспериментальное  исследование  алгоритма

Для  проведения  экспериментов  алгоритм  был  запрограммирован  на  языке  C#  и  протестирован,  для  чего  был  также  разработан  генератор  индивидуальных  задач.  Для  оценки  эффективности  алгоритма  генерировались  такие  индивидуальные  задачи,  для  которых  известно  оптимальное  решение.  Эксперименты  проводились  для  классической  задачи  разбиения  множества.  На  рисунке  1  изображен  график  зависимости  количества  итераций,  пройденных  алгоритмом,  в  зависимости  от  мощности  входного  множества. 

Рисунок  1.  График  зависимости  количества  итераций  от  мощности  входного  множества

Проанализировав  график,  можно  сделать  вывод,  что  данная  зависимость  является  линейной.

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

Рисунок  2.  Гистограмма  зависимости  количества  найденных  оптимальных  решений  в  зависимости  от  мощности  входного  множества

Выводы

К  достоинствам  алгоритма  можно  отнести  следующее:  алгоритм  полный;  он  быстро  обрабатывает  большие  объемы  данных  (так  задача  о  разбиении  множества  из  10  000  элементов  на  2  подмножества  решается  в  пределах  16  секунд  на  процессоре  Intel  core  i5  2410M  (2,3  ГГц));  имеет  высокий  процент  (  получения  оптимального  решения.

К  недостаткам  алгоритма  относятся:  он  не  оптимальный;  его  эффективность  зависит  от  условия  останова  и  диапазона  значений  элементов  множества.

Список  литературы:

1.Бурков  В.Н.,  Горгидзе  И.А.,  Ловецкий  С.Е..  Прикладные  задачи  теории  графов.  М.,  1974.  —  232  с.

2.Бурков  В.Н.,  С.И.  Дзюбко,  А.А.  Ягупов  Эффективный  алгоритм  решения  одного  частного  случая  обобщенной  задачи  о  камнях,  Автомат.  и  телемех,  —  №  7  —  1995.  —124—130  с.

3.Статья  NP-полная  задача  //  Википедия.  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  http://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0   (дата  обращения:  20.04.2014).

4.Hayes  B.  The  Easiest  Hard  Problem  //  American  Scientist,  2002.  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  https://www.americanscientist.org/issues/pub/the-easiest-hard-problem   (дата  обращения:  25.04.2014).

5.Michael  R.  Garey,  David  S.  Johnson  Computers  and  Intractability:  A  Guide  to  the  Theory  of  NP-Completeness,  —  1979.  —  №  96—105,  —  224  с.

6.Silvano  M.,  Paolo  T.  Knapsack  problems:  Algorithms  and  computer  interpretations.  Wiley-Interscience,  1990.  —105—136  с.