Хиценко В.П., Шапошникова Т.А. Практикум на ЭВМ. Алгоритмы - файл n1.doc

приобрести
Хиценко В.П., Шапошникова Т.А. Практикум на ЭВМ. Алгоритмы
скачать (6517.5 kb.)
Доступные файлы (1):
n1.doc6518kb.10.06.2012 10:23скачать

n1.doc

  1   2   3   4   5   6   7   8   9


Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Практикум на эвм

АЛГОРИТМЫ


Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
для студентов I курса ФПМиИ
(направление 510200 – Прикладная математика
и информатика, специальность 351500 –
Математическое обеспечение и администрирование
информационных систем) дневной формы обучения

Новосибирск
2004

УДК 004.421+519.1](075.8)

         П 691

Авторы: В. П. Хиценко, ст. преподаватель,

Т. А. Шапошникова, ст. преподаватель


Рецензенты: С.Х. Рояк, канд. техн. наук, доц.,

Л.В. Тюнина, канд. техн. наук, доц.
Работа подготовлена на кафедре прикладной математики


Практикум на ЭВМ. Алгоритмы

П 691 Учебное пособие / В.П. Хиценко, Т.А. Шапошникова. – Новосибирск: Изд-во НГТУ, 2004. – 112 с.
Рассмотрены основные алгоритмы, изучаемые в курсе «Практикум на ЭВМ»: алгоритмы на графах, комбинаторные алгоритмы, алгоритмы полного перебора. Разобрано много примеров, иллюстрирующих теоретический материал.

УДК 004.421+519.1](075.8)




©


Новосибирский государственный
технический университет, 2004   
оглавление

Курс «Практикум на ЭВМ» является первой базовой дисциплиной среди программистских дисциплин. Нельзя овладеть программированием без знания важнейших и известнейших алгоритмов. В данном учебном пособии подробно разобраны алгоритмы, широко применяемые при решении разных классов задач: основные алгоритмы на графах, алгоритм полного перебора и методы его улучшения (алгоритмы динамического программирования, «жадный» алгоритм, метод ветвей и границ), алгоритмы формирования основных комбинаторных объектов.

Учебное пособие предназначено не только для студентов, изучающих начальные разделы программирования, но и для тех, кто желает обогатить свои навыки конструирования алгоритмов (вместо «изобретения очередного велосипеда»). Часто разница между плохим и хорошим алгоритмами более существенна, чем между быстрым и медленным компьютерами. Например, мы хотим отсортировать массив из миллиона чисел. Что быстрее – отсортировать его вставками на супер–компьютере (100 миллионов операций в секунду) или слиянием на домашнем компьютере (1 миллион операций)? При этом, если сортировка вставками написана на ассемблере чрезвычайно экономно, для сортировки n чисел нужно приблизительно 2n2 операций. В то же время алгоритм слиянием написан без особой заботы об эффективности и требует 50·n· log n операций. В первом случае для сортировки 1 миллиона чисел получаем:

для супер–компьютера:



для домашнего компьютера:




Отсюда видно, что разработка эффективных алгоритмов не менее важна, чем разработка быстрой электроники.

Учебное пособие дополняет лекционный и практический материал дисциплины «Практикум на ЭВМ» и ориентировано прежде всего на поддержку самостоятельной работы студентов при выполнении РГР и курсовых работ. Поэтому каждый алгоритм, приведенный в учебном пособии, разобран на практическом примере, для некоторых приведена программная реализация на языке программирования (Си). Также для алгоритмов даны оценки их сложности.

Алгоритмы записаны в виде «псевдокода», прокомментированы в тексте, наглядно представлены на рисунках и в таблицах.


1. Основные алгоритмы на графах

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

1.1. Некоторые основные определения

Графом (неориентированным графом) G(V,E) называется совокупность двух множеств, где V – конечное непустое множество элементов, называемых вершинами, а E – множество неупорядоченных пар различных элементов множества V (эти пары называются ребрами). Граф, состоящий из одной вершины, называется тривиальным.

Говорят, что ребро e = (u, v) соединяет вершины u и v. Ребро e и вершина u (а также e и v) называются инцидентными, а вершины u и vсмежными. Ребра, инцидентные одной и той же вершине, также называются смежными.

Степень вершины – это число ребер, инцидентных ей. Вершина графа, имеющая степень 0, называется изолированной, а имеющая степень 1, – висячей.

Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф – мультиграфом.

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

Граф называется простым, если любая пара вершин соединена не более чем одним ребром и граф не имеет петель.

Маршрут (путь) – это чередующаяся последовательность

a = v0, e1, v1, e2, ..., vn1, en, vn = b

вершин и ребер графа такая, что ei = (vi-1 , vi), 1 ? i ? n. Говорят, что маршрут соединяет вершины a и b – концы маршрута. В простом графе маршрут можно задать перечислением лишь его вершин a = v0, v1, …, vn = b или его ребер e1 , e2, …, en.

Маршрут называется цепью, если все его ребра различные. Маршрут называется замкнутым, если v0 = vn.

Замкнутая цепь называется циклом. Цепь называется простой, если не содержит одинаковых вершин. Простая замкнутая цепь называется простым циклом.

Гамильтоновой цепью называется простая цепь, содержащая все вершины графа. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа.

Вершина u достижима из вершины v, если существует путь из v в u.

Длина пути v0 , v1, …, vn равна числу его ребер, т.е. n.

Расстояние между двумя вершинами – это длина кратчайшего пути, соединяющего эти вершины.

Часть графа G(V, E) – это такой граф G'(V',E'), что V' V и E'E.

Подграфом графа G называется такая его часть G', которая вместе со всякой парой вершин u, v содержит и ребро (u, v), если оно есть в G.

Дополнением графа G называется граф G' с тем же множеством вершин, что и у G, причем две различные вершины смежны в G' тогда и только тогда, когда они несмежны в G. Ребра графов G и G' вместе образуют полный граф. Граф называется полным, если любые две его вершины смежны.

Два графа G1 и G2 изоморфны, если существует взаимно однозначное отображение множества вершин графа G1 на множество вершин графа G2, сохраняющее смежность.

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

Если задана функция F: V?M, то множество M называется множеством пометок, а граф – помеченным. Если задана функция F: E?M, т.е. ребрам графа приписаны веса, то граф называется взвешенным.

Ребро графа называется ориентированным, если существен порядок расположения его концов. Граф, все ребра которого ориентированные, называется ориентированным графом (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Eдугами. Дуга (u, v) ведет от вершины u к вершине v, Вершину v называют преемником вершины u, а u – предшественником вершины v. Понятия части орграфа, пути, расстояния, простого и замкнутого пути, цикла определяются для орграфа так же, как и для графа, но с учетом ориентации дуг.

Источник орграфа – это вершина, от которой достижимы все остальные вершины. Сток орграфа – это вершина, достижимая со всех других вершин.

Деревом называется связный граф без циклов.

Корневое дерево – это связный орграф без циклов, удовлетворяющий условиям:

  1. имеется единственная вершина, называемая корнем, в которую не входит ни одна дуга;

  2. к каждой некорневой вершине ведет одна дуга.

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

1.2. Представление графов в ЭВМ

Представление в программе объектов математической модели – это важная составляющая программирования. Выбор наилучшего представления определяется требованиями конкретной задачи. Известны различные способы представления графов в памяти компьютера. Они различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Следует заметить, что во многих задачах на графах выбор представления – решающий для эффективности алгоритмов. На рис. 1.1 для неориентированного (а, б, в, г) и ориентированного (д, е, ж, з) графов показаны различные представления: б, е – матрица смежности; в, ж – матрица инцидентности; г – список смежности неориентированного графа при смежном размещении элементов списка; з – список смежности ориентированного графа при связанном размещении элементов списка.

1.2.1. Матрица смежности графа

Матрицей смежности помеченного графа с n вершинами называется матрица A = [aij], i, j = 1, 2, ..., n, в которой



Матрица смежности однозначно определяет граф (рис. 1.1, а–в, д–е). Для неориентированного графа матрица A является симметричной относительно главной диагонали. Число единиц в строке равно степени соответствующей вершины. Петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1.

Преимуществом такого представления является «прямой доступ» к ребрам графа, т.е. имеется возможность за один шаг получить ответ на вопрос «существует ли в графе ребро (x, y)?» Для небольших графов, когда места в памяти достаточно, с матрицей смежности часто проще работать. Недостаток заключается в том, что независимо от числа ребер объем занимаемой памяти составляет n  n или n  n/2 – n, если использовать симметрию и хранить только треугольную подматрицу матрицы смежности. Кроме того, каждый элемент матрицы достаточно представить одним двоичным разрядом.

1.2.2. Матрица инцидентности графа

Матрицей инцидентности называется матрица B = [bij], i =1, 2, ..., n, j = 1, 2, ..., m (где n – число вершин, а m – число ребер графа), строки которой соответствуют вершинам, а столбцы – ребрам. Элемент матрицы в неориентированном графе равен:



В случае ориентированного графа с n вершинами и m дугами элемент матрицы инцидентности равен:



Строки матрицы также соответствуют вершинам, а столбцы – дугам.

Матрица инцидентности однозначно определяет структуру графа (рис. 1.1, ав, д–ж). В каждом столбце матрицы B ровно две единицы. Равных столбцов нет.

Недостаток данного представления состоит в том, что требуется nm единиц памяти, большинство из которых будет занято нулями. Не всегда удобен доступ к информации. Например, для ответа на вопросы «есть ли в графе дуга (x, y)?» или «к каким вершинам ведут ребра из вершины x?» может потребоваться перебор всех столбцов матрицы.

1.2.3. Матрица весов графа

Простой взвешенный граф может быть представлен своей матрицей весов W = [wij], где wij – вес ребра, соединяющего вершины i, j = 1,2, ..., m. Веса несуществующих ребер полагаются равными ? или 0 в зависимости от задачи. Матрица весов – простое обобщение матрицы смежности.

1.2.4. Список ребер графа

При описании графа списком его ребер (или для орграфов списком дуг) каждое ребро представляется парой инцидентных ему вершин. Это представление можно реализовать двумя массивами (или одним двумерным):

x = (x0, x1, ..., xm ) и y = (y0, y1, ..., ym ),

где m –– количество ребер в графе. Каждый элемент в массиве есть метка вершины, а i ребро графа выходит из вершины xi и входит в вершину yi. Объем занимаемой памяти составляет в этом случае 2m единиц памяти. Неудобством является большое число шагов, необходимое для получения множества вершин, к которым ведут ребра из данной вершины.

1.2.5. Списки смежных вершин графа

Граф может быть однозначно представлен структурой смежности своих вершин. Структура смежности состоит из списков Adj [x] вершин графа, смежных с вершиной x. Списки Adj [x] составляются для каждой вершины графа. Структура смежности удобно реализуется массивом из n (число вершин в графе)
линейно связанных списков (1.1, а–г). Каждый список содержит


а д



1

2

3

4

5







1

2

3

4

5

1

0

1

1

0

1




1

0

1

1

0

0

2

1

0

1

0

0




2

0

0

0

0

0

3

1

1

0

1

1




3

0

0

0

0

0

4

0

0

1

0

1




4

1

1

0

0

0

5

1

0

1

1

0




5

0

0

0

1

0

б е



Ѕ

1/3

1/5

2/3

3/4

3/5

4/5







Ѕ

1/3

4/1

4/2

5/4

1

1

1

1

0

0

0

0




1

1

1

-1

0

0

2

1

0

0

1

0

0

0




2

-1

0

0

-1

0

3

0

1

0

1

1

1

0




3

0

-1

0

0

0

4

0

0

0

0

1

0

1




4

0

0

1

1

-1

5

0

0

1

0

0

1

1




5

0

0

0

0

1

в ж



г з

Рис. 1.1

вершины, смежные с вершиной, для которой составляется список. Список смежных вершин графа дает компактное представление для разреженных графов – тех, у которых множество ребер много меньше множества вершин. Недостаток этого представления таков: если мы хотим узнать, есть ли в графе ребро (x, y), приходится просматривать весь список Adj [x] в поисках y. Объем требуемой памяти составляет для ориентированных n+ m и n+2m для неориентированных графов единиц памяти, где n – число вершин графа, а m – число ребер (дуг) графа. Если в основе алгоритма решения задачи лежат операции добавления и удаления вершин из списков, то хранение списков смежности удобно реализовать, используя связанное представление списков (1.1, д–з).

1.3. Обход графа

Обход графа – это некоторое систематическое прохождение его вершин (и/или ребер). Обходя граф, мы двигаемся по ребрам (дугам) и проходим все вершины. При этом можно получить много информации, которая необходима для дальнейшей обработки графа, поэтому обход графа – основа многих алгоритмов исследования структуры графа. Если при посещении вершины структура графа не меняется, то наиболее полезны два основные способа обхода: обход в глубину и обход в ширину.

1.3.1. Обход (или поиск) в глубину

Пусть задан граф и фиксирована начальная вершина s (исходный граф может быть неориентированным или ориентированным). Стратегия поиска в глубину состоит в том, чтобы, начиная с начальной вершины, идти «вглубь», пока это возможно (есть не пройденные исходящие ребра), и возвращаться и искать другой путь, когда таких ребер нет. Так делается, пока не обнаружены все вершины, достижимые из исходной. Если после этого остаются необнаруженные вершины, выбирается одна из них (как начальная) и процесс повторяется. Так делать до тех пор, пока мы не обнаружим все вершины графа.

Когда при поиске мы впервые обнаружим вершину v, смежную с вершиной u, необходимо отметить это событие. Алгоритм поиска в глубину использует для этого цвета (метки) вершин. Каждая из вершин вначале белая (не пройденная). Будучи обнаруженной, она становится серой. Когда вершина будет полностью обработана (т.е. когда список смежных с ней вершин будет просмотрен), она станет черной. Таким образом, в процессе поиска из графа выделяется часть – «дерево поиска в глубину» или несколько деревьев (лес поиска в глубину), если поиск повторяется из нескольких вершин. Каждая вершина попадает ровно в одно дерево поиска в глубину, так что эти деревья не пересекаются. Кроме этого можно ставить дополнительные метки на вершинах дерева: метку, когда вершина была обнаружена (сделалась серой), и метку, когда была закончена обработка списка смежных с u вершин (и u стала черной).

Приведенный ниже алгоритм использует представление графа списками смежных вершин Adj [u]. Для каждой вершины u графа дополнительно хранятся ее цвет Mark[u] и ее предшественник Pr[u]. Если предшественника нет (например, если u = s или u еще не обнаружена), то Pr[u] = nil. Кроме того, в d [u] и
f [u] записываются дополнительные для u метки: метки времени. В d [u] записывается время, когда вершина u была обнаружена (и стала серой), а в f [u] записывается время, когда была закончена обработка списка смежных с u вершин (и u стала черной). В приводимом ниже алгоритме метки времени d [u] и
f [u] это целые числа от 1 до 2| |; для любой вершины u выполнено неравенство: d [u] < f [u]. Вершина u будет белой до момента d [u], серой между d [u] и f [u] и черной после f [u]. Алгоритм использует рекурсию для просмотра всех смежных с
u вершин.
Поиск_в_глубину (G)

1 {

2 for ( каждая вершина u V[G] )

3 { Mark [u]?БЕЛЫЙ;

4 Pr [u] ?nil;

5 }

6 time ?0;

7 for ( каждая вершина s V[G] )

8 if (Mark [u] = БЕЛЫЙ) Search (s);

9 }

Search (u)

1 {

2 Mark [u] ?СЕРЫЙ;

3 d [u] ?time?time+1;

4 for (каждая v Adj [u])

5 { if (Mark [v] = БЕЛЫЙ)

6 { Pr [v] ?u; Search (v); }

7 }

8 Mark [u] ?ЧЕРНЫЙ;

9 f [u] ? time?time+1;

10 }
Алгоритм начинается с того, что сначала (строки 2–5) все вершины красятся в белый цвет (помечаются как не пройденные); в поле Pr помещается nil (пока у вершин нет предшественника). Затем (строка 6) устанавливается начальное (нулевое) время (переменная time – глобальная переменная). Для всех вершин (строки 7–8), которые все еще остались не пройденными (белыми), вызывается процедура Search. Эти вершины становятся корнями деревьев поиска в глубину.

В момент вызова Search (u) вершина u – белая. В процедуре Search она сразу же становится серой (строка 2). Время ее обнаружения (строка 3) заносится в d[u] (счетчик времени перед этим увеличился на единицу). Затем просматриваются (строки 4–7) смежные с u вершины; процедура Search вызывается для тех из них, которые оказываются белыми к моменту вызова. После просмотра всех смежных с u вершин саму вершину u делаем черной и записываем в f [u] время этого события.
  1   2   3   4   5   6   7   8   9


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации