Тема17. Задача про розміщення школи
17.1. Завдання. Задана дорожна мережа, яка складається з дев’яти вершин, з’єднаних ребрами (див. Рис.8).
Необхідно:
побудувати матрицю найкоротших відстаней між пунктами мережі, використовуючи алгоритм Флойда, або ж метод перебору варіантів;
використовуючи дані про кількість учнів у населених пунктах (вузлах мережі), наведені у Таблиці 7, знайти оптимальне місце для розташування школи.
Рис.8. Схема дорожної мережі.
Таблиця 7. Кількість учнів у населених пунктах.
Варiант |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
40 |
50 |
70 |
45 |
30 |
25 |
20 |
55 |
35 |
2 |
50 |
70 |
45 |
30 |
25 |
20 |
55 |
35 |
40 |
3 |
70 |
45 |
30 |
25 |
20 |
55 |
35 |
40 |
50 |
4 |
45 |
30 |
25 |
20 |
55 |
35 |
40 |
50 |
70 |
5 |
30 |
25 |
20 |
55 |
35 |
40 |
50 |
70 |
45 |
6 |
25 |
20 |
55 |
35 |
40 |
50 |
70 |
45 |
30 |
7 |
20 |
55 |
35 |
40 |
50 |
70 |
45 |
30 |
25 |
8 |
55 |
35 |
40 |
50 |
70 |
45 |
30 |
25 |
20 |
9 |
35 |
40 |
50 |
70 |
45 |
30 |
25 |
20 |
55 |
10 |
40 |
70 |
35 |
45 |
20 |
55 |
25 |
50 |
30 |
11 |
70 |
35 |
45 |
20 |
55 |
25 |
50 |
30 |
40 |
12 |
35 |
45 |
20 |
55 |
25 |
50 |
30 |
40 |
70 |
13 |
45 |
20 |
55 |
25 |
50 |
30 |
40 |
70 |
35 |
14 |
20 |
55 |
25 |
50 |
30 |
40 |
70 |
35 |
45 |
15 |
55 |
25 |
50 |
30 |
40 |
70 |
35 |
45 |
20 |
16 |
25 |
50 |
30 |
40 |
70 |
35 |
45 |
20 |
55 |
17 |
50 |
30 |
40 |
70 |
35 |
45 |
20 |
55 |
25 |
18 |
30 |
40 |
70 |
35 |
45 |
20 |
55 |
25 |
50 |
19 |
40 |
55 |
25 |
45 |
70 |
35 |
50 |
30 |
20 |
20 |
55 |
25 |
45 |
70 |
35 |
50 |
30 |
20 |
40 |
21 |
25 |
45 |
70 |
35 |
50 |
30 |
20 |
40 |
55 |
22 |
45 |
70 |
35 |
50 |
30 |
20 |
40 |
55 |
25 |
23 |
70 |
35 |
50 |
30 |
20 |
40 |
55 |
25 |
45 |
24 |
35 |
50 |
30 |
20 |
40 |
55 |
25 |
45 |
70 |
25 |
50 |
30 |
20 |
40 |
55 |
25 |
45 |
70 |
35 |
26 |
30 |
20 |
40 |
55 |
25 |
45 |
70 |
35 |
50 |
27 |
20 |
40 |
55 |
25 |
45 |
70 |
35 |
50 |
30 |
28 |
55 |
70 |
20 |
30 |
50 |
45 |
40 |
35 |
25 |
29 |
70 |
20 |
30 |
50 |
45 |
40 |
35 |
25 |
55 |
30 |
20 |
30 |
50 |
45 |
40 |
35 |
25 |
55 |
70 |
31 |
30 |
50 |
45 |
40 |
35 |
25 |
55 |
70 |
20 |
32 |
50 |
45 |
40 |
35 |
25 |
55 |
70 |
20 |
30 |
33 |
45 |
40 |
35 |
25 |
55 |
70 |
20 |
30 |
50 |
34 |
40 |
35 |
25 |
55 |
70 |
20 |
30 |
50 |
45 |
35 |
35 |
25 |
55 |
70 |
20 |
30 |
50 |
45 |
40 |
36 |
25 |
55 |
70 |
20 |
30 |
50 |
45 |
40 |
35 |
37 |
70 |
55 |
30 |
20 |
45 |
50 |
35 |
40 |
25 |
38 |
55 |
30 |
20 |
45 |
50 |
35 |
40 |
25 |
70 |
39 |
30 |
20 |
45 |
50 |
35 |
40 |
25 |
70 |
55 |
40 |
20 |
45 |
50 |
35 |
40 |
25 |
70 |
55 |
30 |
41 |
45 |
50 |
35 |
40 |
25 |
70 |
55 |
30 |
20 |
42 |
50 |
35 |
40 |
25 |
70 |
55 |
30 |
20 |
45 |
43 |
35 |
40 |
25 |
70 |
55 |
30 |
20 |
45 |
50 |
44 |
40 |
25 |
70 |
55 |
30 |
20 |
45 |
50 |
35 |
45 |
25 |
70 |
55 |
30 |
20 |
45 |
50 |
35 |
40 |
46 |
70 |
20 |
35 |
25 |
30 |
50 |
55 |
45 |
40 |
47 |
20 |
35 |
25 |
30 |
50 |
55 |
45 |
40 |
70 |
48 |
35 |
25 |
30 |
50 |
55 |
45 |
40 |
70 |
20 |
49 |
25 |
30 |
50 |
55 |
45 |
40 |
70 |
20 |
35 |
50 |
30 |
50 |
55 |
45 |
40 |
70 |
20 |
35 |
25 |
17.2. Приклад розв’язування
В основу алгоритму розв’язування задачі покладене таке міркування: сума відстаней, пройдених всіма учнями по дорозі до школи повинна бути мінімальною. Доведена теорема, згідно з якою оптимальним місцем розташування школи може бути лише населений пункт. Це значно спрощує розв’язування задачі і, по суті, зводить її до задачі про побудову матриці найкоротших відстаней між вершинами графа.
Для побудови матриці найкоротших відстаней у нашому випадку можна було б дев’ять разів використати алгоритм Дейкстри. Але це не зовсім раціонально. Тому при комп’ютерних розрахунках матриці найкоротших відстаней використовують алгоритм Флойда, який набагато ефективніший. Основна частина цього алгоритму на мові Pascal має вигляд:
for k:=1 to N do
for i:=1 to N do
for j:=1 to N do
If d[i,k] + d[k,j] < d[i,j] then d[i,j] := d[i,k] + d[k,j]
Тут N – кількість вершин мережі, d[i,j] – відстань від i-ої до j-ої його вершини.
У випадку, коли кількість вершин невелика для побудови матриці найкоротших відстаней можна використати метод перебору варіантів. Розглянемо суть цього методу на прикладі мережі, зображеної на Рис.8. Матриця відстаней для мережі має наступний вигляд.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
0 |
31 |
М |
38 |
М |
М |
М |
М |
М |
2 |
31 |
0 |
24 |
М |
М |
27 |
М |
М |
М |
3 |
М |
24 |
0 |
31 |
22 |
М |
М |
М |
М |
4 |
38 |
М |
31 |
0 |
М |
М |
14 |
11 |
М |
5 |
М |
М |
22 |
М |
0 |
11 |
10 |
М |
М |
6 |
М |
27 |
М |
М |
11 |
0 |
М |
М |
22 |
7 |
М |
М |
М |
14 |
10 |
М |
0 |
27 |
М |
8 |
М |
М |
М |
11 |
М |
М |
27 |
0 |
11 |
9 |
М |
М |
М |
М |
М |
22 |
М |
11 |
0 |
Метод перебору варіантів проілюструємо на прикладі відшукання найкоротших відстаней від вершини 1 до інших вершин мережі.
Найкоротші відстані до вершин 2 і 4 дорівнюють довжинам відповідних ребер, тобто 31 і 38.
Для знаходження найкоротшої відстані до вершини 3 розглянемо два варіанти: маршрут 1 – 2 – 3 довжиною 55 і маршрут 1 – 4 – 3 довжиною 69. Вибираємо коротший, тобто 1 - 2 – 3 (довжина 55).
Для знаходження найкоротшої відстані до вершини 5 розглянемо три варіанти: маршрут 1 – 2 – 3 – 5 довжиною 77; маршрут 1 – 2 – 6 – 5 довжиною 69 і маршрут 1 – 4 – 7 – 5 довжиною 62. Вибираємо коротший, тобто 1 - 4 – 7 – 5 (довжина 62). Маршрут 1 – 4 – 3 – 5 розглядати немає змісту, оскільки вже було показано, що маршрут 1 – 2 – 3 є оптимальнішим від маршруту 1 – 4 – 3.
Найкоротший маршрут до вершини 6 наступний: 1 – 2 – 6 (довжина 58) і це очевидно.
Найкоротший маршрут до вершини 7 наступний: 1 – 4 – 7 (довжина 52) і це також очевидно.
Найкоротший маршрут до вершини 8: 1 – 4 – 8 (довжина 49).
Для знаходження найкоротшої відстані до вершини 9 розглянемо два варіанти: маршрут 1 – 2 – 6 – 9 довжиною 80 і маршрут 1 – 4 – 8 – 9 довжиною 60. Вибираємо коротший, тобто 1 – 4 – 8 – 9 (довжина 60).
Аналогічним чином аналізуємо всі інші вершини. В результаті отримуємо матрицю найкоротших відстаней у вигляді:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
к-сть учнів |
1 |
0 |
31 |
55 |
38 |
62 |
58 |
52 |
49 |
60 |
50 |
2 |
31 |
0 |
24 |
55 |
38 |
27 |
48 |
60 |
49 |
20 |
3 |
55 |
24 |
0 |
31 |
22 |
33 |
32 |
42 |
53 |
10 |
4 |
38 |
55 |
31 |
0 |
24 |
35 |
14 |
11 |
22 |
40 |
5 |
62 |
38 |
22 |
24 |
0 |
11 |
10 |
35 |
33 |
80 |
6 |
58 |
27 |
33 |
35 |
11 |
0 |
21 |
33 |
22 |
30 |
7 |
52 |
48 |
32 |
14 |
10 |
21 |
0 |
25 |
36 |
60 |
8 |
49 |
60 |
42 |
11 |
35 |
33 |
25 |
0 |
11 |
90 |
9 |
60 |
49 |
53 |
22 |
33 |
22 |
36 |
11 |
0 |
70 |
|
21120 |
19550 |
16630 |
9650 |
11430 |
11820 |
10640 |
10570 |
11840 |
|
Приєднаємо справа до таблиці ще один стовпчик, у якому розмістимо дані про кількість учнів у населених пунктах. Приєднаємо знизу до таблиці ще один рядок, у якому розмістимо суму добутків кількості учнів у населених пунктах на найкоротші відстані до цих населених пунктів. Це число буде характеризувати суму відстаней, пройдених всіма учнями, у випадку розташування школи у даному населеному пункті. Аналіз останнього рядка показує, що найвигідніше розмістити школу у четвертому населеному пункті, оскільки сума у цьому випадку буде найменшою.