VI Международная студенческая научная конференция Студенческий научный форум - 2014

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

В общем виде математическую постановку задачи на графах можно описать следующим образом. Задается n-вершинный взвешенный граф G=(X, A), где A={a_i}, i =1, 2,..., m - множество ребер, X = {x_i}, i = 1, 2, ..., n - множество вершин  и  C = {c_i},  i = 1, 2, 3,..., m - множество характеристик дуг. Во взвешенном графе G через с_i(a_i) обозначается вес ребра, a_iÎA. Заданием графа неконструктивно определяется множество или система  S_n={s}  некоторых объектов. Часто s - это некоторая часть графа G. Задается также целевая функция F= f(s), определенная на элементах множества S_n. Задача состоит в том, чтобы в множестве S_n выделить элемент s₀, который является экстремальным согласно целевой функции F.  Как правило, мощность множества S_n очень велика по сравнению с числом вершин графа G. Например, если  S_n - множество гамильтоновых путей в полном ориентированном графе G, то мощность |S_n| = n!.

Алгоритмы решения таких задач принадлежат классу NP полных задач, экспоненциально зависят от размера входа. Решать такие задачи методом перебора всех элементов из S_n  не представляется возможным. Поэтому в более точной формулировке смысл решения задачи на графе состоит в том, чтобы построить достаточно эффективный алгоритм, который гарантированно находит оптимум в случае, если множество допустимых решений  S_n  не пусто. В графе G  с  числом вершин, равным  n,  алгоритм можно считать достаточно  эффективным,  если он находит точное  решение  задачи  и  при этом затрачивает  порядка  n^k   операций, где k - константа.  Операция - это сравнение двух  чисел  или  арифметическая операция. Теоретический интерес представляют алгоритмы трудоемкости t=t(n), для которых справедливо соотношение    Если задача сформулирована на взвешенном графе, то множество допустимых её решений  обозначаем через Y = Y(G) ={y}, где  y=(X_y, A_y) - это удовлетворяющий соответствующим условиям подграф графа G,  X_y ÍХ  и A_y Í А. Качество допустимых решений  y  определяется целевой функцией  F(y), которая представляет собой суммарный вес ребер подмножества  A_y.

Для реализации были выбраны задачи, которые являются классическим примером  NP-задач.  Это задача коммивояжёра и  задача китайского почтальона. Задача коммивояжера  заключается в отыскании самого выгодного маршрута, проходящего через указанные города как минимум один раз с последующим  возвратом в исходный город. Таким образом, коммивояжер сталкивается с задачей  поиска  гамильтонова контура минимальной длины.  Гамильтонов контур возможен только в связном графе с четными степенями каждой вершины. Поэтому  выполняется решение общей задачей коммивояжера, т. е. поиск минимального маршрута с возвратом в точку старта для всех возможных путей. При этом при необходимости вершины посещаются не один раз. [2].

Сформулируем задачу в терминах теории графов. Во взвешенном графе G=(X, A),  каждому ребру (x_i, x_j) которого сопоставлен вес c(x_i, x_j), требуется найти гамильтонов контур наименьшей стоимости, причем контур не обязательно должен  содержать  все  ребра графа. Указывается критерий выгодности маршрута  и  соответствующие  матрицы расстояний, стоимости и т. п.  Целью  решения  является  нахождения  маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.

Решить задачу можно разными способами, которые отличаются точностью и скоростью решения.  В данной работе в основе реализации задачи коммивояжера  лежит алгоритм  Прима - для нахождения на графе минимального остовного дерева  и алгоритм  Дейкстры [1,3] - для построения матрицы кратчайших путей между всеми вершинами графа.

Задача  почтальона заключается в том, чтобы пройти все улицы маршрута и вернуться в его начальную точку, минимизируя при этом длину пройденного пути.  Сформулируем задачу в терминах теории графов. Во взвешенном n-вершинном связном неографе  G=(X, A), каждому ребру (x_i, x_j) которого сопоставлен вес c(x_i, x_j), требуется найти такой кратчайший  замкнутый  маршрут, который посещает каждое ребро a_iÎA (через некоторые ребра проходит многократно). В условиях задачи указывается критерий выгодности маршрута  и соответствующие матрицы расстояний, стоимости и т. п.

Эта задача имеет оптимальное решение только в Эйлеровом графе. В этом случае замкнутый маршрут проходит по каждому ребру единожды.  Граф является Эйлеровым тогда и только тогда, когда он связен и степени всех его вершин четны.  Если в графе имеются вершины с нечетной степенью, то почтальон должен повторно обойти нечетное число ребер, при этом  повторно обходимые ребра  образуют  цепи,  началом  и концом которых являются вершины с нечетной степенью. Т. е. почтальон должен решить, какие ребра, соединяющие вершины с нечетной степенью, будет обходить повторно. Эта задача сводится к полиномиальной задаче нахождения оптимального совершенного паросочетания  в  полном взвешенном графе размерности m<n. Для ее решения использован  алгоритм построения паросочетаний с максимальным весом и алгоритм Дейкстры - для построения матрицы кратчайших  путей  между  всеми вершинами  графа [2,3].

Для реализации рассмотренных алгоритмов был разработан специализированный процессор (СП), структурная схема которого приведена на рисунке 1.

Рисунок 1 - Электрическая структурная схема СП

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

ОЗУ предназначено для хранения результатов работы устройства, и по завершении работы может быть считано с помощью сигналов «Чтение ОЗУ» и «Адрес ОЗУ».

Для реализации СП использованы программируемые логические интегральные схемы (ПЛИС)  семейства VirtexII Pro. 

Литература

1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. 2-е изд.-М.: «Вильямс» 2006. -1296 с. 

2.  Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: «Мир», 1981. - 324 с. 

3. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 432 с.

4. Федосеева Л.И., Юрлов Аппаратная оптимизация графовых задач. / Л.И.Федосеева А.А. Юрлов // XXI век: итоги прошлого и проблемы настоящего плюс: пер. науч. изд. - Пенза, №10 (14), 2013, с.172-175.