Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Основы теории алгоритмов

.docx
Скачиваний:
30
Добавлен:
15.03.2016
Размер:
446.59 Кб
Скачать

Тема: Основы теории алгоритмов

Цель работы:

  • Изучить методы построения минимального остовного дерева.

  • Изучить методы раскраски графа в минимальное число цветов.

Задание

Задан неориентированный взвешенный граф G. Построить минимальные остовные деревья Жадным алгоритмом и алгоритмом Прима.

Дан неориентированный граф G. Раскрасить граф последовательным алгоритмом в минимальное число цветов.

Построение МОД жадным алгоритмом

Обозначим вершины в графе:

Составим таблицу ребер графа:

Ребро

ab

ah

ai

bc

be

bi

cd

ce

de

ef

ei

fg

fh

fi

gh

вес

4

1

2

5

4

1

3

3

2

1

3

2

5

4

6

  1. выбираем ребро с минимальным весом, которое не вызывает появление цикла в остове ah=1

  2. bi=1

  3. ef=1

  4. ai=2

  5. de=2

  6. fg=2

  7. cd=3

  8. ce=3 пропускаем, т.к. появится цикл.

  9. ei=3

  10. все остальные ребра образуют циклы. МОД графа получено.

Построение МОД алгоритмом Прима

Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Таким образом, при выполнении каждого шага алгоритма, высота формируемого дерева увеличивается на 1. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.

  1. В качестве начальной выберем вершину E и найдем инцидентное ей ребро с минимальным весом ef=1

  2. Далее найдем ребро с минимальным весом среди инцидентных вершинам дерева: ed=2

  3. fg=2

  4. cd=3

  5. ei=3

  6. bi=1

  7. ai=2

  8. ah=1

  9. Все вершины задействованы, МОД графа получено

Раскраска графа

  1. Упорядочим вершины по невозрастанию степени и окрасим первую вершину в цвет 1 и выберем этот цвет:

    Вершина

    5

    1

    8

    4

    3

    2

    7

    6

    9

    Степень

    5

    4

    4

    4

    3

    3

    3

    2

    2

    Цвет

    1

  2. Окрасим в выбранный цвет всякую вершину, которая не смежна с другой, уже окрашенной в этот цвет.

    Вершина

    5

    1

    8

    4

    3

    2

    7

    6

    9

    степень

    5

    4

    4

    4

    3

    3

    3

    2

    2

    цвет

    1

    -

    -

    -

    1

    -

    -

    -

    1

  3. Выберем краску 2 и повторим действие

    Вершина

    5

    1

    8

    4

    3

    2

    7

    6

    9

    степень

    5

    4

    4

    4

    3

    3

    3

    2

    2

    цвет

    1

    2

    2

    -

    1

    -

    -

    2

    1

  4. Выберем краску 3 и повторим действие

Вершина

5

1

8

4

3

2

7

6

9

степень

5

4

4

4

3

3

3

2

2

цвет

1

2

2

3

1

3

3

2

1

Контрольные вопросы

Определение алгоритма.

Алгоритмом называется точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.

Свойства алгоритма.

Основными свойствами алгоритма являются:

  • детерминированность (определенность). Предполагает получение однозначного результата вычислительного процесса при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;

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

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

  • дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

Определение комбинаторного алгоритма.

Комбинаторные алгоритмы предназначаются для выполнения вычислений на дискретных конечных математических структурах. 

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

Излагаются современные комбинаторные алгоритмы для решения задач дискретной оптимизации с применением компьютерных средств. Основное внимание уделяется вычислительной реализации алгоритмов. Приводятся результаты вычислительного исследования алгоритмов для классических задач дискретной оптимизации - задачи о ранце и задачи о коммивояжере. Приведено много примеров для самостоятельной работы. 

В комбинаторных алгоритмах часто необходимо порождать и исследовать все элементы некоторого класса комбинаторных объектов. 

Суть жадного алгоритма.

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

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

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

Суть эвристического алгоритма. Основные правила.

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

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

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

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

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

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

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