Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока
В статье представлена запатентованная полезная модель устройства определения места максимального потока в сети связи, созданная на основе квадратичной сложности алгоритма поиска минимального разреза многополюсных сетей теории графов. Технический результат применения данной модели состоит в повыше...
Saved in:
| Date: | 2008 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/7464 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока / К.Э. Тожа, О.О. Варламов // Штучний інтелект. — 2008. — № 4. — С. 302-307. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-7464 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-74642010-03-31T12:01:40Z Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока Тожа, К.Э. Варламов, О.О. Системы принятия решений, планирования и управления. Информационная безопасность интеллектуальных систем В статье представлена запатентованная полезная модель устройства определения места максимального потока в сети связи, созданная на основе квадратичной сложности алгоритма поиска минимального разреза многополюсных сетей теории графов. Технический результат применения данной модели состоит в повышении достоверности при определении места максимального потока, которое является местом потенциального затруднения связи в сети. У статті представлена запатентована корисна модель пристрою визначення місця максимального потоку в мережі зв’язку, створена на основі квадратичної складності алгоритму пошуку мінімального розрізу багатополюсних мереж теорії графів. Технічний результат застосування даної моделі полягає в підвищенні достовірності при визначенні місця максимального потоку, яке є місцем потенційного утруднення зв’язку в мережі. 2008 Article Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока / К.Э. Тожа, О.О. Варламов // Штучний інтелект. — 2008. — № 4. — С. 302-307. — Бібліогр.: 2 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/7464 007.04 ru Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системы принятия решений, планирования и управления. Информационная безопасность интеллектуальных систем Системы принятия решений, планирования и управления. Информационная безопасность интеллектуальных систем |
| spellingShingle |
Системы принятия решений, планирования и управления. Информационная безопасность интеллектуальных систем Системы принятия решений, планирования и управления. Информационная безопасность интеллектуальных систем Тожа, К.Э. Варламов, О.О. Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока |
| description |
В статье представлена запатентованная полезная модель устройства определения места максимального
потока в сети связи, созданная на основе квадратичной сложности алгоритма поиска минимального
разреза многополюсных сетей теории графов. Технический результат применения данной модели состоит
в повышении достоверности при определении места максимального потока, которое является местом
потенциального затруднения связи в сети. |
| format |
Article |
| author |
Тожа, К.Э. Варламов, О.О. |
| author_facet |
Тожа, К.Э. Варламов, О.О. |
| author_sort |
Тожа, К.Э. |
| title |
Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока |
| title_short |
Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока |
| title_full |
Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока |
| title_fullStr |
Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока |
| title_full_unstemmed |
Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока |
| title_sort |
интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2008 |
| topic_facet |
Системы принятия решений, планирования и управления. Информационная безопасность интеллектуальных систем |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/7464 |
| citation_txt |
Интеллектуальные системы принятия решений и запатентованное устройство определения в сети связи места минимального разреза и максимального потока / К.Э. Тожа, О.О. Варламов // Штучний інтелект. — 2008. — № 4. — С. 302-307. — Бібліогр.: 2 назв. — рос. |
| work_keys_str_mv |
AT tožaké intellektualʹnyesistemyprinâtiârešenijizapatentovannoeustrojstvoopredeleniâvsetisvâzimestaminimalʹnogorazrezaimaksimalʹnogopotoka AT varlamovoo intellektualʹnyesistemyprinâtiârešenijizapatentovannoeustrojstvoopredeleniâvsetisvâzimestaminimalʹnogorazrezaimaksimalʹnogopotoka |
| first_indexed |
2025-07-02T10:15:54Z |
| last_indexed |
2025-07-02T10:15:54Z |
| _version_ |
1836529856190349312 |
| fulltext |
«Искусственный интеллект» 4’2008 302
3Т
УДК 007.04
К.Э. Тожа, О.О. Варламов
Московская академия рынка труда и информационных технологий, г. Москва, Россия
ovar@narod.ru
Интеллектуальные системы принятия
решений и запатентованное устройство
определения в сети связи места минимального
разреза и максимального потока
В статье представлена запатентованная полезная модель устройства определения места максимального
потока в сети связи, созданная на основе квадратичной сложности алгоритма поиска минимального
разреза многополюсных сетей теории графов. Технический результат применения данной модели состоит
в повышении достоверности при определении места максимального потока, которое является местом
потенциального затруднения связи в сети.
В настоящее время определение максимального потока критически важно для
многих систем принятия решений, планирования и управления в интеллектуальных
системах, сетях связи и информационных инфраструктурах.
Задача поиска максимального потока относится к классическим задачам теории
графов, называемых еще поиском минимального разреза. Важной проблемой является
снижение вычислительной сложности таких алгоритмов. Как правило, известные
решения этих задач характеризуются кубической сложностью для двухполюсных сетей.
В работе представлена запатентованная полезная модель устройства для определе-
ния места максимального потока в сети связи [1]. Полезная модель создана на основе
квадратичной сложности алгоритма поиска минимального разреза многополюсных
сетей теории графов [2]. Технический результат состоит в повышении достоверности
при определении места максимального потока, которое является местом потенциального
затруднения связи в сети [1], [2].
Постановка задачи
Решаемая задача – создание устройства определения максимального потока для
интеллектуальных систем принятия решений, планирования и управления в целях
снижения вычислительной сложности решения этих задач.
Краткое описание полезной модели
Полезная модель относится к измерительной технике и может быть использована
для исследования параметров систем, описываемых графами, в частности в информаци-
онно-вычислительных сетях или сетях связи.
Известно устройство определения путей распространения сигналов в системах,
описываемых графами (например, патент РФ № 2111533, кл. G06F 15/173, опубл. в
Интеллектуальные системы принятия решений...
«Штучний інтелект» 4’2008 303
3Т
1998 г.), включающее блок задания матрицы, соединенный с блоком управления и
синхронизации, блок формирования дуг графа, соединенный с блоком регистрации,
регистр.
Известное устройство не позволяет находить место максимального потока
в сети связи.
Задачей настоящей полезной модели является разработка устройства для
определения места максимального потока, которое является местом потенциального
нарушения или серьезного затруднения связи в сети.
Технический результат состоит в повышении достоверности при определении
места максимального потока. Результат достигается тем, что в устройство для опреде-
ления места максимального потока в сети связи, включающее блок задания матрицы,
соединенный с блоком управления и синхронизации, блок формирования дуг графа,
соединенный с блоком регистрации, регистр, введены блок сравнения и блок определе-
ния минимума, причем, выход блока управления и синхронизации соединен с входами
блока формирования дуг графа, блока регистрации, блока определения минимума,
блока сравнения и регистра, выход блока задания матрицы соединен с входом блока
формирования дуг графа, выход которого соединен с входом блока регистрации, выход
которого соединен с входом блока определения минимума, выход которого соединен с
входом блока сравнения, соединенным с выходом регистра, выход блока сравнения
является выходом устройства, входы которого соединены с входами регистра, блока
задания матрицы и блока управления и синхронизации.
Схема запатентованного устройства
Устройство содержит:
1) блок 1 управления и синхронизации,
2) блок 2 задания матрицы,
3) блок 3 формирования дуг графа,
4) регистр 4,
5) блок 5 регистрации,
6) блок 6 определения минимума и
7) блок 7 сравнения.
Блок-схема устройства приведена на рис. 1.
Рисунок 1 – Блок-схема устройства
Тожа К.Э., Варламов О.О.
«Искусственный интеллект» 4’2008 304
3Т 3Т
Алгоритм функционирования устройства
Устройство работает следующим образом.
Блок 1 выполняет управление и синхронизацию работы устройства.
В блоке 2 формируются элементы матрицы графа сети. В этот блок поступают в
качестве исходных данных:
1) набор всех вершин графа и
2) набор всех дуг графа.
Набор дуг представляет собой совокупность двух вершин: исходной и конечной для
дуги графа. Все вершины должны быть пронумерованы и каждая дуга задается набором
двух чисел – номеров соответствующих вершин: исходной и конечной, которые
связывает конкретная дуга.
Процесс нумерации вершин является заданием исходных данных и выполняется
заранее и вне данного устройства. На вход данного устройства подаются только заранее
сформированные наборы чисел.
Нумерация вершин производится таким образом, что два полюса, между которыми
необходимо найти минимальный разрез (максимальный поток), получают минимальное
(1) и максимальное (N) значения, где N – количество вершин графа. Все остальные
вершины нумеруются по мере удаления от полюсов графа. Мерой удаленности является
минимальный путь по количеству дуг, начиная с полюса графа и до конкретной вершины.
Наиболее близкими являются вершины непосредственно связанные одной дугой с
соответствующим полюсом и им присваиваются ближайшие к этому полюсу номера.
Нумерация равноудаленных вершин производится в произвольном порядке. Каждая
вершина нумеруется только один раз. Таким образом, в блоке 2 хранятся два набора:
1) номера (числа) вершин графа и
2) пары чисел (номеров вершин), определяющие дуги графа.
Блок 3 определяет наличие связей для каждой вершины графа, т.е. задает значения
элементам матрицы графа связи. На основании информации, хранящейся в блоке 2, из
соответствующих набора (вершин) чисел и набора (дуг) пар чисел в блоке 3 формируется
нижнетреугольная матрица (в которой выше главной диагонали расположены только
нули) графа сети связи. Размерность этой матрицы соответствует количеству вершин
графа (т.е. максимальному номеру вершины графа).
Изначально все клетки нижнетреугольной матрицы получают значение «ноль»
(т.е. в них записывается ноль). Далее для каждой дуги выполняют следующее. Если дуга
связывает две вершины, то в клетке нижнетреугольной матрицы, расположенной на
пересечении столбца и строки с соответствующими номерами вершин графа,
записывается единица. Так как матрица является нижнетреугольной, то каждой дуге
может соответствовать только одна клетка матрицы.
После выполнения записывания единицы для каждой дуги графа получаем
требуемую нижнетреугольную матрицу для проведения дальнейших действий.
В Регистр 4 записывают минимально допустимое число, при котором сеть может
работать с заданным уровнем надежности, при этом «0» (ноль) – это признак разрыва
сети. Уровень надежности может быть равен единице или более.
Блок 5 выполняет регистрацию (суммирование единиц) связей в каждой
прямоугольной подматрице матрицы графа связи из блока 3 и может выполняться в виде
сумматора.
Блок 6 выполняет выбор минимальных чисел из зарегистрированных в блоке 5 и
может быть выполнен в виде блока суммирования.
Интеллектуальные системы принятия решений...
«Штучний інтелект» 4’2008 305
3Т
Блок 7 выполняет сравнение установки в регистре 4 и минимального числа из
блока 6, т.е. определение места максимального потока. При указании единицы в
регистре 4 такое место практически строго определено.
Усовершенствованный алгоритм «графового» поиска
маршрута логического вывода
Рассмотрим усовершенствованный алгоритм «графового» поиска маршрута
логического вывода путем построения многополюсной сети теории графов и
определения ее минимального разреза, например, для информационной инфраструктуры
(ИИ) энергосбытовой деятельности (ЭСД). Отметим, что аналогичный подход может
применяться для поиска максимального потока в многополюсной многоуровневой
динамической сети, с учетом специфики ИИ ЭСД
Практическая ценность состоит в том, что реализация алгоритма поиска
маршрута логического вывода и других алгоритмов повышают эффективность и
конкурентоспособность энергосбытовых компаний.
Проанализируем усовершенствованный алгоритм «графового» поиска маршрута
логического вывода путем построения многополюсной сети теории графов
и определения ее минимального разреза для ИИ ЭСД. «Графовый» поиск
маршрута логического вывода основан на использовании теории графов в части
построения многополюсных сетей и определения минимального разреза (макси-
мального потока).
Данный метод называется «графовым», потому что для поиска маршрута
вывода строится граф обработки, с одной стороны, от исходных, известных значений, а
с другой стороны – от требуемых, искомых значений. Затем осуществляется анализ
связности этого графа путем поиска его минимального разреза.
Если минимальный разрез больше или равен единице, то решение существует и
определяется кратчайший, минимальный путь достижения требуемых результатов, а
затем на этой основе непосредственно запускается механизм вывода и обработки
данных, что позволит значительно экономить вычислительные ресурсы.
Если минимальный разрез равен нулю, то цепочки вывода нет, но можно
определить, значения каких переменных необходимы для уточняющего запроса, что
и является признаком «интерактивности».
Преобразование логической сети правил
в многополюсную сеть теории графов
Преобразование логической сети правил в многополюсную сеть теории графов
осуществляется следующим образом. Выделяют два типа узлов: переменные и
процедуры. Переменные преобразуются в узлы-переменные, правила – в узлы-
процедуры, а их взаимосвязи – в ребра многополюсной сети и получают двудольный
ориентированный граф. Затем выделяют две группы узлов-переменных: «входные» и
«искомые».
Построение многополюсной сети начинают с группы входных переменных,
которые образуют полюса этой сети. Искомые переменные образуют другую группу
полюсов этой сети. От «входных» полюсов осуществляют постепенное построение
многополюсной сети до «искомых» полюсов.
Тожа К.Э., Варламов О.О.
«Искусственный интеллект» 4’2008 306
3Т 3Т
Алгоритм поиска максимального потока
в многополюсной многоуровневой динамической сети
Информационная инфраструктура энергосбытовой деятельности формируется на
основе виртуальных каналов связи, арендуемых у операторов электросвязи.
В настоящее время необходимо заранее прогнозировать загрузку всех таких
каналов и формировать состав и структуру виртуальной сети связи. Для решения такой
задачи целесообразно использовать квадратичной сложности методы поиска мини-
мального разреза (максимального потока) двухполюсных и многополюсных сетей.
Виртуальную сеть каналов связи можно представить в виде некоторого много-
уровневого многотипового динамического графа: G = (V, X), в котором n – количество
вершин. Граф, в котором выделено S вершин, называют S-полюсной сетью или
многополюсной сетью.
В данном случае, полюса – это заданные и искомые логические переменные.
Разрез – это множество удаляемых вершин и ребер, которое разбивает граф на S
компонент по числу полюсов сети, при этом различные полюса находятся в различных
компонентах.
Разрез двухполюсной сети
Рассмотрим случай разреза двухполюсной сети по ребрам. Некоторым образом
все вершины нумеруются: первый полюс – 1, а второй полюс – n. Пусть значения
всех коэффициентов ребер равны 1.
Строим нижнетреугольную матрицу смежности А следующим образом:
.,1;,1;0, njniaji ij
j = 1: aij = 1 для всех nji ,1 .
njij ,1, если эти вершины связаны ребром, то aij=1.
Количество ребер графа равно сумме значений всех клеток матрицы. Если граф
разбивается на две части (в первой k вершин, а во второй остальные – (n – k)), то все
ребра, связывающие вершины из разных частей графа, принадлежат прямоугольнику,
образованному клетками нижнетреугольной матрицы, которые расположены ниже
k-й строки и левее (n – k)-го столбца.
Если граф разбит на два компонента, то практически матрица распадается на
две подматрицы, а соответствующий прямоугольник является нулевым (PRк). Для
нахождения минимального разреза в нижнетреугольной матрице необходимо
просуммировать все прямоугольники при k от 1 до (n – 1), а затем выбрать минимальный,
которому и будет соответствовать искомый разрез.
Процедура определения суммы:
n
i
iaPR
2
11
, где: k=1; j=1; n,1ji .
n
i
iaaPRPR
3
22112 , где: k=2.
n
ki
ik
k
j
kjkk aaPRPR
1
1
1
1
.
Интеллектуальные системы принятия решений...
«Штучний інтелект» 4’2008 307
3Т
Из всех PRk выбираем минимальный. Всего определяются суммы для (n – 1)-го
прямоугольника, при этом выполняется (k – 1) вычитание и (n – k) сложение, т.е. всего
(n – 1) действий.
Получаем квадратичную вычислительную сложность: (n – 1)2, т.е. О(n2).
Разрез многополюсной сети
Особенностью данного подхода является то, что для многополюсной сети
строится фактически такая же матрица, в которой по мере связности указаны все
вершины и полюса.
В полученной матрице ищем разрез 1-го полюса от всех остальных, который
соответствует прямоугольникам от 1-го до 2-го полюса. Затем определяем разрез
2-го полюса от всех и так далее.
Из всех прямоугольников между соседними полюсами выбираем минимальные
и получаем минимальный разрез многополюсной сети по ребрам. Максимальный
поток определяется именно минимальным разрезом.
Выводы
Системный анализ показал, что запатентованное устройство определения места
максимального потока в сети связи важно для интеллектуальных систем принятия
решений, планирования и управления в информационных инфраструктурах, т.к.
позволяет достоверно определить место максимального потока и оптимизировать
функционирование систем. Полезная модель создана на основе квадратичной сложности
алгоритма поиска минимального разреза многополюсных сетей теории графов.
Возможны и другие применения этого устройства.
Литература
1. Варламов О.О., Тожа К.Э. Устройство для определения места максимального потока в сети связи /
Патент на полезную модель № 72559 от 25.01.2008. Зарегистрирован 20.04.2008.
2. Режим доступа: www.ovar.narod.ru.
К.Е. Тожа, О.О. Варламов
Інтелектуальні системи ухвалення рішень і запатентований пристрій визначення в мережі
зв’язку місця мінімального розрізу і максимального потоку
У статті представлена запатентована корисна модель пристрою визначення місця максимального
потоку в мережі зв’язку, створена на основі квадратичної складності алгоритму пошуку мінімального
розрізу багатополюсних мереж теорії графів. Технічний результат застосування даної моделі полягає
в підвищенні достовірності при визначенні місця максимального потоку, яке є місцем потенційного
утруднення зв’язку в мережі.
Статья поступила в редакцию 17.07.2008.
|