Задача про розміщення школи
Завдання. Задана дорожна мережа, яка складається N вершин, з’єднаних ребрами. Необхідно:
побудувати матрицю найкоротших відстаней між пунктами мережі, використовуючи алгоритм Флойда, або ж метод перебору варіантів;
використовуючи дані про кількість учнів у населених пунктах (вузлах мережі), знайти оптимальне місце для розташування школи.
В основу розв’язування задачі покладене таке міркування: сума відстаней, пройдених всіма учнями по дорозі до школи повинна бути мінімальною. Доведена теорема, згідно з якою оптимальним місцем розташування школи може бути лише населений пункт. Це значно спрощує розв’язування задачі і, по суті, зводить її до задачі про побудову матриці найкоротших відстаней між вершинами графа.
Для побудови матриці найкоротших відстаней розроблені спец. алгоритми, але, якщо кількість вершин невелика то можна використати метод перебору варіантів. Ми розглянемо задачу коли ця матриця вже відома.
Приклад (рис 1.)
Задача про розміщення пожежної частини
В основу розв’язування задачі покладене наступне міркування: відстань від пожежної частини до найбільш віддаленого пункту мережі повинна бути мінімальною. Це міркування називають принципом мінімаксу, а саму задачу – мінімаксною (задачу про розміщення школи – мінісумною). Аналогічно розв’язуються задачі про розміщення станції швидкої допомоги, служби охорони, тобто тих служб, час виклику яких повинен бути мінімальним.
18.1. Завдання. Задана дорожна мережа, яка складається з п’яти вершин, з’єднаних ребрами. Рис (2) Необхідно:
розрахувати матрицю найкоротших відстаней між пунктами мережі, використовуючи метод перебору варіантів;
використовуючи побудовану матрицю, знайти оптимальний варіант розташування пожежної частини у одному з населених пунктів;
Ця задача зводиться до задачі про побудову матриці найкоротших відстаней між вершинами графа.
Нехай Матриця найкоротших відстаней має вигляд:Рис 2
|
1 |
2 |
3 |
4 |
5 |
max |
1 |
0 |
31 |
55 |
48 |
62 |
62 |
2 |
31 |
0 |
24 |
43 |
38 |
60 |
3 |
55 |
24 |
0 |
31 |
22 |
55 |
4 |
48 |
43 |
31 |
0 |
24 |
48 |
5 |
62 |
38 |
22 |
24 |
0 |
62 |
Приєднаємо до неї справа ще один стовпчик і випишемо в ньому максимальні елементи кожного рядка. Вони відповідатимуть відстані до найбільш віддаленого пункту мережі (розглядаємо найгірший варіант) у випадку розташування пожежної частини у населеному пункті, номер якого відповідає номеру рядка матриці. Вибираємо мінімальний елемент серед всіх чисел добавленого стовпця. У нашому випадку це число 48 (пункт 4).
Отже, найбільш вигідно розміщувати пожежну частину у населеному пункті. При цьому відстань до найбільш віддаленого пункту становитиме 48 кілометри.