|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[287] Идея алгоритма проста: если через Рг- обозначить множество всех чисел, которые можно получить, складывая некоторые из Х1,Х2,... , Xi, то Pi = Pi-i U (Рг ! + Xi)(37.11) (элемент жг- может не входить в сумму, а может и входить) мы видим (индукция по г, упражнение 37.4-1), что Li представляет собой список элементов множества Рг- в порядке возрастания (из которого выброшены элементы, большие t). Сколько времени требует этот алгоритм? Список Li может содержать до 2г элементов, так что алгоритм экспоненциален. Впрочем, если t (или все элементы S) ограничено сверху многочленом от \S\, то время работы алгоритма также ограничено многочленом от \S\. Полностью полиномиальная схема приближения Такая схема получается из описанного алгоритма, если хранить списки Li в сокращенной форме. Степень сокращения опредеояет-ся параметром 8 - чем он меньше, тем ближе список к полному. Список V называется -сокращением списка L, если V является частью L и для любого элемента у из L в списке V найдётся не превосходащий его элемент z, для которого У-8 У или, другими словами, (1 - $)У z у. Тем самым любой элемент у, выброшенный из L при получении меньшего списка V, представлен в V своим приближением снизу с относительной ошибкой (относительно у) не более 8. Например, для 8 = 0,1 и L = (10,11,12,15,20,21,22, 23, 24, 29) список L = (10,13,15,20,23,29) является -сокращением L, в котором выброшенное число 11 представлено числом 10, числа 21 и 22 представлены числом 20, а число 24 представлено числом 23. Важно иметь в виду, что 5-сокращение является частью оригинального списка. При этом число элементов может сильно уменьшится, но для всех выброшенны элементов чуть меньшие значения останутся. Следующая процедура сокращает список L = (у\, у2, , ут), упорядоченный по возрастанию, за время О (то). Её результат V является 5-сокращеним L; список V также упорядочен по возрастанию. \textsc{Trim} (L, \delta) 1m <- L 2L <- <y l> 3last <- y l 4for i<-2 to m 5do if last < (l-\delta) y i 6then дописать $y i$ в конец списка L 7last <- y i 8return L Элементы списка L просматриваются в порядке возрастания, и в V помещается первый из них, а также те, которые слишком велики, чтобы быть представленными последним из уже имеющихся элементов списка V. Теперь схема приближения для задачи о суммах подмножеств может быть построена следующим образом. Напомним, что исходными данными для неё являются последовательность S = (xi, х2,... ,хп) из п чисел (идущих в произвольном порядке), число t, а также параметр приближения е (в интервале 0 < е < 1). \textsc{Approx-Subset-Sum}(S,t,\varepsilon) 1n <- SI 2L 0 <- <0> 3for i<-l to n 4do L i <- Merge-Lists(L {i-l>,L {i-l>+x i) 5L i <- Trim (L i, \varepsilon/n) 6все элементы $L i$, большие $t$, удаляются 7z <- наибольший элемент $L n$ 8return z Вначале (строка 2) в список Lq помещается единственный элемент 0. В строках 3-6 мы последовательно (для г = 1,...п) вычисляем список Li, который окажется сокращением множества Pi (всевозможных сумм, составленных из первых г элементов) из которого удалены все элементы, большие t. Отметим, что это требует специальной проверки, так как сокращения производятся на каждом шаге, и в строке 4 соединяются уже сокращенные варианты списков. Прежде чем проверять это, рассмотрим пример: пусть L = (104,102,201,101) при этом t = 308 и е = 0,2. Тогда на каждом шаге производиться 0,05-сокращение, и вычисления проходят так: строка 2: L 0 = <0>,
В ответе получается z = 302, что отличается от оптимального варианта (307 = 104+102+101) менее чем на 2% (что много меньше разрешённого отклонения в 20%). Теорема. Алгоритм Approx-Subset-Sum представляет собой полностью полиномиальную схему приближения для задачи о сумме подмножества. Доказательство. Обе операции (сокращение списка в строке 5 и удаление слишком больших элементов в строке 6) могут лишь уменьшить список, так что список Li остаётся подмножеством множества Д. (Напомним, что через Pi обозначается множество всех чисел, которые можно получить, складывая некоторые из Ж1,Ж2,... , Xi.) Таким образом, число z действительно будет суммой некоторого подмножества, причём z t. Осталось проверить лишь, что оно не меньше (1-е), умноженного на максимально возможную сумму, не превосходящую t. (Именно этого требует неравенство (37.2) для нашейго случая.) Посмотрим, к какой ошибке приводит сокращение списка на каждом шаге. При сокращении остающееся число будет меньше вычеркнутого, но не намного: не более чем на (е/п)-ую долю. Другими словами, остающийся элемент не меньше вычеркнутого, умноженного на (1 - е/п). Рассуждая по индукции, легко видеть, что для всякого элемента у множества Pi, не превосходящего t, можно указать элемент z в списке Li, для которого В частности, при г = п можно взять в качестве у оптимальное решение задачи о сумме подмножества и убедиться, что существует z £ Ln, для которого (1 -е/п)пу <z <у |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||