Вероятностные алгоритмы для задачи о разбиении при случайных данных
|
Введение 3
1. Постановка задачи 5
2. Описание задачи о разбиении и алгоритмы её решения 6
2.1 Алгоритм динамического программирования 6
2.2 Алгоритм 8 единиц и его обобщение 10
2.3 Алгоритм разбиения с помощью прохода по всему массиву весов 12
2.4 Алгоритм n-1 единиц с использованием алгоритма Евклида 13
2.5 Алгоритм разбиения с использованием расширенного алгоритма
Евклида 15
3. Результаты 17
3.1 Результаты 17
3.2 Результаты 25
4. Исключения 27
4.1 Особенности работы алгоритма для степенного закона 27
4.2 Особенности работы алгоритма разбиения с использованием
расширенного алгоритма Евклида 29
Заключение 30
Список используемых источников 32
Приложение 1 33
Приложение 2 36
1. Постановка задачи 5
2. Описание задачи о разбиении и алгоритмы её решения 6
2.1 Алгоритм динамического программирования 6
2.2 Алгоритм 8 единиц и его обобщение 10
2.3 Алгоритм разбиения с помощью прохода по всему массиву весов 12
2.4 Алгоритм n-1 единиц с использованием алгоритма Евклида 13
2.5 Алгоритм разбиения с использованием расширенного алгоритма
Евклида 15
3. Результаты 17
3.1 Результаты 17
3.2 Результаты 25
4. Исключения 27
4.1 Особенности работы алгоритма для степенного закона 27
4.2 Особенности работы алгоритма разбиения с использованием
расширенного алгоритма Евклида 29
Заключение 30
Список используемых источников 32
Приложение 1 33
Приложение 2 36
Задача о разбиении относится к классу трудно решаемых задач (NP-полных). Дадим определение NP - полным задачам. Класс NP - это переборные задачи. NP-полные задачи - обладают универсальностью: любую задачу из класса NP можно полиномиально свести к любой из NP-полных задач, то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных. Таким образом, NP- полные задачи образуют подмножество типовых задач в классе NP: если для какой-то из них найден полиномиально быстрый алгоритм решения, то и любая другая задача из класса NP может быть решена так же быстро.
Переборная задача - это задача, в которой нужно отыскать объект, который удовлетворяет группе условий. Проблема перебора звучит следующим образом: совпадают ли классы P и NP? Определим класс P: класс Р - вычислительные задачи, которые легко решить (быстро решаемые задачи, то есть разрешимые за полиномиальное время). Если P = NP, то тогда можно будет сделать вывод, что все переборные задачи (задачи из класса NP) могут быть быстро решены. Но если все переборные задачи могут быть быстро решены, то разрушится современная технология криптографии, позволяющая наладить безопасный обмен данными между двумя объектами (например, передача данных от клиента к банку). Тема моей дипломной работы актуальна, так как задача о разбиении при случайных данных является задачей перебора.
Задача разбиения множества заключается в разбиении множества на подмножества так, чтобы сумма одного подмножества равнялась сумме другого подмножества. Существует решение задачи о разбиении методом динамического программирования, а так же существуют эвристические алгоритмы решения, что и будет продемонстрировано в этой работе.
Гарантированно получить результат задачи о разбиении можно лишь с помощью полного перебора, который требует экспоненциального времени работы. Но вышеперечисленные алгоритмы дадут приемлемое решение за полиномиальное время.
Множество для задачи о разбиении может состоять из непрерывных значений различных законов распределения случайных величин, а так же мы рассмотрим случаи дискретного распределения, то есть когда задан определенный целочисленный массив. В этой работе показана зависимость времени работы алгоритмов от количества элементов в первоначальном множестве для равномерного распределения на [0, 9], показательного и степенного законов, а также рассмотрим случай с римскими цифрами, кратными пяти (с использованием расширенного алгоритма Евклида), после чего проведём сравнение эффективности алгоритмов и рассмотрим особенности некоторых из них.
Целью работы является доказательство того, что время работы вышеперечисленных алгоритмов не превышает полиномиального, а так же показать, что случайно взятый набор чисел тоже может быть разбит на две группы с равными суммами при условии, что сумма изначального ряда чётна.
Переборная задача - это задача, в которой нужно отыскать объект, который удовлетворяет группе условий. Проблема перебора звучит следующим образом: совпадают ли классы P и NP? Определим класс P: класс Р - вычислительные задачи, которые легко решить (быстро решаемые задачи, то есть разрешимые за полиномиальное время). Если P = NP, то тогда можно будет сделать вывод, что все переборные задачи (задачи из класса NP) могут быть быстро решены. Но если все переборные задачи могут быть быстро решены, то разрушится современная технология криптографии, позволяющая наладить безопасный обмен данными между двумя объектами (например, передача данных от клиента к банку). Тема моей дипломной работы актуальна, так как задача о разбиении при случайных данных является задачей перебора.
Задача разбиения множества заключается в разбиении множества на подмножества так, чтобы сумма одного подмножества равнялась сумме другого подмножества. Существует решение задачи о разбиении методом динамического программирования, а так же существуют эвристические алгоритмы решения, что и будет продемонстрировано в этой работе.
Гарантированно получить результат задачи о разбиении можно лишь с помощью полного перебора, который требует экспоненциального времени работы. Но вышеперечисленные алгоритмы дадут приемлемое решение за полиномиальное время.
Множество для задачи о разбиении может состоять из непрерывных значений различных законов распределения случайных величин, а так же мы рассмотрим случаи дискретного распределения, то есть когда задан определенный целочисленный массив. В этой работе показана зависимость времени работы алгоритмов от количества элементов в первоначальном множестве для равномерного распределения на [0, 9], показательного и степенного законов, а также рассмотрим случай с римскими цифрами, кратными пяти (с использованием расширенного алгоритма Евклида), после чего проведём сравнение эффективности алгоритмов и рассмотрим особенности некоторых из них.
Целью работы является доказательство того, что время работы вышеперечисленных алгоритмов не превышает полиномиального, а так же показать, что случайно взятый набор чисел тоже может быть разбит на две группы с равными суммами при условии, что сумма изначального ряда чётна.
В данной дипломной работе было реализовано несколько алгоритмов для задачи о разбиении при случайных данных, относящейся к классу трудно решаемых задач. Подведем итоги и сделаем выводы по каждому алгоритму в отдельности:
1) Время работы алгоритма динамического программироания квадратично зависит от размерности в тех случаях, которые были рассмотрены в этой работе, а именно, когда данные для задачи о разбиении сгенерированы с помощью закона распределения, принимающего значения на конечном множестве или же с помощью показательного и степенного законов.
2) Время работы алгоритма 8 единиц и алгоритма разбиения с помощью прохода по всему массиву весов зависит практически линейно от размерности задачи (в случаях, описанных в предыдущем абзаце).
3) Алгоритм 8 единиц при достаточно больших размерностях(>150) всегда применим и находит разбиение, если сумма весов чётна.
4) Для показательного закона порождения весов алгоритм разбиения с помощью прохода по всему массиву весов всегда применим при достаточно большой размерности и выдаёт разбиение при чётной сумме весов.
5) Для степенного закона распределения весов с параметром а 6 (2, 2.3) при любой размерности существуют примеры сгенерированных весов, не позволяющие разбить множество на две части, не смотря на чётность суммы весов.
6) Для степенного закона распределения весов при показателе этого закона а > 2.3 при размерностях > 100 и чётной сумме решение задачи о разбиении всегда существует.
7) Во всех ситуациях, описанных в пунктах 4-6, когда решение существует, оно может быть найдено с помощью алгоритма разбиения с помощью прохода по всему массиву весов.
8) Разбиение на две группы с равными суммами произвольного дискретного распределения возможно в случае, когда сумма первоначального ряда чётна и учтены условия раздела 4.2 об особенностях работы алгоритма разбиения с использованием расширенного алгоритма Евклида.
Общие выводы:
Все приведенные результаты работы алгоритмов давали нам приемлемое время работы: было затрачено такое количество операций, что не превышает некоторого полинома в зависимости от исходных данных.
А так же было показано, что случайно взятый набор чисел тоже может быть разбит на две группы с равными суммами при условии, что сумма изначального ряда чётна.
1) Время работы алгоритма динамического программироания квадратично зависит от размерности в тех случаях, которые были рассмотрены в этой работе, а именно, когда данные для задачи о разбиении сгенерированы с помощью закона распределения, принимающего значения на конечном множестве или же с помощью показательного и степенного законов.
2) Время работы алгоритма 8 единиц и алгоритма разбиения с помощью прохода по всему массиву весов зависит практически линейно от размерности задачи (в случаях, описанных в предыдущем абзаце).
3) Алгоритм 8 единиц при достаточно больших размерностях(>150) всегда применим и находит разбиение, если сумма весов чётна.
4) Для показательного закона порождения весов алгоритм разбиения с помощью прохода по всему массиву весов всегда применим при достаточно большой размерности и выдаёт разбиение при чётной сумме весов.
5) Для степенного закона распределения весов с параметром а 6 (2, 2.3) при любой размерности существуют примеры сгенерированных весов, не позволяющие разбить множество на две части, не смотря на чётность суммы весов.
6) Для степенного закона распределения весов при показателе этого закона а > 2.3 при размерностях > 100 и чётной сумме решение задачи о разбиении всегда существует.
7) Во всех ситуациях, описанных в пунктах 4-6, когда решение существует, оно может быть найдено с помощью алгоритма разбиения с помощью прохода по всему массиву весов.
8) Разбиение на две группы с равными суммами произвольного дискретного распределения возможно в случае, когда сумма первоначального ряда чётна и учтены условия раздела 4.2 об особенностях работы алгоритма разбиения с использованием расширенного алгоритма Евклида.
Общие выводы:
Все приведенные результаты работы алгоритмов давали нам приемлемое время работы: было затрачено такое количество операций, что не превышает некоторого полинома в зависимости от исходных данных.
А так же было показано, что случайно взятый набор чисел тоже может быть разбит на две группы с равными суммами при условии, что сумма изначального ряда чётна.
Подобные работы
- Эффективные алгоритмы с гарантированными оценками
точности для некоторых обобщений задачи коммивояжера
Диссертация , математика. Язык работы: Русский. Цена: 5720 р. Год сдачи: 2017 - Специальные задачи линейного и нелинейного программирования
Дипломные работы, ВКР, прочее. Язык работы: Русский. Цена: 4970 р. Год сдачи: 2016 - ИСПОЛЬЗОВАНИЕ ГИС-ТЕХНОЛОГИЙ И ДАННЫХ
ДИСТАНЦИОННОГО ЗОНДИРОВАНИЯ ЗЕМЛИ ДЛЯ ИЗУЧЕНИЯ
ОВРАЖНОЙ ЭРОЗИИ НА ПРИМЕРЕ ВЕРХНЕУСЛОНСКОГО
МУНИЦИПАЛЬНОГО РАЙОНА РЕСПУБЛИКИ ТАТАРСТАН
Дипломные работы, ВКР, картография. Язык работы: Русский. Цена: 4900 р. Год сдачи: 2019 - СУБПОЛОСНАЯ ИДЕНТИФИКАЦИЯ ДИКТОРОВ
Магистерская диссертация, информационные системы. Язык работы: Русский. Цена: 4830 р. Год сдачи: 2017 - АВТОМАТИЧЕСКОЕ ПОПОЛНЕНИЕ ПРЕДМЕТНО-ОРИЕНТИРОВАННЫХ ТОНАЛЬНЫХ СЛОВАРЕЙ (НА МАТЕРИАЛЕ ОТЗЫВОВ О БАНКОВСКИХ ОРГАНИЗАЦИЯХ)
Магистерская диссертация, лингвистика. Язык работы: Русский. Цена: 5500 р. Год сдачи: 2017