«Исследование жадного алгоритма». Курсовая работа включает в себя разработку программой модели нахождения наикратчайшего расстояния - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр... 1 42.31kb.
Данный раздел включает работу с текстовой информацией, одномерными... 1 192.27kb.
Контрольная работа по теме «Алгоритмизация и программирование» 1 15.09kb.
О методе построения модели перемещения шагающей платформы 1 24.52kb.
Исследование эффективности генетического алгоритма условной оптимизации 1 55.38kb.
Техническое задание на создание рабочей версии сайта Санкт-Петербурга... 1 90.94kb.
Тестирование 1 38.51kb.
Карта инноваций гбоу ао скош №15 г 1 33.77kb.
Наукові записки ундіз, №4(6), 2008 1 12.14kb.
Тест по курсу «Теория алгоритмов» Специальность «Информатика и вычислительная... 3 419.17kb.
Библия Невады: Глава четвертая Февраль 2012 г. (обновлено в 2014 г. 1 142.14kb.
Блоки оконные и дверные метод определения звукоизоляции windows and... 1 147.56kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

«Исследование жадного алгоритма». Курсовая работа включает в себя разработку программой - страница №1/1


Изм.

Лист

докум.



Подп.

Дата











Лист

051.1-23 01 00.121338.13.81-01





Аннотация.

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

Введение.

Понятие алгоритмической стратегии позволяет классифицировать базовые алгоритмы обработки данных по группам их использования. Более современное понимание термина относится к программным реализациям

алгоритмов.

Стратегия, Strategy — поведенческий шаблон проектирования, предназначенный для определения семейства алгоритмов, инкапсуляции каждого из них и обеспечения их взаимозаменяемости. Это позволяет выбирать алгоритм путем определения соответствующего класса. Шаблон Strategy позволяет менять выбранный алгоритм независимо от объектов-клиентов, которые его используют.

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

К базовым алгоритмам программирования можно отнести:

• Алгоритмы работы со структурами данных. Они определяют базовые принципы и методологию, используемые для реализации, анализа и сравнения алгоритмов. Позволяют получить представление о методах представления данных. К таким структурам относятся связные списки и строки, деревья, абстрактные типы данных, такие как стеки и очереди.

•Алгоритмы сортировки, предназначенные для упорядочения массивов и файлов, имеют особую важность. С алгоритмами сортировки связаны, в частности, очереди по приоритету, задачи выбора и слияния.

●Алгоритмы поиска, предназначенные для поиска конкретных элементов в больших коллекциях элементов. К ним относятся основные и расширенные методы поиска с использованием деревьев и преобразований цифровых ключей, в том числе деревья цифрового поиска, сбалансированные деревья, хеширование, а также методы, которые подходят для работы с очень крупными файлами.

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

•Алгоритмы обработки строк включают ряд методов обработки (длинных) последователей символов. Поиск в строке приводит к сопоставлению с эталоном, что в свою очередь ведет к синтаксическому анализу. К

этому же классу задач можно отнести и технологии сжатия файлов.

•Геометрические алгоритмы – это методы решения задач с использованием точек и линий (и других простых геометрических объектов), которые вошли в употребление достаточно недавно. К ним относятся алгоритмы построения выпуклых оболочек, заданных набором точек, определения пересечений геометрических объектов, решения задач отыскания ближайших точек и алгоритма многомерного поиска. Многие из этих методов дополняют простые методы сортировки и поиска.

Выделим алгоритмические стратегии, которые используются в алгоритмах:

•"Разделяй и властвуй";

Идея алгоритма “Разделяй и властвуй” (англ. “divide and conquer”) состоит из нескольких шагов:

1. Разделение задачи на подзадачи, как правило меньшего размера

2. Решение каждой из подзадач (напрямую, если они достаточно небольшого объёма – иначе рекурсивно, разбивая на меньшие части)

3. Объединение полученных решений подзадач

В силу специфики этого метода оценка времени выполнения всегда будет представляться в виде рекуррентности, которую удобно решать с помощью основной теоремы.

Этот метод применим только в случаях, когда подзадачи являются независимыми. Если подзадачи будут взаимозависимыми, то алгоритм «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подзадачи по несколько раз.

•алгоритмы с возвратом;

Решение задачи с использованием алгоритма с возвратом сводится к последовательному расширению частичного решения. Если на очередном шаге такое расширение провести не удается, то возвращаются к более короткому частичному решению и продолжают поиск дальше. Данный алгоритм позволяет найти все решения поставленной задачи, если они существуют. Для ускорения метода стараются вычисления организовать таким образом, чтобы как можно раньше выявлять заведомо неподходящие варианты. Зачастую это позволяет значительно уменьшить время нахождения решения.

Классическим примером использования алгоритма с возвратом является задача о восьми ферзях. Её формулировка такова: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Сперва на доску ставят одного ферзя, а потом пытаются поставить каждого следующего ферзя так, чтобы его не били уже установленные ферзи. Если на очередном шаге такую установку сделать нельзя — возвращаются на шаг назад и пытаются поставить ранее установленного ферзя на другое место.

•эвристические алгоритмы;

Эвристический алгоритм — это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат.

Проще говоря, эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.

Важно понимать, что эвристика, в отличие от корректного алгоритма решения задачи, обладает следующими особенностями:

Она не гарантирует нахождение лучшего решения.

Она не гарантирует нахождение решения, даже если оно заведомо существует (возможен «пропуск цели»).

Она может дать неверное решение в некоторых случаях.

•сопоставления с образцом и алгоритмы обработки строк/текстов;

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

Уменьшает или исключает избыточность условий за счет объединения узлов.

Сохраняет частичные соответствия между фактами при слиянии разных типов фактов. Это позволяет избежать полного вычисления (re-evaluation) всех фактов при любом изменении в рабочей памяти продукционной системы. Система работает только с самими изменениями (deltas).

Позволяет эффективно высвобождать память при удалении фактов.


Алгоритм обработки строк/текстов широко используется для реализации сопоставления с образцом в системах с циклом сопоставление-решение-действие (match-resolve-act) для генерации и логического вывода.

•динамическое программирование;

Динамическое программирование, как правило, применяется к задачам оптимизации (optimization problems). В таких задачах возможно наличие многих решений. Каждому варианту решения можно сопоставить какое-то значение, и нам нужно найти среди них решение с оптимальным (минимальным или максимальным) значением. Назовем такое решение одним из возможных оптимальных решений. В силу того, что таких решений с оптимальным значением может быть несколько, следует отличать их от единственного оптимального решения.

Процесс разработки алгоритмов динамического программирования можно разбить на четыре перечисленных ниже этапа.

1. Описание структуры оптимального решения.

2. Рекурсивное определение значения, соответствующего оптимальному решению.

3. Вычисление значения, соответствующего оптимальному решению, с помощью метода восходящего анализа.

4. Составление оптимального решения на основе информации, полученной на предыдущих этапах.

Этапы 1-3 составляют основу метода динамического программирования. Этап 4 может быть опущен, если требуется узнать только значение, соответствующее оптимальному решению. На четвертом этапе иногда используется дополнительная информация, полученная на третьем этапе, что облегчает процесс конструирования оптимального решения.

•жадные алгоритмы.

В данной курсовой работе подробно будет рассмотрен жадный алгоритм

1 Анализ и теоретическое исследование алгоритма.

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

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


1.2 Основные понятия жадного алгоритма.
Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь алгоритм превратится в стратегию “иди в ближайший, в который еще не входил, город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

В пользу процедуры “иди в ближайший” можно сказать лишь то, что при старте из одного города она не уступит стратегии “иди в дальнейший”.

Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного алгоритма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть fB - настоящий минимум, а fA - тот квазиминимум, который получен по алгоритму. Ясно, что fA/ fB≥1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно «зажать» отношение оценкой сверху:

fA/fB ≥ 1+nε (1)

где, как обычно в высшей математике, ε≥0, но, против обычая, может быть очень большим. Величина ε и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (1), мы будем говорить, что он имеет погрешность ε.

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




С[i,j]={

1, если ребро (i,j) принадлежит Е

1+nε, в противном случае




Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и fB = n. Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, не переборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+nε. Но тогда fA  (n-1)+(1+nε) так что fA/fB = 1+nε, т.е. превосходит погрешность ε на заданную неравенством (1). О величине ε в нашем рассуждении мы не договаривались, так что ε может быть произвольно большим.

Таким образом доказана следующая теорема.



Либо алгоритм А определяет, существует ли в произвольном графе гамильтонов цикл, либо погрешность А при решении ЗК может быть произвольно велика.

Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника.


1.3 Правильность алгоритма.

Не для всех задач жадный алгоритм дает оптимальное решение, но для нашей дает. Убедимся в этом.

Теорема 1. Алгоритм Greedy-Activity- Selector дает набор из наибольшего возможного количества совместных заявок.

Доказательство. Напомним, что заявки отсортированы по возрастанию времени окончания. Прежде всего докажем, что существует оптимальное решение задачи о выборе заявок, содержащее заявку номер1 (с самым ранним временем окончания). В самом деле, если в каком-то оптимальном множестве заявок заявка номер 1 не содержится, то можно заменить в нем заявку с самым ранним временем окончания не заявку номер 1, что не повредит совместности заявок ( ибо заявка номер 1 кончается еще раньше, чем прежняя, и не с чем пересечься не может) и не изменит их общего количества. Стало быть, можно искать оптимальное решение, начинающееся с жадного выбора.

После того, как мы договорились рассматривать только наборы, содержащие заявку номер 1, все несовместные с ней заявки можно выкинуть, и задача сводится к выбору оптимального набора заявок из множества оставшихся заявок (совместных с заявкой номер 1). Другими словами, мы свели задачу к аналогичной задаче с меньшим числом заявок. Рассуждая по индукции, получаем, что, делая на каждом шаге жадный выбор, мы придем к оптимальному решению.
1.4 Принцип жадного выбора.
Говорят, что к оптимизационной задаче применим принцип жадного выбора (greedy-choice property), если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берет "самый жирный кусок", а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни были; алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов.

Как доказать, что жадный алгоритм дает оптимальное решение? Это не всегда тривиально, но в типичном случае такое доказательство следует схеме, использованной в доказательстве теоремы 1. Сначала мы доказываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.

1.5 Оптимальная подструктура задачи о выборе процессов.

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

Sn = К {eSifi^ sk < fk ^ Sj}. (2)

Sjj — подмножество процессов из множества S, которые можно успеть выполнить в промежутке времени между завершением процесса аг и началом процесса cij.

Фактически множество Sjj состоит из всех процессов, совместимых с процессами а, и cij, а также теми, которые оканчиваются не позже процесса щ и теми, которые начинаются не ранее процесса cij. Для представления всей задачи добавим фиктивные процессы ао и an+i и примем соглашение, что /о = 0 и sn+\ = оо.

Тогда 5 = 5*0,7?+], ^ лщексы г и j находятся в диапазоне 0 ^ г, j ^ п + 1.

Дополнительнь : ограничения диапазонов индексов г и j можно получить с помощью приведенных ниже рассуждений. Предположим, что процессы отсортированы в порядке возрастания соответствующих им конечных моментов времени:

(3)

Утверждается, что в этом случае Sjj = 0, если г ^ j. Почему? Предположим, что существует процесс a^eSij для некоторого г ^ j, так что процесс а* следует после процесса clj, если расположить их в порядке сортировки. Однако из определения Sij следует соотношение fo ^ s/~ < Д < Sj < fj, откуда fo < fj, что противоречит предположению о том, что процесс щ следует после процесса а^, если расположить их в порядке сортировки. Можно прийти к выводу, что если процессы отсортированы в порядке монотонного возрастания времени их окончания, то пространство подзадач образуется путем выбора максимального подмножества взаимно совместимых процессов из множества S^ для 0^i

Чтобы понять подструктуру задачи о выборе процессов, рассмотрим некоторую непустую подзадачу Sijl и предположим, что ее решение включает некоторый процесс а/., так что fa ^ Sk < fk ^ Sj. С помощью процесса а^ генерируются две подзадачи, S^ (процессы, которые начинаются после окончания процесса и заканчиваются перед началом процесса а^) и Skj (процессы, которые начинаначинаются после окончания процесса а^ и заканчиваются перед началом процесса а каждая из которых состоит из подмножества процессов, входящих в Sij. Решение задачи Sij представляет собой объединение решений задач Sik, Skj и процесса «д..

Таким образом, количество процессов, входящее в состав решения задачи S^, — это сумма количества процессов в решении задачи Sjk, количества процессов в решении задачи Skj и еще одного процесса (а&).

Опишем оптимальную подструктуру этой задачи. Предположим, что оптимальное решение Ац задачи Sij включает в себя процесс а^. Тогда решения Aik задачи Sik и Ащ задачи Skj в рамках оптимального решения Sij тоже должны быть оптимальными. Как обычно, это доказывается с помощью рассуждений типа "вырезания и вставки". Если бы существовало решение A'ik задачи 5^, включающее в себя большее количество процессов, чем Aik, в решение A\j можно было бы вместо Aik подставить Afik, что привело бы к решению задачи Sij, в котором содержится больше процессов, чем в Aij. Поскольку предполагается, что A7J — оптимальное решение, мы приходим к противоречию. Аналогично, если бы существовало решение Ащ задачи Skj, содержащее больше процессов, чем Akj, то путем замены Akj на А'к- можно было бы получить решение задачи Sij, в которое входит больше процессов, чем в Aij. Теперь с помощью сформулированной выше оптимальной подструктуры покажем, что оптимальное решение задачи можно составить из оптимальных решений подзадач. Мы уже знаем, что в любое решение непустой задачи S^ входит некоторый процесс ak и что любое оптимальное решение задачи содержит в себе оптимальные решения подзадач Sjk и Skj- Таким образом, максимальное подмножество взаимно совместимых процессов множества S^ можно составить путем разбиения задачи на две подзадачи (определение подмножеств максимального размера, состоящих из взаимно совместимых процессов в задачах 5^ и Skj) — собственно нахождения максимальных подмножеств А^ и Ащ взаимно совместимых процессов, являющихся решениями этих подзадач, и составления подмножества A{j максимального размера, включающего в себя взаимно совместимые задачи:

(4)

Оптимальное решение всей задачи представляет собой решение задачи Sb,n+i

1.6 Рекурсивное решение

Второй этап разработки решения по методу динамического программирования — определение значения, соответствующего оптимальному решению. Пусть в задаче о выборе процесса c[z,j] — количество процессов в подмножестве максимального размера, состоящем из взаимно совместимых процессов в задаче 5ц. Эта величина равна нулю при S^ = 0; в частности, с [г, j] = 0 при г ^ j. Теперь рассмотрим непустое подмножество S^. Мы уже знаем, что если процесс ак используется в максимальном подмножестве, состоящем из взаимно совместимых процессов задачи 5^, то для подзадач Sik и Skj также используются подмножества максимального размера. С помощью уравнения A6.2) получаем рекуррентное соотношение



(5)

В приведенном выше рекурсивном уравнении предполагается, что значение к известно, но на самом деле это не так. Это значение можно выбрать из j — г - 1 возможных значений: к = г + 1,... ,j — 1. Поскольку в подмножестве максимального размера для задачи Sij должно использоваться одно из этих значений к, нужно проверить, какое из них подходит лучше других. Таким образом, полное рекурсивное определение величины c[i,j] принимает вид:



1.7 Преобразование решения динамического программирования в жадное решение.

На данном этапе не составляет труда написать восходящий алгоритм динамического программирования, основанный на рекуррентном уравнении A6.3). Это предлагается сделать читателю в упражнении A6.1-1). Однако можно сделать два наблюдения, позволяющие упростить полученное решение.

Теорема1. Рассмотрим произвольную непустую задачу S^ и пусть ат —процесс, который оканчивается раньше других:

fm = min {Л : akeSij}.

В этом случае справедливы такие утверждения.

1. Процесс ат используется в некотором подмножестве максимального размера, состоящем из взаимно совместимых процессов задачи Sij.

2. Подзадача S{m пустая, поэтому в результате выбора процесса ат непустой остается только подзадача Smj.

Доказательство. Сначала докажем вторую часть теоремы, так как она несколько проще. Предположим, что подзадача Sim непустая и существует некоторый процесс аь такой что fi ^ Sfc < fk ^ sm < fm- Тогда процесс а* также входит в решение подзадачи 5im, причем он оканчивается раньше, чем процесс ат, что противоречит выбору процесса ат. Таким образом, мы приходим к выводу, что решение подзадачи Sim — пустое множество.

Чтобы доказать первую часть, предположим, что Ац — подмножество максимального размера взаимно совместимых процессов задачи 5#, и упорядочим процессы этого подмножества в порядке возрастания времени их окончания. Пусть ak — первый процесс множества >4у. Если а& = ат, то доказательство завершено, поскольку мы показали, что процесс ат используется в некотором подмножестве максимального размера, состоящем из взаимно совместимых процессов задачи Sij. Если же ak ф аш, то составим подмножество А'^ = A\j — {a/J U {am}. Процессы в A'ij не перекрываются, поскольку процессы во множестве Aij не перекрываются, а& — процесс из множества Aij, который оканчивается раньше всех, и fm ^ Д. Заметим, что количество процессов во множестве А[- совпадает с количеством процессов во множестве Ац, поэтому А!ц — подмножество максимального размера, состоящее из взаимно совместимых процессов задачи S^ и включающее в себя процесс ат. U

Следующая подзадача — 5mi?n+i. Теперь предположим, что в качестве процесса задачи Smull+i, который оканчивается раньше других, выбран процесс аП12. Следующая на очереди подзадача — S7r?2?n+i. Продолжая рассуждения, нетрудно убедиться в том, что каждая подзадача будет иметь вид 57?,i?n+i и ей будет соответствовать некоторый номер процесса m.j. Другими словами, каждая подзадача состоит из некоторого количества процессов,завершающихся последними, и это количество меняется от одной подзадачи к другой.

Для процессов, которые первыми выбираются в каждой подзадаче, тоже существует свой шаблон. Поскольку в задаче Sm.Ol+i всегда выбирается процесс, который оканчивается раньше других, моменты окончания процессов, которые последовательно выбираются во всех подзадачах, образуют монотонно возрастающую последовательность. Более того, каждый процесс в процессе решения задачи можно рассмотреть лишь один раз, воспользовавшись сортировкой в порядке возрастания времен окончания процессов.

В ходе решения подзадачи всегда выбирается процесс ат, который оканчивается раньше других. Таким образом, выбор является жадным в том смысле, что интуитивно для остальных процессов он оставляет как можно больше возможностей войти в расписание. Таким образом, жадный выбор — это такой выбор, который максимизирует количество процессов, пока что не включенных в расписание.

1.8 Рекурсивный жадный алгоритм.

После того как стал понятен путь упрощения решения, основанного на принципах динамического программирования, и преобразования его в нисходящий метод, можно перейти к рассмотрению алгоритма, работающего исключительно в жадной нисходящей манере. Здесь приводится простое рекурсивное решение, реализованное в виде процедуры Recursive_Activity_Selector. На ее вход подаются значения начальных и конечных моментов процессов, представленные в виде массивов s и /, а также индексы г и п, определяющие подзадачу S;jn+b которую требуется решить. Процедура возвращает множество максимального размера, состоящее из взаимно совместимых процессов задачи S^n+i- В соответствии с уравнением A6.1), предполагается, что все п входных процессов расположены в порядке монотонного возрастания времени их окончания. Если это не так, их можно отсортировать в указанном порядке за время О (п lg n). Начальный вызов этой процедуры имеет вид Recursive_ActivityJSelector(s, /, 0, п).

Работа представленного алгоритма процессов проиллюстрирована на рис. 16.1. Процессы, которые рассматриваются в каждом рекурсивном вызове, разделены горизонтальными линиями.

Фиктивный процесс ао оканчивается в нулевой момент времени, и в начальном вызове, который имеет вид Recursive_Activity__Selector(s, /, 0,11), выбирается процесс а\. В каждом рекурсивном вызове заштрихованы процессы, которые уже были выбраны, а белым цветом обозначен рассматриваемый процесс. Если начальный момент процесса наступает до конечного момента процесса, который был добавлен последним (т.е. стрелка, проведенная от первого процесса ко второму, направлена влево), такой процесс отвергается. В противном случае (стрелка направлена прямо вверх или вправо) процесс выбирается. В последнем рекурсивном вызове процедуры, имеющем вид Recursive_Activity_Selector(s,/, 11,11), возвращается 0. Результирующее множество выбранных процессов — {а\, а4, ag, an}.

В рекурсивном вызове процедуры Recursive_Activity_Selector(s, /,г,п) в цикле while в строках 2-3 осуществляется поиск первого процесса задачи 5,->n+i.

В цикле проверяются процессы а^+х, <2i+2>..., ап до тех пор, пока не будет найден первый процесс ат> совместимый с процессом а*; для такого процесса справедливо соотношение sm ^ /». Если цикл завершается из-за того, что такой процесс найден, то происходит возврат из процедуры в строке 5, в которой процесс {ат} объединяется с подмножеством максимального размера для задачи Smjn+i, которое возвращается рекурсивным вызовом Recursive_Activity_Selector(s, /, m, n).

Еще одна возможная причина завершения процесса — достижение условия т > п. В этом случае проверены все процессы, но среди них не найден такой, который был бы совместим с процессом щ. Таким образом, 5i,n+i = 0 и процедура возвращает значение 0 в строке 6. Если процессы отсортированы в порядке, заданном временем их окончания, время, которое затрачивается на вызов процедуры Recursive_Activity_Selector(s, /, 0, п), равно 0(п). Это можно показать следующим образом. Сколько бы ни было рекурсивных вызовов, каждый процесс проверяется в цикле while в строке 2 ровно по одному разу. В частности, процесс аь проверяется в последнем вызове, когда г < к.





1.9 Итерационный жадный алгоритм.

Представленную ранее рекурсивную процедуру легко преобразовать в итеративную. Процедура Recursive_ActivityJSelector почти подпадает под определение оконечной рекурсии (см. задачу 7-4): она оканчивается рекурсивным вызовом самой себя, после чего выполняется операция объединения. Преобразование процедуры, построенной по принципу оконечной рекурсии, в итерационную — обычно простая задача. Некоторые компиляторы разных языковпрограммирования выполняют эту задачу автоматически. Как уже упоминалось, процедура Recursive_Activity__Selector выполняется для подзадач 5г,п+ь те- Для подзадач, состоящих из процессов, которые оканчиваются позже других. Процедура Greedy_Activity_Selector — итеративная версия процедуры RECURSIVE_Activity_Selector. В ней также предполагается, что входные процессы расположены в порядке монотонного возрастания времен окончания. Выбранные процессы объединяются в этой процедуре в множество А, которое и возвращается процедурой после ее окончания.

Процедура работает следующим образом. Переменная г индексирует самое последнее добавление к множеству А, соответствующее процессу а* в рекурсивной версии. Поскольку процессы рассматриваются в порядке монотонного возрастания моментов их окончания, fi — всегда максимальное время окончания всех процессов, принадлежащих множеству А:



В строках 2-3 выбирается процесс а\, инициализируется множество А, содержащее только этот процесс, а переменной г присваивается индекс этого процесса.

В цикле for в строках 4-7 происходит поиск процесса задачи Si|fl+i, оканчивающегося раньше других. В этом цикле по очереди рассматривается каждый процесс ат, который добавляется в множество А, если он совместим со всеми ранее выбранными процессами; этот процесс оканчивается раньше других в задаче S^n+i- Чтобы узнать, совместим ли процесс ат с процессами, которые уже содержатся во множестве А, в соответствии с уравнением A6.4) достаточно проверить (строка 5), что его начальный момент sm наступает не раньше момента fo окончания последнего из добавленных в множество А процессов. Если процесс ат удовлетворяет сформулированным выше условиям, то в строках 6-7 он добавляется в множество А и переменной г присваивается значение га. Множество А, возвращаемое процедурой Greedy_Activity_Selector(s, /), совпадает с тем, которое возвращается процедурой Recursive_Activity_Selector(s, /, 0, п). Процедура Greedy_Activity_Selector, как и ее рекурсивная версия, составляет расписание для n-элементного множества в течение времени в (п). Это утверждение справедливо в предположении, что процессы уже отсортированы в порядке возрастания времени их окончания.

2 Разработка технологии экспериментального исследования алгоритм.



2.1 Блок схема программы и ее описание.