WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 | 4 |
На станции возможна пересадка с одного маршрута на другой, если время между отправлением и прибытием на станцию S больше, либо равно минимальному времени пересадки для этой станции. Для станций расположенных близко друг к другу возможно прохождение пешком, которое описывается введением, так называемых пеших ребер между станциями. Формально, мы рассматриваем пешее ребро как элементарное соединение с, где маршрут Z, времена отправления и прибытия и не определены, но length(c) определено и равно времени пешего перехода.

Пусть – последовательность элементарных соединений (включая пешие ребра), с заданными отправлениями и прибытиями для каждого элементарного соединения,. Полагаем, что времена прибытия и отправления включают также даты прибытий и отправлений и учитывают время, прошедшее с первого дня поездки. Время, где, М – кол-во минут в сутках,. Последовательность P называется постоянным соединением от станции до станции, если удовлетворяет следующим условиям:

Наиболее известная частная задача о расписаниях называется также задачей наискорейшего прибытия. Запрос определяет станцию отправления A, станцию прибытия B и время отправления. Соединение допустимо, если отправление из А не происходит раньше заданного. Критерий оптимизации – минимизировать разницу между временем прибытия и заданным временем отправления. В другой задаче минимального количества пересадок необходимо отыскать путь с наименьшим количеством пересадок для станций А и B, вообще не принимая во внимание времена прибытий и отправлений.

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

Чтобы учесть времена пересадки во время-расширенной модели, на графе создается копия всех узлов прибытия и отправления со станции, которые мы называем узлами пересадки. Для каждого узла прибытия существует два исходящих ребра: одно ребро к отправлению того же маршрута, второе ребро – к узлу пересадки со временем больше или равным сумме времен прибытия в узел и минимальным временем требуемым на пересадку на данной станции.

Часто пассажиры заинтересованы в том, чтобы найти самый дешевый путь из А в B в заданном интервале времени. К сожалению, тарифная система в большинстве стран настолько сложна, что практически невозможно решить такую задачу поиска точно и одновременно быстро. Даже в стандартных тарифах стоимость проезда обычно не аддитивна. Еще хуже обстоит дело, если требуется учесть специальные тарифы. Многокритериальная оптимизация по нескольким критериям необходима, когда пассажиру требуется найти путь с минимальным количеством пересадок, который начинается после заданного времени и не заканчивается слишком поздно. Вычисление оптимального пути по нескольким критериям сводится к решению задачи поиска кратчайшего пути по нескольким критериям (MOSP, multi-objective shortest path) – основная задача в области многоцелевой оптимизации. Задача многокритериальной оптимизации обычно NP – полная. Так как даже для очень простых графов (цепь узлов, соединенных ребрами) в задаче с двумя критериями количество решений в наборе Парето растет экспоненциально. Поэтому на практике для нахождения решения многокритериальной задачи используются приближенные подходы.

Исследования известных алгоритмов поиска по расписаниям показали, что без применения специальных ускоряющих техник производительность оказывается недостаточной. Средняя производительность особенно важна в системах с центральным сервером, который должен обрабатывать тысячи запросов одновременно, например, в Интернет или на транспортных терминалах (вокзалах, аэропортах). Техника «ограничения угла» использует информацию о пространственном расположении географических объектов. На этапе препроцессинга применяется алгоритм Дийкстры, чтобы вычислить кратчайшие пути из узла до всех других станций. Результаты вычислений не сохраняются, так как это потребовало бы слишком много места, но сохраняются два значения углов и, которые сопоставляются ребру графа. Пусть - ребро соединяющее событие c другим событием на время-расширенном графе и пусть и – станции, к которым принадлежат эти события.

Рассмотрим угловой сектор между углами и с вершиной в точке. Углы и определяются таким образом, что конечные точки кратчайших путей, проходящих через ребро, будут внутри сектора. Позднее, во время работы алгоритма ребра могут быть проигнорированы поиском, если целевой узел не входит в угловой сектор. Основная идея другой техники «выбора станций» применяется во многих планировщиках маршрута на транспорте. Пусть – означает маршрутный граф. Пусть - набор выбранных узлов, из которых строится вспомогательный граф. Вспомогательный граф и веса ребер создаются и задаются только один раз на этапе препроцессинга. После этого любой запрос может быть обработан на вспомогательном графе и путь будет соответствовать кратчайшему пути на графе. Техника «поиска в направлении цели» использует потенциальную функцию на наборе узлов. Веса ребер в очереди изменяются так, чтобы направить поиск по графу в сторону цели. Пусть – эта потенциальная функция. Новый вес ребра определяется как «Иерархический поиск» требует препроцессинга на котором исходный граф G = (V, E) разбивается на несколько уровней и дополняется кратчайшими путями между определенными узлами. Чтобы найти кратчайший путь между узлами, алгоритму Дийкстры достаточно рассмотреть меньший подграф многоуровневого графа.

Еще одна интересная техника использует понятие «радиуса достижения». Если – вершина на кратчайшем пути P из в, то радиус достижения по отношению к есть минимум от длины префикса P (часть пути от s к v) и длины суффикса (часть пути от к ). Радиус достижения узла – это максимум по всем кратчайшим путям, которые содержат. Вычислив предварительно для всех узлов можно использовать эту информацию во время работы алгоритма Дийкстры. Техника «прямоугольника кратчайших узлов» похожа на метод «ограничения угла». На этапе препроцессинга обрабатываются все деревья кратчайших путей. Для каждого ребра, вычисляется набор узлов, кратчайшие пути к которым проходят через ребро, и для каждого, сохраняется ограничивающий прямоугольник. Во время работы алгоритма можно оперативно определить, по какому ребру необходимо двигаться дальше, исключая из рассмотрения те ребра, которые заведомо не ведут к цели.

В параграфе 1.8 сделан обзор архитектур распределенных систем кэширования в Интернет. Кэширование данных - фундаментальная технология, позволяющая уменьшить время доступа к объекту данных. Пусть N – общее число документов. Пусть – условная вероятность того, что пришедший запрос относится к документу i. Расположим документы в порядке их популярности, где документ i – i-ый по популярности документ. Полагаем, что, i = 1, 2, …N имеет Zipf распределение, где В случае бесконечного кэша и конечного числа запросов, количество попаданий как функцию количества запросов можно получить следующим образом:.

Асимптотическое поведение коэффициента попаданий Это поведение можно очевидным образом получить приближением H(R):

В случае ограниченного размера кэша объемом С документов, на который поступает бесконечный поток запросов, асимптотическое значение коэффициента H(C) может быть вычислено так:

Вероятностное распределение того, что следующий запрос к документу придет через k запросов, определяется как Эффективность кэша в Интернет сильно зависит от корреляции интересов в группе пользователей. Чтобы повысить эффективность кэширования, несколько кэшей объединяют в систему. Существует два основных подхода к построению больших систем кэширования: иерархический и распределенный. В иерархическом кэшировании кэши располагаются на различных сетевых уровнях. В распределенном кэшировании не устанавливается промежуточных кэшей. Сетевая топология моделируется в виде дерева. Пусть O – плотность ветвей дерева. Пусть N – общее число документов и S – размер документа, документы обновляются с периодичностью, запросы к документу, в кэше учреждения распределены по закону Пуассона со средней интенсивностью Тогда общее число запросов к документу равно = I,i tot,I I,i O2H и тоже распределено по Пуассону. Пусть интенсивность запросов к кэшу учреждения для всех N документов, распределена по закону.

Zipf:

где константа определяет, насколько пологим будет Zipf распределение и как:

В иерархическом кэшировании имеет место меньшее время соединения, чем в распределенном кэшировании. Но распределенное кэширование имеет меньшее время передачи, чем иерархическое кэширование, так как больше трафика проходит через менее загруженный нижний сетевой уровень. Что касается нагрузки на сеть, то при иерархическом кэшировании она суммарно меньше, чем при распределенном, так как иерархическое кэширование использует промежуточные кэши. С другой стороны, распределенное кэширование хорошо распределяет сетевую нагрузку на систему, в отличие от иерархической, где могут возникать перегруженные узлы системы.

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

В параграфе 2.1 разработан оригинальный алгоритм поиска, который строго решает поставленную двухкритериальную задачу. На первом этапе проводится поиск по «виртуальному» графу. Этот поиск находит все пути с одинаковым минимальным количеством пересадок. Найденные пути анализируются на следующем шаге алгоритма, где для каждого из них проверяется допустимость с учетом дней курсирования и наличия мест, и решается задача наискорейшего прибытия. Затем среди допустимых путей выбирается наискорейший. В том случае, если все пути оказались недопустимы, то повторяется первый этап поиска по графу с исключением найденных ранее путей. Основные функциональные части алгоритма: (i) алгоритм оптимистического поиска в графе, (ii) методы выбора наискорейшего пути из оптимистически найденных на графе, (iii) проверка наличия свободных мест. В графе хранится информация обо всех допустимых транспортных маршрутах и решается задача поиска пути с минимальным количеством пересадок. Все узлы графа, между которыми можно проехать без пересадки, соединим ребрами веса 1. Поиск такого пути можно производить с помощью двунаправленного алгоритма Дийкстры. В реализации алгоритма необходимые ребра рассчитываются динамически, и по окончании работы алгоритма память освобождается. В противном случае потребовался бы значительный объем памяти для хранения данных. В оригинальном алгоритме подсчитывается не минимальное число пересадок, а минимальное число маршрутов, которое на единицу больше числа пересадок. Известны два распространенных способа представить граф: как набор смежных вершин или как матрицу смежности. Алгоритм реализован на встроенном языке базы данных и работает с таблицами и записями. Хранение расписаний в таблицах и реализация алгоритма на уровне базы данных оказывается на практике достаточно эффективной и не требует избыточного преобразования данных. Для каждой записи о расписании хранится идентификатор узла, идентификатор маршрута, время прибытия, время отправления и другая информация. Алгоритм Дийкстры, хотя и может быть применим к данной задаче, но не является достаточно быстрым для практической реализации в справочной системе.

Существующие техники ускорения не могут быть использованы в информационной системе. В них используется длительный препроцессинг данных и хранение вспомогательной информации для каждого ребра.

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

Другой метод - балансировка двунаправленным поиском - заключается в выборе прямого или обратного поиска на каждом шаге итерации с учетом количества смежных станций. В работе этого метода используется информация о количестве смежных станций, которая может быстро вычисляться в режиме реального времени. Еще один возможный подход - это ускорение последней итерации. Последняя итерация поиска требует больше времени, чем предыдущие, так как поиск охватывает все большее количество станций. Для каждой станции вычисляется ограничивающий прямоугольник станций, достижимых без пересадок. На последнем шаге итерации используется информация об ограничивающем прямоугольнике каждой станции для выяснения, может ли станция быть пересадкой или ее заведомо нужно исключить. Еще один эффективный метод ускорения - это метод ускорения А*.

Он основан на эвристическом алгоритме А* и превосходит алгоритм Дийкстры в быстродействии. Хотя А* в данной задаче и не является точным подходом, но на практике его можно эффективно применить, и найденное решение с высокой вероятностью оказывается оптимальным. Важно, что все предложенные методы ускорения могут применяться в оригинальном алгоритме поиска совместно.

Pages:     | 1 || 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»