Roozbeh Shad
Graduate student
Email: Rouzbeh_shad@yahoo.com

Hamid Ebadi
Assistant professor
Email: ebadi@kntu.ac.ir

Mohsen Ghods
Graduate student
Email: mohsen59ghods@yahoo.com

Dept of Geodesy and Geomatics Eng. K.N.Toosi University of Technology
No 1346, Mirdamad cross, Valiasr st., Tehran, IRAN
Fax (21) 877 9476

Оценка методов нахождения путей в среде ГИС

Evaluation of Route Finding Methods in GIS Application

Источник:
  gisdevelopment.net/technology/gis/ma03202pf.htm

Данная статья переведена на русский язык частично. Полную версию на английском языке можно найти в библиотеке или по адресу источника.

1.Введение

С развитием технологий географических информационных систем (ГИС) анализ сетевых транспортировок с применением этих систем стал обычным явлением во многих прикладных областях. Ключевой проблемой в анализе транспортной сети является вычисление кратчайших путей между различными пунктами в сети. Иногда это вычисление должно быть сделано в режиме реального времени. В некоторых случаях наиболее быстрый маршрут должен быть определен за несколько секунд, чтобы гарантировать безопасность пациента. Кроме того, когда речь идет о создании больших реальных транспортных сетей, вычисление кратчайших путей может быть очень интенсивным. Т.к. во многих случаях речь идет о реальных транспортных сетях и поскольку вычисление самого быстрого маршрута (кратчайшего пути) требует ответа в реальном времени, возникает естественный вопрос: какой алгоритм нахождения кратчайшего пути выполняется наиболее быстро в реальных транспортных сетях.

Хотя значительные эмпирические исследования алгоритмов кратчайшего пути были проведены ранее, нет ясного ответа, какой алгоритм или группа алгоритмов работает быстрее всего на реальных транспортных сетях [1]. В нашем исследовании были рассмотрены три алгоритма нахождения кратчайшего пути с точки зрения скорости их выполнения на реальных транспортных сетях. Этими тремя алгоритмами являются: алгоритм Дейкстры, Эвристический алгоритм и Генетический алгоритм. По результатам исследований в этой статье рассматриваются и подводятся итоги по этим трем алгоритмам, а также описываются стратегии выполнения этих алгоритмов.

2.Теория графов

В теории графов сеть представляется в виде направленного графа G=(N,A), включающий в себя набор N узлов и набор A дуг с соответствующими численными значениями: число узлов n=|N|, число дуг m=|A| и длина каждой дуги, соединяющей i-тый и j-тый узлы, обозначаемая как l(i,j). Задача кратчайшего пути может быть сформулирована следующим образом: дана сеть, найти кратчайшее расстояние (наименьшие затраты) от начального узла ко всем остальным узлам или к выборке узлов сети [2]. Эти кратчайшие пути представляются направленным деревом Т, начинающегося от исходного узла j с характеристикой, что этот уникальный путь от S до любого узла і сети является кратчайшим путем до данного узла. Длина кратчайшего пути от S к любому узлу і обозначается как d(i). Это направленное дерево называется деревом кратчайшего пути. Для любой сети с n узлами можно получить n различных деревьев кратчайшего пути. Кратчайшие пути от одной (исходной) точки до всех других точек сети обычно относят к кратчайшим путям типа «от одного ко всем». Кратчайшие пути от одного исходного узла к выборке узлов называют кратчайшими путями типа «от одного к нескольким». Кратчайшие пути от каждого узла к каждому другому узлу сети обычно называют кратчайшими путями типа «от всех ко всем» (задача расположения узлов).

3. Важные параметры в алгоритмах нахождения кратчайших путей

3.1 Представление сети

Способ, которым представляется и реализовывается исходная сеть в алгоритме кратчайшего пути, очень важен для выполнения алгоритма. Есть несколько непосредственных способов представления общей сети для вычислительных целей. Предыдущие исследования показали, что представление Forward Star – самая эффективная структура данных для представления сетей. В данной структуре данных используется два набора множеств. Первое множество используется для хранения данных о дугах, второе множество используется для хранения данных об узлах. Все дуги сети располагаются в списке и рассматриваются в определенной последовательности. Т.е. дуги, исходящие из узлов 1, 2, 3, … рассматриваются в таком же порядке. Дуги, исходящие их одного и того же узла, рассматриваются в произвольном порядке. Вся информация о дуге, такая как начальный узел, конечной узел, стоимость, длина дуги и пропускная способность, связана с дугой определенным образом (например, связанными массивами или связанными списками).

3.2 Процесс маркировки

Процесс маркировки является главной процедурой в алгоритме кратчайшего пути. Итог процесса маркировки – дерево, исходящее от начального узла к набору узлов. Это дерево строится постепенно, и кратчайший пуль от S к і получается в конце работы процесса. Три вида информации обрабатывается для каждого узла i в процессе маркировки во время построения кратчайшего пути: метка расстояния d(i), родительский узел p(i) и статус узла S(i). Метка расстояния (d(i)) хранит последнее расстояние кратчайшего пути от S до i в текущей итерации. После завершения алгоритма d(i) представляет собой кратчайший путь от S до i. Родительский узел p(i) содержит запись об узле, который предшествует узлу i в выходящем дереве. Статус узла S(i)может быть одним из таких вариантов: необработанный, временно помеченный и постоянно помеченный. Если узел не был рассмотрен в ходе итерации, он необработанный. Обычно метка расстояния до необработанного узла устанавливается равной плюс бесконечности. Если известно, что на данный момент найденный самый короткий путь к узлу і является также абсолютно точно кратчайшим путем, который вообще можно найти, узел называют постоянно помеченным. Если дальнейшие итерации еще могут привести к нахождению кратчайшего пути к узлу і, узел і считаестя временно помеченным. Из этого следует, что d(i) содержит кратчайшее расстояние к узлу і, если узел временно помечен, и d(i) содержит окончательную и оптимальную длину кратчайшего маршрута, если узел помечен постоянным.

3.3 Правила выбора и структура данных

Работа конкретного алгоритма кратчайшего пути зависит частично от того, как осуществляются основные действия в процессе маркировки. Для выполнения алгоритма кратчайшего пути особенно важны два аспекта: 1). Метод выбора следующего временно помеченного узла, с которым предстоит работать; 2). Структура данных для оптимального хранения набора помеченных узлов [2].

Традиционно используемые методы выбора следующего временно помеченного узла – это FIFO (first-in-first-out) – узел, первый вошедший в набор временно помеченных узлов, выбирается первым для работы; LIFO (last-in-first-out) – узел, вошедший последним в список временно помеченных узлов, выбирается первым для работы; BFS (best-first-search) – метка минимального расстояния из набора временно помеченных меток берется как лучшая (выбирается тот узел, которому соответствует метка с минимальным расстоянием).

Для управления набором временно помеченных точек в реализации этих методов может быть использовано несколько структур данных: массивы, одно- и двусвязные списки, стеки, упорядоченные множества, стеки, очереди, ведра и т.д.

5.Анализ результатов работы

Мы исследовали 4 алгоритма кратчайшего пути в условиях реальных транспортных сетей. В нашей работе мы использовали 6 реальных транспортных сетей для оценки алгоритмов кратчайшего пути. Эти 6 сетей включают в себя Схему транспортных сетей Ирана, которая представлена в масштабах 1:25000 и 1:250000. уровень транспортных сетей включает транспортные сети низкой детализации и транспортные сети высокой детализации. Сети низкой детализации состоят из двух видов дорог: автострады и шоссе. Сети высокой детализации состоят из Асфальтовой дороги 1, Асфальтовой дороги 2, Асфальтовой дороги 3 и Грунтовой дороги. Сети были занесены и обработаны в ArcViewGIS, действующей на рабочей станции Pentium 4 (RAM 280 Mb, CPU 1800 MHz) в среде Windows NT. Топологические отношения и длины дуг были определены в Arc/Info и конвертированы в формат ArcView. До и после определения топологии мы сделали эти документы в готовой стадии для работы ГИС для всех слоев и отредактировали и устранили те ошибки, которые искажали данные в слоях. 4 алгоритма были написаны на языках программирования Visual Basic, Visual C++, MapObject. Программы разрабатывались для нахождения группы кратчайших путей типа «от одного к одному», «от одного ко всем» и «от всех ко всем».

Алгоритмы были реализованы, используя данные с различным числом узлов и связей. В таблицах 1-3 показано время выполнения алгоритмов.

Из таблицы 1 ясно, что:

1. при условии «от одного к одному» при числе точек до 2000 определили, что время выполнения алгоритмов располагается так: Dijkstra < DKD < Graph Growth < Genetic. Т.е. в данном случае мы предлагаем применять алгоритм Дейкстры.
2. при условии «от одного к одному» при числе точек более или равном 2000 определили, что время выполнения алгоритмов располагается так: DKD < Graph Growth < Dijkstra. Т.е. в данном случае мы предлагаем применять алгоритм DKD.

Из таблицы 2 ясно, что:

1. при условии «от одного ко всем» при числе точек до 500 определили, что время выполнения алгоритмов располагается так: Genetic < Dijkstra < Graph Growth < DKD. Т.е. в данном случае мы предлагаем применять Генетический алгоритм.
2. при условии «от одного ко всем» при числе точек 500 < N < 2000 определили, что время выполнения алгоритмов располагается так: Dijkstra < Graph Growth < DKD < Genetic. Т.е. в данном случае мы предлагаем применять алгоритм Дейкстры.
3. при условии «от одного ко всем» при числе точек более или равном 2000 определили, что время выполнения алгоритмов располагается так: Graph Growth < DKD < Genetic < Dijkstra. Т.е. в данном случае мы предлагаем применять Graph Growth алгоритм.

Из таблицы 3 ясно, что:

1. при условии «от всех ко всем» при числе точек до 2000 определили, что время выполнения алгоритмов располагается так: Genetic < Graph Growth < DKD <Dijkstra Т.е. в данном случае мы предлагаем применять Генетический алгоритм.
2. при условии «от всех ко всем» при числе точек более или равном 2000 определили, что время выполнения алгоритмов располагается так:Graph Growth < DKD < Genetic < Dijkstra. Т.е. в данном случае мы предлагаем применять Graph Growth алгоритм.

6. Заключение

В последние годы произошел рост популярности анализа решений, связанного с транспортированием, в среде ГИС. В таком типе анализа вычисление кратчайших путей часто является центральной задачей, т.к. длины кратчайших путей часто необходимы как исходные данные для «высокоуровневых» моделей во многих задачах анализа транспортировок. Кроме того, проблема кратчайшего пути обычно охватывает существенные элементы более сложных задач анализа транспорта. С развитием ГИС-технологий и доступностью высококачественных данных о транспортной сети есть возможность выполнить анализ транспортировки внутри ГИС-среды. Иногда такой тип анализа должен быть выполнен в режиме реального времени. Как следствие, эти задачи анализа требуют высокой производительности алгоритмов кратчайшего пути, которые работают наиболее быстро на реальных транспортных сетях.

Хотя ранее было выполнено исследование, о котором сообщалось, по оценке работы алгоритмов кратчайшего пути в литературе не было ясного ответа, какой алгоритм или группа алгоритмов работает наиболее быстро на реальных транспортных сетях. Наша оценка четырех алгоритмов кратчайшего пути с использованием реальных транспортных сетей определила:

1. время выполнения упомянутых алгоритмов зависит от условий задачи и числа узлов в реальных транспортных сетях;
   
2. когда число узлов и сложность задачи увеличиваются, Эвристический метод работает лучше, чем другие;
   
3. Для небольшого числа узлов и сложных условий задачи Метаэвристический метод (Генетический алгоритм) работает лучше, чем другие;
   
4. Для небольшого чиста узлов и легких условий задачи алгоритм Дейкстры применять выгоднее, чем другие.
   

7. Перечень ссылок

1. Cherkassky, B. V., Goldberg, A. V., and Radzik, T. (1993) Shortest Paths Algorithms: Theory and Experimental Evaluation. Technical Report 93-1480, Computer Science Department, Stanford University
2. Ahuja, R. K., Magnanti, T. L., and Orlin, J. B.(1993) Network Flows: Theory, Algorithms and Applications. Englewood Cliffs, NJ: Prentice Hall.