3.5 Сетевые модели и графы. ч.1

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

Частным случаем сетевой модели являются обычные бинарные графы, которые могут быть ориентированными или неориентированными. Граф математически задается в виде набора элементов:

(X,V, Г),

где X – множество вершин;

V – множество ребер (или дуг – для ориентированного графа), связывающих между сообй вершины, т.е. v (x_i,x_j) – ребро, соединяющее между собой вершины x_i,x_j из множества Х;

Г – инцидентор отношения на множестве X, в котором как раз и заложен смысл взаимосвязей между моделируемыми объектами.

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

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

Добавим, что графы могут быть взвешенными, т.е. ребра (дуги) и/или вершины могут наделяться некоторыми числовыми характеристиками. Так, в графе отношения «причина-следстве» веса дуг могут означать субъективные (экспертные) оценки вероятности наступления одних событий в результате других.

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

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

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

Положим, что веса F – это не просто измеренные расстояния или пропускные способности, а некоторые комплексные показатели, зависящие от более частных f:

F = F (f1, f2, f,3, …)

Так, в задаче поиска оптимального маршрута f1 может быть показателем качества дорожного покрытия, f2 – расстоянием на участке маршрута, а f3 – показателем загруженности участка маршрута. Часть из этих показателей будут объективной измеряемой величиной (расстояние f2), но другая часть показателей могут быть экспертно вычисляемыми на некоторой балльной шкале (f1, f3). Вспомним способы комбинирования F (см. например [9]). В качестве основного можно выделить способ аддитивной свертки:

F = ∑ α_if_i^н

где f_i^н – нормированное значение частных показателей ;

α_i – коэффициенты относительной важности частных показателей в суммарном F.

Заметим, что эти веса в данном случае могут означать:

- мнения экспертов (которые формируются путем экспертных опросов одновременно с оценками f_i);

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

Таким образом, в предложенной графовой модели будут соединены знания объективные и знания субъективные, т.е. экспертные. Более того, система позволяет учесть не только внешние экспертные оценки, но и предпочтения и приоритеты самого ЛПР – пользователя, выполняющего выбор. Именно учет предпочтений ЛПР является необходимой составляющей человеко-машинных систем поддержки принятия решений, особенно  в сложных условиях многокритериальности (см. [9])

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

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

Читать дальше:

3.5 Сетевые модели и графы. ч.2