Главная | Обратная связь

Лабораторная работа 2.

Задача выбора пути.

Постановка задачи.

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

2.Задание к выполнению лабораторной работы:

2.1 Нарисовать схему транспортной сети.

2.2. Решить методом динамического программирования выполнив обратный проход, от последнего пункта к первому.

2.3. Решить методом динамического программирования выполнив обратный проход, от первого пункта к. последнему.

2.4. Сравнить полученные результаты.

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

Вариант1.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		5-11		10-14
1-3		6-9		11-16
1-4		7-10		12-19
1-5		8-11		13-18
2-6		9-13		14-19
2-8		9-15		12-17
3-7		10-12		18-19
4-8		11-15		16-19
		15-17		17-19

 

Вариант2.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		4-7		5-8
1-3		4-8		5-12
1-4		2-9		6-7
1-5		3-6		6-9
7-8		9-13		11-13
7-10		10-11		11-14
8-12		10-13		12-14
9-10		7-13		13-14

 

Вариант3.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		2-10		6-8
1-3		3-6		8-10
1-4		4-7		7-9
1-5		5-9		9-10

 

Вариант4.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		2-5		5-9
1-3		3-6		6-9
1-4		4-8		7-9
4-7		6-8		8-9

 

Вариант5.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		6-9
1-3		7-8
1-4		7-10
1-5		8-12
2-9		9-13
3-6		10-11
4-7		10-13
5-8		11-14
5-12		12-14
6-7		13-14

 

Вариант6.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		3-7		9-10
1-3		3-9		13-17
1-4		3-12		14-18
1-5		4-8		15-19
2-6		4-7		16-19
2-9		4-10		17-18
2-14		5-9		18-19
6-10		7-15		11-14
10-13		8-11		12-16

 

Вариант7.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		5-11		10-14
1-3		6-9		11-16
1-4		7-10		12-19
1-5		8-11		13-18
2-6		9-13		14-19
2-7		9-15		12-17
3-7		10-12		18-19
4-8		11-15		16-19
		15-17		17-19

 

Вариант8.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		4-7		5-8
1-3		4-5		5-10
1-4		2-9		6-7
1-5		3-6		6-9
7-8		9-13		11-13
7-10		10-11		11-14
8-12		10-13		12-14
9-10		7-13		13-14

 

Вариант9.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		2-10		6-8
1-3		3-6		8-10
1-4		4-7		7-9
1-5		5-9		9-10

 

Вариант10.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		2-5		5-9
1-3		3-6		6-9
1-4		4-8		7-9
4-7		6-8		8-9

 

Вариант11.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		6-9
1-3		7-8
1-4		7-10
1-5		8-12
2-9		9-13
3-6		10-11
4-7		10-13
5-8		11-14
5-12		12-14
6-7		13-14

 

Вариант12.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		3-7		9-10
1-3		3-9		13-17
1-4		3-8		14-18
1-5		4-8		15-19
2-6		4-16		16-19
2-9		4-9		17-18
2-4		5-9		18-19
6-10		7-15		11-14
10-13		8-11		12-16

 

Вариант13.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		5-11		10-14
1-3		6-9		11-16
1-4		7-10		12-19
1-5		8-11		13-18
2-6		9-13		14-19
2-9		9-15		12-17
3-7		10-12		18-19
4-8		11-15		16-19
		15-17		17-19

 

Вариант14.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		4-7		5-8
1-3		4-8		5-12
1-4		2-9		6-7
1-5		3-6		6-9
7-8		9-13		11-13
7-10		10-11		11-14
8-12		10-13		12-14
9-10		7-13		13-14

 

Вариант15.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		2-10		6-8
1-3		3-6		8-10
1-4		4-7		7-9
1-5		5-9		9-10

Вариант16.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		2-5		5-9
1-3		3-6		6-9
1-4		4-8		7-9
4-7		6-8		8-9

 

Вариант17.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
пунктов	км.	Пунктов	Км.
1-2		6-9
1-3		7-8
1-4		7-10
1-5		8-12
2-9		9-13
3-6		10-11
4-7		10-13
5-8		11-14
5-12		12-14
6-7		13-14

 

Вариант18.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		4-7		5-8
1-3		4-8		5-12
1-4		2-9		6-7
1-5		3-6		6-9
7-8		9-13		11-13
7-10		10-11		11-14
8-12		10-13		12-14
9-10		7-13		13-14

 

Вариант19.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		2-10		6-8
1-3		3-6		8-10
1-4		4-7		7-9
1-5		5-9		9-10

 

Вариант20.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		2-5		5-9
1-3		3-6		6-9
1-4		4-8		7-9
4-7		6-8		8-9

 

Вариант21.

Последовательность пунктов	Расстояние	Последовательность пунктов	Расстояние
1-2		6-9
1-3		7-8
1-4		7-10
1-5		8-12
2-9		9-13
3-6		10-11
4-7		10-13
5-8		11-14
5-10		12-14
6-7		13-14