3.2. Методы расчета расстояний на сети

Методы, рассмотренные в предыдущем пункте, можно использовать для расчета расстояний как для пары объектов, так и внутри целого множества объектов. Результатом таких расчетов является матрица расстояний между объектами.

Рассматриваемые в данном пункте методы расчета расстояний на сети позволяют учесть все вышеперечисленные факторы и обеспечить высокую точность расчетов. Можно с уверенностью утверждать, что точность расчетов на сети напрямую зависит от точности расчетов на отдельных участках сети.

Результатом расчетов расстояний являются две матрицы – матрица расстояний и матрица указателей. Для разъяснения сущности и назначения второй матрицы рассмотрим следующий пример. Пример

Рассмотрим транспортную сеть, которая состоит из девяти пунктов. Расстояний между пунктами представлены на рисунке 3.7, а под ним приведены матрица расстояний и матрица указателей.

Представим, что схема транспортной сети – это карта, на которой в одном из пунктов располагается игральная фишка, например, в пункте A. Необходимо передвинуть фишку из пункта 1 в пункт 7. Поставим два вопроса:

1) Какой путь должна пройти фишка?

2) Какой маршрут для фишки является оптимальным?

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

Расстояние от пункта 1 до пункта 7 находится из матрицы расстояний – это ячейка, которая располагается на пересечении строки 1 и столбца 7. Расстояние это составляет 31 км.

Для поиска оптимального маршрута используется матрица указателей. Находим ячейку на пересечении строки 1 и столбца 7. В найденной ячейке указан пункт 3. Перемещаем фишку в пункт 3 и ставим новый вопрос: как добраться из пункта 3 в пункт 7? Находим ячейку на пересечении строки 3 и столбца 7, где указан новый пункт 8. Перемещаем фишку в пункт 8 и формулируем вопрос: как добраться из пункта 8 в пункт 7? На пересечении строки 8 и столбца 7 указан пункт 6. Перемещаем фишку в пункт 6. На пересечении строки 6 и столбца 7 стоит число 7. Перемещаем фишку в пункт 7. Оптимальный маршрут найден: 1 – 3 – 8 – 6 – 7.

Протяженность оптимального маршрута определяется как сумма длины отдельных участков маршрута, например:

d(1,7) = d(1,3) + d(3,8) + d(8,6) + d(6,7) = 9 + 7 + 8 + 7 = 31 км.

Следует отметить, что матрица указателей носит только вспомогательный характер.

Используя рисунок, постарайтесь самостоятельно составить матрицу расстояний и указателей. Используйте для расчетов калькулятор. В конце сравните полученный Вами результат с данными матрицы расстояний и указателей, представленных в табл. 3.6 и 3.7.

Когда Вы выполните задание, то Вы убедитесь, что составление матрицы расстояний и указателей вручную даже для такой простой сети – задача довольно сложная и трудоемкая. Поэтому для расчетов используются специальные методы, которые позволяют автоматизировать этот процесс. В данном разделе мы рассмотрим только два метода расчетов:

Ÿ метод потенциалов,

Ÿ метод «мельницы».