Преглед на алгоритми за решаване на проблема за намиране на сумата от елементи на подмножество е темата на научна статия за

Тази статия предоставя преглед на алгоритмите за решаване на проблема за намиране на сумата от елементите на подмножество. Разглеждат се алгоритми с експоненциална сложност, приблизителни алгоритми с полиномно време за изпълнение. Целта на работата е да подреди наличната информация според различни, но близки формулировки на проблема за намиране на сумата от елементи на подмножества. Всички алгоритми имат подробно описание, илюстрирано с примери.

ПРЕГЛЕД НА АЛГОРИТМИТЕ ЗА РЕШАВАНЕ НА ПРОБЛЕМА ЗА НАМЕРВАНЕ НА СУМАТА НА ПОДПОДГОТОВКА НА ЕЛЕМЕНТИТЕ

Тази статия предоставя преглед на алгоритмите за решаване на проблема за намиране на сумата на подмножество елементи. Обсъдени са алгоритми с експоненциална сложност, алгоритми за сближаване с време на изпълнение на полиноми. Поръчваме информация за различни подходи към проблема за намиране на сумата от елементи на подмножества. Всички алгоритми имат подробни описания и са илюстрирани с примери.

Текст на научната работа по темата „Преглед на алгоритми за решаване на задачата за намиране на сумата от елементи на подмножество“

Селиванова И.А., Зикина М.В.

ПРЕГЛЕД НА АЛГОРИТМИТЕ ЗА РЕШЯВАНЕ НА ПРОБЛЕМА ЗА НАМЕРВАНЕ НА СУМАТА НА ЕЛЕМЕНТИ НА ПОДПОДМОЩ

Анотация. Тази статия предоставя преглед на алгоритмите за решаване на проблема за намиране на сумата от елементи на подмножество. Разглеждат се алгоритми с експоненциална сложност, приблизителни алгоритми с полиномно време за изпълнение. Целта на тази работа е да подреди наличната информация според различни, но близки формулировки на проблема за намиране на сумата от елементи на подмножества. Всички алгоритми имат подробно описание, илюстрирано с примери.

Ключови думи: сума, множество, подмножество, алгоритъм.

Selivanova I.A., Zykina M. V.

ПРЕГЛЕД НА АЛГОРИТМИТЕ ЗА РЕШАВАНЕ НА ПРОБЛЕМА ЗА НАМЕРВАНЕ НА СУМАТА НА ПОДПОДГОТОВКА НА ЕЛЕМЕНТИТЕ

Анотация. Тази статия предоставя преглед на алгоритмите за решаване на проблема за намиране на сумата на подмножество елементи. Обсъждат се алгоритми с експоненциална сложност, алгоритми за сближаване с време на изпълнение на полиноми. Ние подреждаме информация за различни подходи към проблема за намиране на сумата от елементи на подмножества. Всички алгоритми имат подробни описания и са илюстрирани с примери.

Ключови думи: сума, набор, подмножество, алгоритъм.

Задачата за сумата е формулирана по следния начин: намерете подмножество на Γ, така че техните числа от дадена крайна колекция X, които се събират до дадено число 5. Класически, проблемът е формулиран по отношение на цели числа [4].

Еквивалентни задачи са задачи, при които числото z е равно на 0, или например половината от сумата на всички елементи от множеството [5, с. 3]. Понякога се изисква да се намери подмножество K с X, чиято сума от елементите приема максимално възможната стойност, която не надвишава

Задачата за сумата принадлежи към NP-пълните задачи. В теорията на алгоритмите проблемите от клас P са изчислителни задачи, които могат да бъдат решени за полиномиално време. Алгоритмите, чиято сложност не е ограничена от полином по дължината на входа, се наричат експоненциални. IR класът е набор от задачи, за които може да бъде проверка на коректността на резултата-

е завършен за полиномиално време. В теорията за NP-пълнотата се разглеждат само проблеми с разрешаването - проблеми, при които се изисква да се даде отговор „да“ или „не“ на някакъв въпрос. Например проблемът за намиране на сумата от елементите на подмножината Y е свързан с проблема за разделителната способност: може ли числото 5 да бъде представено като сбор от всякакви елементи на масива X. Ако някой алгоритъм даде резултат - масив V, след това проверката на правилността на този резултат може да се извърши с полиномиална сложност: проверката на X = ^ изисква най-много O (n) операции. KP-пълен проблем е проблем от IR класа, до който всеки друг проблем от този клас може да бъде сведен за полиномиално време [6].

Изчислителната сложност на задачата върху сумата от подмножества зависи от два параметъра: n и p, където n е броят на елементите от множеството, p е броят на двоичните цифри в числата, които съставят множеството Ако n-

малък, след това за решаване на проблема със сумата от елементи на подмножества се използват методи за изброяване; ако p е относително малък, тогава се използват методи за динамично програмиране [5, p. 3].

При практическото решение на задачата за сумата на подмножество се изисква не само да се посочи дали този проблем има решение, но и да се определят елементите на намереното подмножество. Решението на тази подпроблема е свързано с представянето на данни при изпълнението на алгоритъма.

Помислете за някои алгоритми за решаване на задачата във време, което експоненциално зависи от n.

Алгоритми на експоненциална сложност

Първоначални данни: много различни положителни числа X = и

Най-простият алгоритъм е да се генерират всички подмножества от множеството X. Броят на всички подмножества от множеството и елементи, като се вземе предвид празното подмножество, е равен на 2 "За всеки от тези подмножества се изчислява сумата на елементите и се проверява дали е равна на желаната сума 5. Проблемът за генериране на всички подмножества от множеството е еквивалентен на проблема за генериране на всички n-мерни вектори от нули и единици Ако има 1 (един) на i-тия позиция на вектора, това означава, че елементът е включен в това подмножество и трябва да се вземе предвид при изчисляване на сумата от елементите на подмножеството.Така, всяко подмножество съответства на двоично число или структура, която симулира двоично число Определяне номерата на позициите, на които стоят тези, ви позволява уникално да маркирате елементите на X и да изчислите тяхната сума.