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

Задание 1: Найти кратчайший путь на графе между тремя парами вершин методом динамического программирования

Варианты Граф

1, 13

2, 14

3, 15

4, 16

5, 17, 25

6, 18

7, 19

8, 20

9; 21

10; 22

11; 23

12; 24

Задание 2: Найти кратчайший путь между тремя парами вершин методом Дейкстры

1; 24

2; 23

3; 22

4; 21

5; 20

6; 19

7; 18

8; 17

9; 16

10; 15; 25

11; 14

12; 13

Решить задачи

Задание 1.Дана карта автомобильных дорог. Найти кратчайший путь, учитывая длины дорог, из Ярославля до Новосибирска. Использовать только те города, которые отмечены флажком. Совпадет ли кратчайший маршрут, если не брать во внимание длины дорог?

Задание 2.Дана карта Европы. Турагенству необходимо найти кратчайший туристический маршрут между произвольно выбранными странами Европы.

Задание 4.На участке 3 дома и 3 колодца. От каждого дома к каждому колодцу ведет тропинка. Когда владельцы домов поссорились, они задумали проложить дорогу от каждого дома к каждому колодцу так, чтобы не встречаться на пути к колодцам. Может ли осуществиться их намерение?

Составить программу для нахождения кратчайшего пути

Вариант 1. Путь из 1 в 9

Вариант 3. Путь из 1 в 9

Вариант 2. Путь из 2 в 5

Вариант 4. Путь из 2 в 5

Вариант 5. Путь из 2 в 7

Вариант 8. Путь из 2 в 9

Вариант 6. Путь из 1 в 7

Вариант 9. Путь из 1 в 5

Вариант 7. Путь из 4 в 1

Вариант 10. Путь из 1 в 3

Вариант 11. Путь из 2 в 7

Вариант 14. Путь из 2 в 9

Вариант 12. Путь из 1 в 7

Вариант 15. Путь из 1 в 5

Вариант 13. Путь из 4 в 1

Вариант 16. Путь из 1 в 3

Вариант 17. Путь из 2 в 7

Вариант 20. Путь из 2 в 9

Вариант 18. Путь из 1 в 7

Вариант 21. Путь из 1 в 5

Вариант 19. Путь из 4 в 1

Вариант 22. Путь из 1 в 3

Вариант 23. Путь из 1 в 9

Вариант 25. Путь из 1 в 9

Вариант 24. Путь из 2 в 5

Вариант 26. Путь из 2 в 5

Лабораторная работа № 6 « Эвристические алгоритмы »

Цель работы:ознакомление с эвристическими алгоритмами и методикой оценки их эффективности .

Продолжительность работы:- 2 часа.

Теоретические сведения

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

К эвристическим алгоритмам относятся : волновой , двухлучевой , четырехлучевой , маршрутный, алгоритмы составления расписания.