Алгоритмы и технология решения задач

Схема графического диалога пользователя в интернет-офисе представлена на рис. 2.6.

Рис. 2.6. Схема графического диалога пользователя в интернет-офисе

Алгоритм поиска клиентом варианта обмена в интернет-офисе представлен на рис. 2.7.

Рис. 2.7. Алгоритм поиска клиентом варианта обмена в интернет-офисе

Алгоритм обработки входящей информации менеджером представлен на рис. 2.8.

Рис. 2.8. Алгоритм обработки входящей информации менеджером

Математическая модель

Одной из важных составляющих информационных процессов в современных технических и экономических системах является необходимость принятия неформальных решений многоцелевого выбора [19].

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

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

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

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

Шаг 1. Определение n параметров квартир.

Шаг 2. Выяснение предпочтений для соответствующих квартирных параметров.

Шаг 3. Выделение области компромиссов (решений, оптимальных по Парето).

Шаг 4. Оптимизация на основе полученных решений с помощью эстафетного метода.

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

Агентство недвижимости имеет базу данных, в которой содержатся количественные характеристики квартир (этаж, площадь и т. д.) [8].

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

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

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

(2.1).

При фиксированных линии уровня функции являются, по сути, поверхностями безразличия в пространстве квартирных параметров.

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

• ? вместо скаляра, отвечающего за высоту этажа, введем пятимерный вектор по правилу; ;;; ;
• ? вместо скаляра, отвечающего за оценку этажа, введем пятимерный вектор по правилу, где — цена этажа i.

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

Пусть имеется набор квартир, где. Обозначим через Z матрицу размерности, в которой элемент определяет оценку квартиры k:

(2.2).

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

По сути, Z является произведением матрицы Х (в которой векторы располагаются по строкам) и матрицы V (в которой вектор выстраивается по столбцам).

Далее, жилец согласен переехать из своей квартиры в, когда происходит улучшение его жилищных условий:

(2.3).

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

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

Существуют следующие алгоритмы, применяемые для решения задачи о кратчайшем маршруте как самостоятельно, так и в совокупности с другими методами [5, 11]:

• ? волновой алгоритм — алгоритм, позволяющий найти минимальный путь на графе с рёбрами единичной длины;
• ? алгоритм Дейкстры — находит кратчайшее расстояние от одной из вершин графа до всех остальных, работает только для графов без рёбер отрицательного веса;
• ? алгоритм Флойда — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа;
• ? алгоритм Форда-Беллмана — алгоритм поиска кратчайшего пути во взвешенном графе за время ;
• ? алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа;
• ? алгоритм Краскала — находит остовный лес минимального веса в графе.

Классическая задача о кратчайшем пути на графе относится по степени сложности к классу NP-полных задач, и ее постановка в форме задачи математического программирования со скалярными переменными не позволяет создать достаточно эффективные алгоритмы, особенно для решения задач больших размеров. Поэтому нужны специальные методы, не связанные с классическим подходом, основанным на аппарате анализа бесконечно малых величин. Наиболее успешные реализации приближенных алгоритмов связаны с двумя схемами решения: улучшения исходного цикла и последовательного построения цикла. Предлагаемый эстафетный метод (ЭМ) построения кратчайшего пути на графе относится ко второй схеме [4].

Формальную постановку задачи о кратчайшем пути на графе удобно записать в комбинаторном виде как задачу минимизации (максимизации) целевой функции (2.4) на множестве нескалярных переменных :

(2.4).

где — длина дуги в соответствующих единицах;

r — возможное количество номеров промежуточных вершин в кортеже (r=0; n-2).

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

Блок-схема алгоритма эстафетного метода представлена на рис. 2.9.

Для описания алгоритма ЭМ введем некоторые обозначения:

? множество номеров вершин, к которым при выполнении t-го шага (итерации) процесса ещё не найдены кратчайшие маршруты (например,.

).

Рис. 2.9. Алгоритм эстафетного метода (ЭМ)

? множество номеров вершин, к которым при выполнении t-го шага от вершины существует конечная дуга () и, следовательно, к этим вершинам ещё возможно построение маршрута.

(2.5).

где — множество номеров вершин, от которых за все t шагов стартовали группы гонцов (например,).

? множество номеров концевых вершин, к которым на t-м шаге были найдены кратчайшие маршруты.

Данный алгоритм достаточно прост, что обеспечивает решение задач больших размеров (n >1000) за приемлемое для практических целей время.

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

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

Для решения задачи коммивояжера применяют следующие методы:

• ? метод «ближайшего соседа»;
• ? метод «ближайшего соседа с двух сторон»;
• ? метод «ветвей и границ»;
• ? метод полного перебора.

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

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

Методом решения задачи коммивояжера, позволяющим получить оптимальное решение, является метод ветвей и границ (алгоритм Литтла). Данный алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом, то есть графом, в котором каждая пара различных вершин смежна. Это утверждение накладывает серьезное ограничение на решение рассматриваемой проблемы построения взаимовыгодных схем квартирных обменов [1, 11].

Предлагаемый метод расширения цикла (МРЦ) позволяет рассматривать постановку классической задачи коммивояжера с жестким или ослабленным требованием на количество вершин каждого типа в конечном цикле, снимая, таким образом, ограничение на полноту матрицы смежности c [4].

Формальную постановку задачи коммивояжера можно записать в виде задачи минимизации (максимизации) целевой функции на множестве нескалярных переменных (квартир):

(2.6).

где — длина дуги в соответствующих единицах (сумма доплаты);

• — длина цикла как сумма длин дуг (i, j), входящих в цикл n?1;
• — контур (цикл), содержащий в качестве промежуточных все n-1 остальных вершин графа (гамильтонов цикл).

Блок-схема алгоритма метода расширения цикла представлена на рис. 2.10.

Суть МРЦ состоит в том, что на каждом t-м шаге процесса при пробном включении j -й вершины в интервал (k — i) вместо дуг (k, j) и (j, i) при вычислении приращения используются кратчайшие маршруты и :

(2.7).

Рис. 2.10. Алгоритм метода расширения цикла (МРЦ)

где точки в (2.7) между k, i; j, i отражают тот факт, что соответствующие вершины соединены через кратчайшие маршруты.

Использование (2.7) предполагает отказ от жесткого условия об однократности включения каждой вершины в цикл, а, следовательно, создает дополнительные условия для уменьшения его длины.

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

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

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

(2.8).

В качестве начального цикла (t=1) в модифицированном методе расширения цикла целесообразно брать цикл, составленный из двух кратчайших маршрутов, которые соединяются между собой включаемым в нулевой цикл (k, k) номером j:

(2.9).

где точка между индексами означает, что k, j и k соединены кратчайшими маршрутами.

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

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

Таким образом, с помощью метода расширения цикла получена замкнутая схема обмена квартир.

Пример работы предложенного алгоритма

Рассмотрим работу предложенного алгоритма формализации обменных операций на примере.

Шаг 1.

Пусть — однокомнатная квартира, которая имеет количественные характеристики в соответствии с БД агентства недвижимости. Параметры квартиры представлены в таблице 2.5.

Ранжирование параметров квартир в соответствии с данными, полученными в агентстве недвижимости «Лидер», представлено в таблице 2.4.

Шаг 2.

Далее, в результате опроса экспертов агентства недвижимости «Лидер» были выяснены предпочтения квартирных параметров клиентами агентства, и получен вектор предпочтений для соответствующих квартирных показателей (табл. 2.5).

Шаг 3.

Общая ценность квартиры вычисляется как скалярное произведение двух векторов и. Согласно (2.3) владельцу квартиры в качестве варианта обмена может быть предложена квартира (табл. 2.6).

Шаг 4.

Предположим, что для рассматриваемого варианта менеджеру агентства недвижимости не удалось подобрать прямой обмен. Тогда на основе исходного множества альтернатив, полученного на шаге 3 данного алгоритма, естественно построить ориентированный граф обменов квартир, в котором являются вершинами, а между и проводится стрелка при выполнении условия (2.3).

Таблица 2.6.

Граф G обменных операций представлен на рис. 2.9.

Рис. 2.9. Граф обменных операций

Граф G квартирных обменов в соответствии с вектором предпочтений представлен также матрицей смежности, где i — возможные альтернативы, j — критерии выбора (табл. 2.7).

Таблица 2.7.

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

Для первого шага (t=1; пункт) вычисляются начальные значения текущих величин :

Множество концевых дуг лидеров стартовавших групп для шага t=1 () согласно равно:

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

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

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

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

Далее осуществляется переход к шагу t=2 (пункт), и весь цикл повторяется уже с двумя стартовавшими группами, так как .

Расчеты работы алгоритма ЭМ для шагов 2, 3 и 4 имеют следующий вид.

.

.

.

К вершинам 1, 4 и 5 все возможные маршруты уже найдены, тогда.

.

Таким образом, искомая схема квартирного обмена получена на шаге t=4. Результаты расчетов представлены в таблице 2.8.

Таблица 2.8.

Множество кратчайших маршрутов (схем обмена) и их длины (суммы доплаты) вычислены согласно алгоритму ЭМ (табл. 2.9).

Шаг 5.

Порядок решения задачи коммивояжера методом расширения цикла имеет следующий вид.

Начало цикла выбирается произвольно, пусть k=1.

Таблица 2.9.

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

Согласно (2.7) и таблице 2.9 для шага t=1:

В один из пяти интервалов осталось включить только номер вершины .

.

Таким образом, получена оптимальная замкнутая схема квартирных обменов.

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