Лгоритм поиска пути наименьшей длины

Пусть G=(V,Г) – произвольный ориентированный граф; v,w - вершины. Требуется найти (v-w) - путь, имеющий наименьшее число дуг.

Пункты 1-2.

Пункты 3-4.

Пункт 5.

Пункт 6.

1.2. Пример решения задачи в EXCEL с использованием «Поиск решения»

Дано:имеются n=5 узлов транспортной сети, соединенных между собой дорогами, протяженность которых представлена матрицей || d_ij|| _5´5 (где символом «_» отражено отсутствие дороги) и соответствующей ей матрицей булевых констант, отражающих возможность наличия потока между узлами:

0 2 6 8 _ 0 1 1 1 0

_ 0 3 _ 7 0 0 1 0 1

_ 5 0 1 5 и 0 1 0 1 1

_ _ 4 0 2 0 0 1 0 1

_ _ _ _ 0 0 0 0 0 0

Найти:оптимальный маршрут из узла №1 сети в узел №5, с целью минимизации суммарной его протяженности.

Решение: Для указания входящего в узел маршрута и величину выходящего из узла маршрута введем следующие обозначения:

-1 – для начального узла маршрута;

= 0 – для промежуточных узлов;

1 – для конечного узла маршрута.

Чтобы из начального узла маршрута выходил поток в один из других узлов сети:

- для 1-го узла:

.

Чтобы величина входящего потока в промежуточный узел сети была равна величине выходящего:

- для 2-го узла:

- для 3-го узла:

- для 4-го узла:

Чтобы в конечный узел маршрута входил поток из какого-нибудь другого узла:

- для 5-го узла:

Целевая функция:

где w - множество допустимых альтернатив, обусловленных ограничениями задачи.

1. Для автоматизированного расчета результатов решения задачи в ячейку А2ввести слово Расстояния, в ячейки С2:G2, B3:B7, B9:B13иB15:B19 ввести числа: 1, 2, 3, 4, 5. В ячейки С2:G7ввести числа, соответствующие протяженности соответствующих дорог, при этом отсутствие дорог будем отражаться большим числом): 0, 2, 6, 8, 1000; 1000, 0, 3, 1000, 7; 1000, 5, 0, 1, 5; 1000, 1000, 4, 0, 2; 1000, 1000, 1000, 1000, 0 и выделить их цветом и границами обрамления.

2. В ячейку А9 ввести слово Константы, в ячейки С2:G13 ввести числа, соответствующие значениям булевых констант: 0, 1, 1, 1, 0; 0, 0, 1, 0, 1; 0, 1, 0, 1, 1; 0, 0, 1, 0, 1; 0, 0, 0, 0, 0 и выделить их цветом и границами обрамления.

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

4. В ячейку А21 ввести слово Ограничения, в ячейку I15 ввести формулу соответствующую отрицательной составляющей левой части ограничений задачи для узлов: =СУММПРОИЗВ(С9:G9;С15:G15). Скопировать эту формулу в ячейки I15:I19. В ячейку С21ввести формулу соответствующую положительной составляющей левой части ограничений задачи для узлов: =СУММПРОИЗВ(С9:С13;С15:С19). Скопировать эту формулу в ячейки С21:G21. Выделить их цветом и границами обрамления.

5. Ввести дополнения в формулы ячеекС21:G21, чтобысформировать в них левую часть ограничений задачи, соответственно:

- В ячейку С21:=СУММПРОИЗВ(С9:С13;С15:С19)-I15;

- В ячейку D21:=СУММПРОИЗВ(D9:D13;D15:D19)-I16;

- В ячейку E21:=СУММПРОИЗВ(E9:E13;E15:E19)-I17;

- В ячейку F21:=СУММПРОИЗВ(F9:F13;F15:F19)-I18;

- В ячейку G21:=СУММПРОИЗВ(G9:G13;G15:G19)-I19.

6. В ячейку А23 ввести Целевая функция, в ячейку С23 ввести формулу, соответствующую выражению целевой функции задачи: СУММПРОИЗВ(С3:G7;С15:G19), выделить ячейки цветом и границами обрамления.

7. В главном меню выбрать Сервис à Поиск решения.

8. Установить целевую ячейку С23, Минимальное значение, Изменяя ячейки С15:G19.

9. Щелкнуть по кнопке Добавить и в открывшемся диалоговом окне в областиСсылка на ячейку:ввести диапазон ячеек, соответствующих переменных задачах: С15:G19, затем в выпадающем списке выбрать знак ≥, щелкнуть курсором в области Ограничение: и ввести число 0, нажать кнопку Добавить.

10. В открывшемся диалоговом окне в области Ссылка на ячейку: указать поочередно (то есть для каждой отдельно сформировать ограничение) ячейки, соответствующие диагональным элементами матрицы: С15, D16, E17, F18 и G19, в выпадающем списке выбрать знак: =, щелкнуть курсором в области Ограничение: и ввести число 0, соответствующее правой части ограничения задачи, нажать кнопку Добавить.

11. В открывшемся диалоговом окне в области Ссылка на ячейку: указать ячейку, соответствующую левой части ограничения задачи для 1-го узла: С21, в выпадающем списке выбрать знак: =, щелкнуть курсором в области Ограничение: и ввести число -1, соответствующее правой части ограничения задачи, нажать кнопку Добавить.

12. В открывшемся диалоговом окне в области Ссылка на ячейку: указать диапазон ячеек, соответствующих левой части ограничения задачи для 2-го, 3-го и 4-го узлов: =D21:F21, в выпадающем списке выбрать знак: =, щелкнуть курсором в области Ограничение: и ввести число 0, соответствующее правой части ограничения задачи, нажать кнопку Добавить.

13. В открывшемся диалоговом окне в области Ссылка на ячейку: указать ячейку, соответствующую левой части ограничения задачи для 5-го узла: G21, в выпадающем списке выбрать знак: =, щелкнуть курсором в области Ограничение: и ввести число 1, соответствующее правой части ограничения задачи, нажать кнопку ОК.

14. В диалоговом окне Поиск решения нажать кнопку Параметры, в отрывшемся диалоговом окне установить флажок Линейная модель и нажать ОК.

15. В диалоговом окне Поиск решения нажать кнопку Выполнить (в случае корректной постановки задачи автоматически будет найдено оптимальное решение задачи, о чем появится сообщение Решение найдено. Все ограничения и условие оптимальности выполнены, нажать кнопку ОК).

16. Сохранить файл с шаблоном решения.

арианты заданий

Вариант 1

Кратчайший путь от 1 к 7

Вариант 2

Кратчайший путь от 1 к 9

Вариант 3

Кратчайший путь от 1 к 8

Вариант 4

Кратчайший путь от 1 к 8

Вариант 5

Кратчайший путь от 1 к 7

Вариант 6

Кратчайший путь от 1 к 9

Вариант 7.

Кратчайший путь от 1 к 8.

Вариант 8.

Кратчайший путь от 1 к 8.

Вариант 9

Кратчайший путь от 1 к 8.

Вариант 10.

Кратчайший путь от 1 к 8.

Вариант 11.

Кратчайший путь от 1 к 9.

Вариант 12.

Кратчайший путь от 1 к 8.

Вариант 13.

Кратчайший путь от 1 к 9.

Вариант 14.

Кратчайший путь от 1 к 9.

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

1. Изобразите с помощью графа договорные отношения между предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту:

- предприятие А установило договорные отношения со всеми другими предприятиями;

- Б установило с Г и Д;

- В установило со всеми предприятиями, кроме предприятия Е.
Сколько вершин и сколько ребер имеет полученный граф?

2. Сколько ребер нужно провести чтобы достроить граф, изображенный на рис. 1 до полного?

Рис. 1. Неполный граф

3. Сколько существует путей из вершины А в вершину Д на графе рис. 20.

4. Найдите простые пути на графе рис. 1.

5. Укажите степени вершин графа на рис. 1.

6. Дайте определение изоморфного графа и укажите, какой из графов, изображенных на рис. 2, не является изоморфным с другими.

Рис. 2. Примеры графов

7. Среди графов, изображенных на рис. 2 найдите плоский граф и дайте ему определение.

8. Приведите пример нулевого графа и дайте ему определение.

9. Приведите собственный пример несвязного графа и моста на нем.

10. Между четырьмя государствами были подписаны двухсторонние договорные обязательства. Каждый договор был подписан президентами обоих договаривающихся государств. Сколько всего подписей фигурировало в договорах, если каждый договор подписывался в двух экземплярах? Укажите закономерность, которая позволяет найти число подписей.

11. Определите степени входа и выхода всех вершин ориентированного графа на рис. 3.

Рис. 3. Ориентированный граф

12. Дайте определение длины пути и найдите ее значение от вершины Д до всех остальных вершин графа, изображенного на рис. 3.

13. Дайте определения пути и цикла на графе и найдите их, если они есть на графе рис. 3.