Приближеный алгоритм

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
Maria_Z
Сообщения: 2
Зарегистрирован: 28 май 2015, 08:21

Приближеный алгоритм

Сообщение Maria_Z » 28 май 2015, 08:24

Есть задача о сумме подмножества и есть приближенный алгоритм ее решения:

Создаем список S, первоначально состоящий из одного элемента 0.
Для всех i от 1 до n выполним следующие действия
Создаем список T, состоящий из xi + y для всех y из S
Создаем список U, равный объединению T и S
Сортируем U
Опустошаем S
Пусть y – наименьший элемент U
Внесем y в S
Для всех элементов zi из U, перебирая их в порядке возрастания выполним:
Если y + ε*s/n < z ≤ s, положим y = z и внесем z в список S
(тем самым мы исключаем близкие значения и отбрасываем значения, превосходящие s)
Если S содержит число между (1− ε)*s и s, говорим Да, в противном случае - Нет

Само создание списка описано весьма туманно. Возможно ли заполнить список по другой схеме?

Полный получившийся алгоритм:
Создаем списки S и Т, первоначально состоящие из одного элемента 0.
Для всех i от 1 до n выполним следующие действия:
Записываем в список T xi
Записываем в список S суммы элемента xi с другими ранее записанными элементами в списке Т
Создаем список U, равный объединению T и S
Сортируем элементы из списка U в порядке возрастания
Отбрасываем из списка U повторяющиеся элементы
Пусть y – наименьший элемент U
Внесем y в D
Для всех элементов zi из U, i от 1 до k, k – длина списка D перебирая их в порядке возрастания выполним:
Если y + ε*s/k < zi≤ s
Положим y = zi и внесем z в список D (тем самым мы исключаем близкие значения и отбрасываем значения, превосходящие s)
Eсли D содержит число между (1− ε)*s и s включительно, говорим Да, в противном случае - Нет

Насколько критична будет замена?

Ответить