Составление алгоритма поиска кротчайшего пути.

Цель работы: изучение алгоритмов поиска кратчайших путей на графах и составление алгоритма на языке высокого уровня.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

2.1 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Так на рисунке 5 последовательности дуг μ₁= { a₆, a₅, a₉, a₈, a₄ }, μ₂= { a₁, a₆, a₅, a₉ }, μ₃= { a₁, a₆, a₅, a₉, a₁₀, a₆, a₄ } являются путями.

Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например, приведенные выше пути μ₁ и μ₂ являются орцепями, а путь μ₃ не является таким, поскольку дуга a₆ в нем используется дважды.

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

Таким образом, маршрут есть последовательность ребер a₁, a₂,..., a_q, в которой каждое ребро a_i, за исключением, возможно, первого и последнего ребер, связано с ребрами a_i-1 и a_i+1 своими двумя концевыми вершинами.

Последовательности дуг на рисунке 6

μ₄= { a₂, a₄, a₈, a₁₀ }, μ₅= { a₂, a₇, a₈, a₄, a₃ } и μ₆= { a₁₀, a₇, a₄, a₈, a₇, a₂ }

являются маршрутами.

Контуром (простой цепью) называется такой путь (маршрут), в котором каждая вершина используется не более одного раза. Например, путь μ₂ является контуром, а пути μ₁ и μ₃ - нет. Очевидно, что контур является также цепью, но обратное утверждение неверно. Например, путь μ₁ является цепью, но не контуром, путь μ₂ является цепью и контуром, а путь μ₃ не является ни цепью, ни контуром.

Аналогично определяется простая цепь в неориентированных графах. Так, например, маршрут μ₄ есть простая цепь, маршрут μ₅ - цепь, а маршрут μ₆ не является цепью.

Путь или маршрут можно изображать также последовательностью вершин. Например, путь μ₁ можно представить также: μ₁ ={ x₂, x₅, x₄, x₃, x₅, x₆ } и такое представление часто оказывается более полезным в тех случаях, когда осуществляется поиск контуров или простых цепей.

Иногда дугам графа G сопоставляются (приписываются) числа - дуге (x_i, x_j) ставится в соответствие некоторое число c_ij, называемое весом, или длиной, или стоимостью (ценой) дуги. Тогда граф G называется взвешенным. Иногда веса (числа v_i) приписываются вершинам x_i графа.

При рассмотрении пути μ, представленного последовательностью дуг (a₁, a₂,..., a_q), за его вес (или длину, или стоимость) принимается число L (µ), равное сумме весов всех дуг, входящих в μ, т. е.

(2)

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

Длиной (или мощностью) пути и называется число дуг, входящих в него.

 

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ

Пусть дан граф G= (X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей С = [ с_ij ]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины (истока) s до заданной конечной вершины (стока) t, при условии, что такой путь существует:

Найти µ (s,t) при L (µ)® min, s,t Î Х, t Î R (s),

где R (s) - множество, достижимое из вершины s.

В общем случае элементы с_ij матрицы весов С могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с суммарным отрицательным весом. Отсюда следует, что дуги (ребра) графа G не должны иметь отрицательные веса.

Почти все методы, позволяющие решить задачу о кратчайшем (s-t)-пути, дают также (в процессе решения) и все кратчайшие пути от s к x_i (" x_i Î Х). Таким образом, они позволяют решить задачу с небольшими дополнительными вычислительными затратами.

Допускается, что матрица весов С не удовлетворяет условию треугольника, т. е. не обязательно с_ij £ с_ik + с_kj для всех i, j и k.

Если в графе G дуга (x_i, x_j) отсутствует, то ее вес полагается равным ¥.

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

Существует множество методов решения данной задачи, отличающиеся областью применимости и трудоемкостью (Дейкстры, Флойда, динамического программирования). Среди них большое распространение получили частные алгоритмы, применяющиеся при решении частных задач, и имеющие меньшую трудоемкость. Эти частные случаи встречаются на практике довольно часто (например, когда с_ij являются расстояниями), так что рассмотрение этих специальных алгоритмов оправдано.

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

Отчет о выполнении

Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.

Текст задачи

Листинг алгоритма исполняемого файла

Скриншот интерфейса запускного файла программы

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

1. Что такое граф?

2. Основные понятия и определения.

3. Описать задачу о кротчайшем пути.

4. Объяснить алгоритм решения на языке высокого уровня

 

Перечень литературы:

1. Теория алгоритмов: учебник / Д.Ш. Матрос, Г.Б. Поднебесова. – М.: БИНОМ.Лаборатория знаний, 2008. – 202 с.: ил. – (Педагогическое образование).
2. Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы: Учебное пособие. — М.: Издательство ЛКИ, 2008. — 216 с.
3. Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. — 2-е изд., стер. — М.: Издательский центр «Академия», 2008. — 448
4. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов / В. И. Игошин. — 3-е изд., стер. — М.: Издательский центр «Академия», 2007. — 304 с.

Дополнительная литература:

1. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений. – М.: Академия, 2007. - 304 с.
2. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008. - 448 с.
3. Колмогоров А.Н., Драгалин А.Г. Математическая логика. – М.: КомКнига, 2006. - 240 с.
4. Колмогоров А.Н., Драгалин А.Г. Математическая логика. – М.: КомКнига, 2006. - 240 с.
5. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, 1999. - 288 с.
6. Тимофеева И.Л. Математическая логика в вопросах и задачах. Учебное пособие для студентов математических факультетов педвузов. – М.: Прометей, 2002. - 112 с.
7. Тимофеева И.Л. Математическая логика. Курс лекций. Часть 1. – М.: Прометей, 2003. - 144 с.
8. Тимофеева И.Л. Математическая логика. Курс лекций. Часть 2. – М.: Прометей, 2003. - 164 с.

Интернет ресурсы

1. http://mmf.nsu.ru/sites/default/files/AlgorithmsKogabaev.pdf
2. http://230101.ru/teor_algor/lect_t_a.htm
3. http://ap-economics.narod.ru/info/algoritms.pdf
4. http://any-book.org/download/68890.html
5. http://discopal.ispras.ru/ru.book-advanced-algorithms.htm
6. http://www.coolreferat.com/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2
7. http://rutracker.org/forum/viewtopic.php?t=3025567
8. http://logic.pdmi.ras.ru/
   http://infologos.narod.ru/
9. www.4tivo.com/education/; www.matburo.ru/literat.php;www.plib.ru; http://nehudlit.ru; www.gaudeamus.omskcity.com; www.alleng.ru; www.symplex.ru; www.math.ru.
10. http://agpi.itech.ru/.

 

Задания для дополнительного изучения

ЗАДАНИЕ 1. Изучить и реализовать следующие сортировки:

1. Простой вставкой.

2. Пузырьковая сортировка.

3. Простым выбором.

4. Пирамидальная сортировка.

5. Быстрая рекурсивная сортировка.

6. Быстрая сортировка с использованием стека.

7. Файловая сортировка естественным слиянием.

 

ВАРИАНТЫ ДОМАШНИХ ЗАДАНИЙ

ВАРИАНТ 1. “Карманная” сортировка [2]

ВАРИАНТ 2. Поразрядная сортировка [2]

ВАРИАНТ 3. Сортировка Шелла. [2]

ВАРИАНТ 4. Сортировка двухпутевым слиянием [3].

ВАРИАНТ 5. Сортировка связных списков слиянием сверху вниз[3].

ВАРИАНТ 6. Восходящая сортировка связных списков слиянием [3].

ВАРИАНТ 7. Быстрая сортировка с разделением на три части[3].

ВАРИАНТ 8. Индексная сортировка [3]

ВАРИАНТ 9. Сортировка бинарными включениями.[1].

ВАРИАНТ 10.Шейкер-сортировка [1].

ВАРИАНТ 11.Сортировка связных списков [3]

ВАРИАНТ 12. Метод распределяющего подсчета [3].

ВАРИАНТ 13.Метод разделения с вычислением медианы трех элементов [3].

ВАРИАНТ 14.Поразрядная сортировка [3].