Удк 004. 021+004. 81 Алгоритмы построения маршрута на карте по параметрам

Вид материала

Задача

Содержание Поиск маршрута Релевантность объекта Полезность маршрута Алгоритм, основанный на решении задачи коммивояжера Генетический алгоритм P – полезность маршрута t Сравнительный анализ алгоритмов

Подобный материал:

• Удк 004. 838: 004. 853: 004. 855. 5: 004. 738. 5 Анализ эффективности работы web-сайта, 146.96kb.
• Удк 378. 147. 1: 004., 198.01kb.
• Удк 378. 144: 004. 3 Т. В. Столяр, зав библиотекой, 156.42kb.
• Удк 004. 083 +519. 71 Моделирование и оптимизация структуры информационного ресурса, 332.68kb.
• Удк 371. 13: 004, 144.17kb.
• Удк 37. 01. 004:(06) Технологии управления знаниями, 12.36kb.
• Удк 004. 89: 616 принципы структурной организации информации при построении медицинских, 144.02kb.
• Учебное пособие Санкт-Петербург 2008 удк 005. 91: 004. 9(075. 8) Ббк 65. 291. 212., 97.7kb.
• Удк 004. 89 Функциональная организация интеллекта в многоцелевой информационной среде, 131.05kb.
• Удк 378 004. 94, 167.51kb.

УДК 004.021+004.81

АЛГОРИТМЫ ПОСТРОЕНИЯ МАРШРУТА
НА КАРТЕ ПО ПАРАМЕТРАМ

Блох Илья Игоревич, Дураков Андрей Викторович

ПГНИУ, ул. Букирева, 15

Аннотация

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

Введение

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

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

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

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

Поиск маршрута

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

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

Таким образом, возникают следующие задачи:

1. Необходимо предложить способ вычисления релевантности каждого отдельного объекта.
   
2. Необходимо предложить способ определения полезности маршрута. Полезность маршрута – некоторое численное выражение его содержания, основанное на совокупности релевантностей входящих в него объектов.
   
3. Необходимо разработать алгоритм нахождения подходящего маршрута. Дополнительную сложность в задачу вносит то обстоятельство, что неизвестно, сколько объектов должно входить в такой маршрут, то есть в принципе их может оказаться от 0 до N, где N – количество объектов на карте.
   

Вычисление релевантности и полезности маршрута

Релевантность объекта

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

Положим, что значением релевантности может быть неотрицательное рациональное число. Чем выше релевантность, тем больше соответствующий объект подходит человеку. Маршрут будет строиться из наиболее релевантных объектов. На значение релевантности определяется тем, насколько близкими оказались теги пользователя к его собственным (далее близость).

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

1. Является тегом объекта, то есть полное совпадение.
   
2. Не является тегом объекта, однако принадлежит тому же словарю или словарям тегов, что и некоторые из принадлежащих объекту. Данную ситуацию можно рассматривать как косвенную близость, при которой объект тематически пользователю подходит, однако полного совпадения нет.
   
3. Не находится среди тегов объектов и не принадлежит ни одному из словарей, в который входят теги объекта.
   

За каждый случай полного совпадения (ситуация 1) значение близости увеличивается на некоторую величину _, при косвенной близости (ситуация 2) на величину за попадание в один словарь, а в случае ситуации 3 значение близости не увеличивается. Оптимальное значение будет определено уже во время тестирования приложения. Таким образом, если пользователь ввел N тегов, из которых
подходят к случаю 1, к случаю 2 и к случаю 3, при этом для тегов из второго случая имеет место _ попаданий в словари тегов, то значение близости будет равно

(1)

Полезность маршрута

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

Предлагаются следующие варианты расчета полезности P:

1. _ (2)
   

Полезность маршрута равняется самому высокому значению релевантности из входящих в маршрут объектов. Использование формулы (2) будет соответствовать принципу, согласно которому туриста нужно обязательно провести через максимально релевантный для него объект. Однако использование такого способа расчёта является неперспективным, так как согласно нему достаточно включить единственный, самый релевантный объект в маршрут. Поэтому данный способ расчёта полезности применяться не будет.

2. _ (3)
   

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

Алгоритм, основанный на решении задачи коммивояжера

Наиболее подходящий маршрут будет содержать некоторое подмножество всего множества имеющихся объектов:



Рис.1. Объекты, их релевантности и затрачиваемое время

На рис.1 каждая вершина соответствует одному объекту на карте. Известна его релевантность _, а также время, необходимое для перехода от одного объекта к другому t_(i-j) и время пребывания в объекте _. Так как нам нужно уложиться в некоторый отведённый срок, то можно рассматривать решаемую задачу как задачу коммивояжера, в которой необходимо минимизировать время прохождения всего маршрута. Однако, в отличие от задачи коммивояжера, неизвестно, сколько и какие объекты войдут в маршрут. Полученный маршрут должен оказать максимально полезным. Если рассчитывать полезность первым способом, то для нахождения подходящего маршрута достаточно найти самый релевантный объект и включить его в маршрут. В таком случае маршрут будет состоять только из одного объекта. Одна если исходить из второго способа расчета полезности, в маршрут должны войти объекты с самими большими значениями релевантности. Это будет гарантировать высокое значение суммы релевантностей, а значит и высокую полезность. К тому же, в маршрут также будет включён самый релевантный для туриста объект.

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

1. Из упорядоченного списка объектов выбирается первые M.
   
2. Для выборки решается задача коммивояжера
   
3. Затраченное на весь маршрут время сравнивается с временем, выделенным пользователем для прохождения маршрута
   
4. Если алгоритм решения задачи коммивояжера потратил больше времени, чем требуется, то величина M будет уменьшена. Если же алгоритм потратил меньше времени, то M будет увеличена. Изменение величины M проводится по принципу дихотомии, то есть каждое изменение в два раза меньше предыдущего. В первый раз M увеличивается или уменьшается также в два раза.
   
5. Алгоритм завершает работу тогда, когда происходит стабилизация значения M, то есть при очередном прохождении четвертого шага изменения M равняются 0.
   

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

Вышеприведённый алгоритм не гарантирует получение самого полезного маршрута из всех возможных. Это объясняется тем, что маршрут строится из самых релевантных объектов, а полезность считается как сумма релевантностей. Однако может оказаться так, что большее значение полезности будет достигаться при включении в маршрут большего числа объектов, не являющихся наиболее релевантными среди всех. Например, самый релевантный объект, согласно алгоритму, будет всегда включен в маршрут. Однако могут найтись такие объекты, чья суммарная релевантность выше, при тех же временных затратах на посещение. Предложенный алгоритм не сможет построить такой маршрут, который включал бы в себя набор менее релевантных по отдельности объектов вместо одного, более релевантного, чем любой из набора. []

Генетический алгоритм

Второй алгоритм, предлагаемый для решения задачи – классический генетический алгоритм [].

Предлагается следующая функция приспособленности в решаемой задаче:



P – полезность маршрута

t – время, необходимое для прохода маршрута. Вычисляется при помощи жадного алгоритма решения задачи коммивояжера

– время, которым ограничен пользователь



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

Таким образом, решение будет кодироваться так: i-му гену хромосомы будет соответствовать тот объект, который является i-м в обходе всех объектов жадным алгоритмом для задачи коммивояжера. Значение гена i будет равно 0, если i-ый объект из нового списка не включен в маршрут, и будет равно 1 в противном случае.

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

Сравнительный анализ алгоритмов

Выделим два критерия сравнения алгоритмов:

1. Разница между временем, заданным пользователем и временем, вычисленным алгоритмом. Эта разница должна быть как можно ближе к 0.
   
2. Итоговая полезность маршрута. Чем выше полезность маршрута, тем считается лучше работает алгоритм.
   

Было проведено несколько сравнительных тестов. [, c.20] В каждом из них фиксировались данные, получаемые от пользователя, и выбирались различные параметры алгоритмов. За каждый тест алгоритм решал поставленную задачу фиксированное число раз.

Заключение

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



Рис.2. Полезность построенных алгоритмами маршрутов за 20 прогонов


Библиографический список

1. Блох И.И. Разработка алгоритмов построения маршрута для ГИС-приложения туриста – 2010. – курсовая работа – 43 с.
   
2. Вороновский Г. К., Махотенко К. В., Петрашев С. Н., Сергеев С. А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. – Х.: ОСНОВА, 1997. – 112 с.
   
3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / Пер. с англ. под ред. Шеня А. – М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 2-е изд., стереотип. – 960 с.
   

Algorithms of route construction by parameters

Blokh Ilya Igorevich, Durakov Andrey Victorovich

Perm State University, Bukireva st. 15

Annotation

In this article the necessity of algorithms of route construction by parameters development was based, the problem was analyzed, approaches for issue resolving were given. Description of two algorithms and of their comparative analysis proposed.