Содержание

ЦЕЛЬ НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЫ

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

Алгоритм Дейкстры поиска кратчайшего пути

     Будем хранить текущее минимальное расстояние до всех вершин V (от данной вершины a) и на каждом шаге алгоритма пытаться уменьшить это расстояние. Первоначально установим расстояния до всех вершин равным бесконечности, а до вершины а - нулю.

Рассмотрим выполнение алгоритма на примере. Пусть нужно найти расстояния от 1-й вершины до всех остальных. Кружочками обозначены вершины, линиями - пути между ними ("дуги"). Над дугами обозначена их "цена" - длина пути. Красным обозначено текущее кратчайшее расстояние до вершины.

Шаг 1

     Инициализация. Расстояния до всех вершин графа V = ?. Расстояние до а = 0. Ни одна вершина графа не обработана.

Шаг 2

     Находим такую вершину (из еще не обработанных), текущее кратчайшее расстояние до которой минимально. В нашем случае это вершина 1. Обходим всех ее соседей и, если путь в соседнюю вершину через 1 меньше текущего минимального пути в эту соседнюю вершину, то запоминаем этот новый, более короткий путь как текущее кратчайшее расстояние до соседа.

Шаг 3

     Первый по очереди сосед 1-й вершины - 2-я вершина. Путь до нее через 1-ю вершину равен кратчайшему расстоянию до 1-й вершины + длина дуги между 1-й и 2-й вершиной, т.е. 0 + 7 = 7. Это меньше текущего кратчайшего расстояния до 2-й вершины, поэтому новое расстояние до 2-й вершины равно 7.

Шаги 4, 5

     Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.

Шаг 6

     Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и обсуждению не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем ее из графа, чтобы отметить этот факт.

Шаг 7

     Практически происходит возврат к шагу 2. Снова находим "ближайшую" необработанную (невычеркнутую) вершину. Это вершина 2 с текущим кратчайшим расстоянием до нее = 7.

И снова пытаемся уменьшить расстояние до всех соседей 2-й вершины, пытаясь пройти в них через 2-ю. Соседями 2-й вершины являются 1, 3, 4.

     Первый (по порядку) сосед вершины № 2 - 1-я вершина. Но она уже обработана (или вычеркнута - см. шаг 6). Поэтому с 1-й вершиной ничего не делаем.

Шаг 8

     Другой сосед вершины 2 - вершина 4. Если идти в нее через 2-ю, то путь будет = кратчайшее расстояние до 2-й + расстояние между 2-й и 4-й вершинами = 7 + 15 = 22. Раз 22 < ?, устанавливаем расстояние до вершины № 4 равным 22.

Шаг 9

     Еще один сосед вершины 2 - вершина 3. Если идти в нее через 2-ю, то путь будет = 7 + 10 = 17. Но 17 > уже запомненного ранее расстояния до вершины № 3 и равного 9, поэтому текущее расстояние до 3-й вершины не меняем.

Шаг 10

     Все соседи вершины 2 просмотренны, замораживаем расстояние до нее и вычеркиваем из графа.

Шаги 11 - 15

     По уже "отработанной" схеме повторяем шаги 2 - 6. Теперь самой "близкой" оказывается вершина № 3. После ее "обработки" получим такие результаты:

Дальнейшие шаги

     Проделываем то же самое с оставшимися вершинами (№ по порядку: 6, 4 и 5).

Завершение выполнения алгоритма

     Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от 1-й вершины до 2-й составляет 7, до 3-й — 9, до 4-й — 21, до 5-й — 20, до 6-й — 11 условных единиц.

ТЕХНОЛОГИЯ WEB SERVICES

Сеть Интернет стала общепризнанным фактором деловой и общественной жизни. Широкая распространенность и возросшая пропускная способность создают условия, при которых выгодно решать многие задачи при помощи интернет-технологий. Однако Интернет объединяет в себе много различных платформ, а информация содержится в разнообразных источниках данных. Поэтому актуальна проблема связи таких разнородных данных, а также создания способа, который позволяет получать их в виде удобном для дальнейшей обработки. Концепция веб-сервисов (Web Services) призвана решить эту задачу объединения, интеграции разнородных систем на основе открытых стандартов. Данная работа посвящена веб-сервисам, в ней кратко рассмотрены основные положения модели веб-сервисов, а также компоненты этой модели и технологии, используемые для их реализации. Практическая часть работы содержит небольшой пример, демонстрирующий разработку веб-сервиса и приложений использующих его. Пример основывается на реализации концепции веб-сервисов в рамках Java-технологий. Для понимания примера достаточно базовых знаний Java. Веб-сервисы являются концепцией создания таких приложений, функции которых можно использовать при помощи стандартных протоколов Интернет. В настоящее время эту концепцию применяют и развивают многие ведущие компании в IT-области. Концепция веб-сервисов реализуется при помощи ряда технологий, которые стандартизованы World Wide Web Consortium (W3C). Взаимосвязь этих технологий можно условно представить следующим образом.

     Веб-сервисы являются одним из вариантов реализации компонентной архитектуры. XML является фундаментом для создания большинства технологий, связанных с веб-сервисами. Для удаленного взаимодействия с веб-сервисами используется Simple Object Access Protocol (SOAP) [3]. SOAP обеспечивает взаимодействие распределенных систем, независимо от объектной модели, операционной системы или языка программирования. Данные передаются в виде особых XML документов особого формата. Согласно определению W3C, веб-сервисы это приложения, которые доступны по протоколам, которые являются стандартными для Интернет. Нет требования, чтобы веб-сервисы использовали какой-то определенный транспортный протокол. Спецификация SOAP определяет, каким образом связываются сообщения SOAP и транспортный протокол. Наиболее часто реализуется передача SOAP сообщений по протоколу HTTP. Также широко распространено использование в качестве транспортного протокола SMTP, FTP, TCP. Согласно определению W3C, "WSDL - формат XML для описания сетевых сервисов как набора конечных операций, работающих при помощи сообщений, содержащих документно-ориентированную или процедурно-ориентированную информацию" [3]. Документ WSDL полностью описывает интерфейс веб-сервиса с внешним миром. Он предоставляет информацию об услугах, которые можно получить, воспользовавшись методами сервиса, и способах обращения к этим методам. Технология Universal Description, Discovery and Integration (UDDI) предполагает ведения реестра веб-сервисов. Подключившись к этому реестру, потребитель сможет найти веб-сервисы, которые наилучшим образом удовлетворяют его потребностям. Технология UDDI дает возможность поиска и публикации нужного сервиса, как человеком, так и программой-клиентом. Поиск и публикация в реестре предоставляется программе-клиенту как набор веб-сервисов реестра UDDI. Веб-сервисы позиционируются как программное обеспечение промежуточного слоя. Использовать веб-сервисы могут как клиентские приложения, непосредственно работающие с пользователем, так и другие приложения (в том числе и другие веб-сервисы). Веб-сервисы размещаются на серверах приложений. Разработчики концепции веб-сервисов предлагают следующие сценарии применения веб-сервисов: Веб-сервисы как реализация логики приложения (бизнес-логики). То есть, создание нового приложения бизнес-логика, которого реализуется в веб-сервисе.

Веб-сервисы как средство интеграции. То есть, использование веб-сервиса как способа доступа удаленных клиентов к внутренней ИС компании, или для организации взаимодействия компонента (например, EJB, COM-компонента) с различными удаленными клиентами.

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

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

4. СТРУКТУРА РАСПРЕДЕЛЕННОЙ СИСТЕМЫ

Структура распределенной сети представлена на рис. 4.1. Она состоит из серверной и клиентской части. Важно отметить, что Web-сервер не работает непосредственно с хранилищем данных и не реализует логику системы. Эти функции сосредоточены в Web-сервисе, который предлагает наша система. Все клиенты, основанные на HTML либо WML интерфейсе, работают с Web-сервером, в то время как для всех остальных клиентов предоставлен Web-сервис. Таким образом даже внутренний web-сервер нашей системы является клиентом для Web-сервиса.

Для узлов распределенной системы выбраны следующие продукты различных фирм-производителей крупных корпоративных систем:

5. БАЗА ДАННЫХ

Схема базы данных представлена на рисунке 5.1. Она описывает принцип построения схемы базы данных на концептуальном уровне. На физическом уровне будет использована СУБД Oracle и соответственно типы данных будут соответствовать тем, которые используются в СУБД. В основном благодаря следующим нововведениям Oracle завоевала в наши дни огромную популярность на рынке СУБД:

Рисунок 5.1 - Cхема данных БД

Рисунок 5.1 - Раздел рынка СУБД для платформы UNIX

Рисунок 5.1 - Раздел рынка СУБД для платформы Windows NT

6. ВЫВОДЫ

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

     Все данные должны храниться в БД, а для работы с ними необходимо использовать управляемые контроллером классы. Бизнес методы должны работать непосредственно с этими классами, а не с СУБД. Также, как и Web-сервер должен работать с Web-сервисом, а не с БД.

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

7. СПИСОК ЛИТЕРАТУРЫ

1. Э.Майника, АЛГОРИТМЫ ОПТИМИЗАЦИИ НА СЕТЯХ И ГРАФАХ М.: Мир, 1981,324 стр.

2. А.А.Зыков, ОСНОВЫ ТЕОРИИ ГРАФОВ, НАУКА, 1986, 381 стр.

3. Н.Вирт, АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ, М.: Мир, 1989, 360 стр.

PS:На момент создания этой страницы проект находится на стадии разработки. Полный текст магистерской работы будет доступен после защиты в 2007 году.