О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности
В статье показаны некоторые возможности нового миварно-матричного подхода к решению задач на графах и гиперграфах. Миварно-матричный подход основывается на отказе от полного перебора и построения специальных матриц, позволяющих анализировать «весь лабиринт графа». Подход позволяет снизить вычисли...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/7140 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности / О.О. Варламов // Штучний інтелект. — 2008. — № 3. — С. 626-629. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859619674656866304 |
|---|---|
| author | Варламов, О.О. |
| author_facet | Варламов, О.О. |
| citation_txt | О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности / О.О. Варламов // Штучний інтелект. — 2008. — № 3. — С. 626-629. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| description | В статье показаны некоторые возможности нового миварно-матричного подхода к решению задач на
графах и гиперграфах. Миварно-матричный подход основывается на отказе от полного перебора и
построения специальных матриц, позволяющих анализировать «весь лабиринт графа». Подход позволяет
снизить вычислительную сложность алгоритмов, считавшихся полно-переборными (NP-полными), до
квадратичной и даже линейной.
У статті висвітлені деякі можливості нового міварно-матричного підходу до розв’язання задач на
графах і гіперграфах. Міварно-матричний підхід ґрунтується на відмові від повного перебору і
побудови спеціальних матриць, що дозволяють аналізувати «весь лабіринт графа». Підхід дозволяє
знизити обчислювальну складність алгоритмів, які вважались повно-переборними (NP-повними), до
квадратичної або навіть лінійної.
|
| first_indexed | 2025-11-29T01:09:23Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 3’2008 626
8В
УДК 007.04
О.О. Варламов
Московская академия рынка труда и информационных технологий, Россия
ovar@narod.ru
О миварно-матричном подходе
к решению задач поиска
минимального разреза и коммивояжера
в целях снижения вычислительной сложности
В статье показаны некоторые возможности нового миварно-матричного подхода к решению задач на
графах и гиперграфах. Миварно-матричный подход основывается на отказе от полного перебора и
построения специальных матриц, позволяющих анализировать «весь лабиринт графа». Подход позволяет
снизить вычислительную сложность алгоритмов, считавшихся полно-переборными (NP-полными), до
квадратичной и даже линейной.
Введение
В настоящее время актуальным является решение различных задач в теории графов
со снижением вычислительной сложности. Рассмотрим некоторые возможности нового
миварно-матричного подхода к решению задач на графах и гиперграфах, значительно
снижающие вычислительную сложность. Решение основывается на отказе от полного
перебора всех вариантов путем «подъема над плоскостью лабиринта графа» и построения
специальных матриц, позволяющих анализировать «весь лабиринт графа» в комплексе и
быстро находить требуемые решения. Подход позволяет снизить вычислительную
сложность алгоритмов, считавшихся полно-переборными (NP-полными), до квадратич-
ной и даже линейной.
Постановка задачи
Решаемая задача – снижение вычислительной сложности решения некоторых
классов задач на графах. Некоторые задачи теории графов можно решать на основе
миварно-матричного подхода со значительным снижением вычислительной слож-
ности алгоритмов [1]. Например, классическая задача поиска минимального разреза
многополюсной сети теории графов или максимального потока на основе нового
подхода решается с квадратичной сложностью. Данный алгоритм запатентован в
виде полезной модели [2].
Основы миварно-матричного подхода
Миварно-матричный подход основан на представлении графа в виде специальной
нижнетреугольной матрицы, в которой отражены все вершины и ребра между ними.
Такой подход работает с ненаправленными ребрами графа, но возможно расширение
матрицы до квадратной для учета направленности в орграфах. Отметим, что на основе
этого подхода предложен линейной вычислительной сложности матричный метод поиска
маршрута логического вывода [1].
О миварно-матричном подходе к решению задач поиска минимального разреза…
«Штучний інтелект» 3’2008 627
8В
Применение миварно-матричного подхода
к решению задачи коммивояжера
Рассмотрим применение миварно-матричного подхода к решению задачи комми-
вояжера. Имеется n городов-вершин графа (v1, v2, ..., vi, ...,vn) и заданы расстояния (веса
ребер) между ними – cij. Выезжая из первого города, коммивояжер должен побывать в
каждом городе по одному разу и вернуться в первый город – получаем полный цикл без
повторений. Требуется определить порядок, в котором следует объезжать города, чтобы
суммарное расстояние было минимальным. Каждому циклу соответствует некая сумма
весов всех ребер этого цикла. Задача о коммивояжере из-за условия цикличности не
сводится к транспортной и является типичной задачей дискретной математики с резко
выраженными комбинаторными свойствами.
Итак, начнем построение нижнетреугольной матрицы: первая вершина – это
исходная точка, в которую потом необходимо вернуться. Далее, включаем в нашу матри-
цу в порядке возрастания весов ребер все связанные с ней одним ребром вершины и
проставляем соответствующие значения cij. Если веса ребер одинаковы, то выбираем
произвольную вершину, т.е. первую попавшуюся. В дальнейшем в подобных случаях
поступаем аналогично. Если остались еще вершины, то берем вторую вершину и простав-
ляем аналогично все неучтенные ранее вершины. Повторяем эту процедуру аналогично
для всех следующих вершин графа. Есть два возможных выхода: либо все вершины
включены в матрицу, либо остались вершины, которые не связаны ни с одной из нашей
матрицы, что сразу же означает отсутствие решения, т.к. граф будет не связанным.
Анализ матрицы и формальный расчет
Если матрица построена и включает все вершины, то проводим формальный расчет
наличия исходящих ребер из каждой вершины: начинаем суммирование и идем слева
направо по строке с номером соответствующей вершины, доходим до главной диагонали
и переходим сверху вниз по столбцу с таким же номером до самого конца матрицы. Если
по ходу мы встречаем значение (вес ребра), отличное от нуля, то прибавляем единицу к
признаку количеств ребер у соответствующей вершины.
Если хоть для одной вершины значение этого признака меньше двух, то задача
не имеет решения, т.к. найдена вершина с одним ребром и из нее нельзя «выйти»
отличной от «входа» дорогой (по условиям задачи: в каждом городе можно побывать
только один раз, т.е. в каждом городе должно быть не менее 2 дорог, а у каждой
вершины не менее 2 ребер). Если для всех вершин признак количества ребер равен 2,
то существует только одно решение (точнее, два симметричных, например: v1,v2,v3,
v4,v5,v6,v7,v8,v9,v10,v1 и v1,v10,v9,v8,v7,v6,v5,v4,v3,v2,v1 – это обход в разные
стороны). Следовательно, если существует одно решение, то всегда должно сущест-
вовать и «обратное» к нему симметричное решение. Значит, количество решений
всегда будет четным. В дальнейшем целесообразно рассматривать только первые из
двух симметричных решений, заранее определив, что первый шаг будем делать по
минимальной из двух возможных дорог одного «цикла». Если веса ребер одинаковы,
то выбираем ребро к вершине с меньшим номером.
Итак, получаем матрицу, в которой все признаки количества ребер более или
равны 2. Причем хотя бы одно значение строго больше 2. Теперь начинаем искать
другие возможные циклы. Основная идея состоит в постепенном исключении из
Варламов О.О.
«Искусственный интеллект» 3’2008 628
8В
матрицы тех вершин, которые включаются в «возможное решение», что позволяет
снижать размерность матрицы (задачи). В случае выбора из нескольких возможных
ребер, будем всегда сначала выбирать минимальное ребро по весу, а в случае
равенства весов – с наименьшим номером связанной вершины.
Необходимо только четко фиксировать те вершины, через которые в результате
можно попасть в исходную первую вершину для замыкания цикла. Такие вершины
должны замыкать «возможное решение». В противном случае такое «возможное
решение» определяется как «нереализуемое» и, при необходимости, фиксируется в
специальной области для исключения повтора «нереализуемых» решений и/или его
фрагментов. Такой прием позволит значительно сократить наш «направленный»
перебор возможных вариантов решения задачи.
Отметим, что после каждого перехода и фиксации некоторой вершины в
«возможном решении» необходимо провести проверку, аналогичную приведенной
выше, на существование решения: вершины с одним ребром (кроме вершин,
связанных с «исключенными» вершинами, которые специально фиксируются),
связность графа и т.п. Так как размерность матрицы после фиксации новой вершины
в «возможном решении» каждый раз снижается, то поиск становится вычислительно
менее сложным, при этом можно соответствующим образом использовать всю ранее
полученную информацию, которая должна накапливаться.
Оценка минимальных и максимальных значений
суммарных расстояний искомого цикла
Представляется целесообразным заранее оценить возможные минимальные и
максимальные значения суммарных расстояний искомого цикла. Например, можно
выбрать для каждой вершины по одному минимальному (максимальному) значению
весов ребер, примыкающих к ней, и суммировать их, получив минимальное (макси-
мальное) суммарное расстояние цикла. Получив, таким образом, минимальную и
максимальную границы требуемого решения, в дальнейшем можно оценивать
оптимальность получаемых решений по некоторому, заранее заданному, значению
отклонения от возможного минимума. Интервал между минимумом и максимумом
можно использовать для выборки относительных отклонений при анализе достаточ-
ности поиска решений.
Например, если в процессе анализа получаем некоторое решение (цикл),
которое не превышает минимально возможное значение на заданное отклонение, то
решение можно считать найденным, а задачу – решенной. Такой подход позволит
значительно сократить время решения задачи за счет небольшого и допустимого
снижения точности.
Деление оптимизационной задачи
Тогда наша оптимизационная задача может быть разделена на две большие части:
1) поиск возможного решения и 2) оптимизация найденного решения и поиск минималь-
ного (максимального) и/или оптимального решения. Практика показывает, что в реальной
жизни при жестких ограничениях на время принятия решения важно, прежде всего, найти
решение, а уже потом, если позволяет время, то и оптимизировать его. При этом важно
как можно быстрее определить факт существования такого решения.
О миварно-матричном подходе к решению задач поиска минимального разреза…
«Штучний інтелект» 3’2008 629
8В
Как показано в начале, миварно-матричный подход именно так и работает:
проверяем факт существования решения, находим некое решение и оцениваем его, а
затем, при необходимости и возможности, ищем другие решения и сравниваем их по
критерию оптимальности.
В процессе направленного перебора после нахождения некоторого «текущего»
(оптимального) решения, все остальные возможные решения можно заранее в про-
цессе поиска сравнивать с этим «текущим», а если сумма весов возможного решения
на некотором этапе превышает сумму «текущего», то проверку такого возможного
решения прекращают и переходят к следующему.
Направления дальнейших исследований
Исследования возможностей миварно-матричного подхода для решения задачи
коммивояжера продолжаются. Как показано выше, одно из возможных существую-
щих решений находится практически сразу, еще на этапе построения матрицы.
Варианты задачи, которые не имеют решения, также определяются на предвари-
тельном этапе с минимальной сложностью. Оптимизация решений требует дополни-
тельного анализа.
Выводы
Показаны новые возможности миварно-матричного подхода к решению задач
на графах, снижающие вычислительную сложность. Подход основан на отказе от
полного перебора всех вариантов путем «подъема над плоскостью лабиринта графа»
и построения специальных матриц, позволяющих анализировать «весь лабиринт
графа» в комплексе и быстро находить требуемые решения, что позволяет снизить
вычислительную сложность алгоритмов, считавшихся NP-полными, до квадратич-
ной и даже линейной.
Литература
1. Сайт Варламова О.О. – Режим доступа: www.ovar.narod.ru.
2. Варламов О.О., Тожа К.Э. Устройство для определения места максимального потока в сети связи /
Патент на полезную модель № 72559 от 25.01.2008. Зарегистрирован 20.04.2008.
О.О. Варламов
Про міварно-матричний підхід до розв’язання задач пошуку мінімального розрізу та комівояжера з
метою зниження обчислювальної складності
У статті висвітлені деякі можливості нового міварно-матричного підходу до розв’язання задач на
графах і гіперграфах. Міварно-матричний підхід ґрунтується на відмові від повного перебору і
побудови спеціальних матриць, що дозволяють аналізувати «весь лабіринт графа». Підхід дозволяє
знизити обчислювальну складність алгоритмів, які вважались повно-переборними (NP-повними), до
квадратичної або навіть лінійної.
Статья поступила в редакцию 17.07.2008.
|
| id | nasplib_isofts_kiev_ua-123456789-7140 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-11-29T01:09:23Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Варламов, О.О. 2010-03-24T17:56:03Z 2010-03-24T17:56:03Z 2008 О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности / О.О. Варламов // Штучний інтелект. — 2008. — № 3. — С. 626-629. — Бібліогр.: 2 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7140 007.04 В статье показаны некоторые возможности нового миварно-матричного подхода к решению задач на графах и гиперграфах. Миварно-матричный подход основывается на отказе от полного перебора и построения специальных матриц, позволяющих анализировать «весь лабиринт графа». Подход позволяет снизить вычислительную сложность алгоритмов, считавшихся полно-переборными (NP-полными), до квадратичной и даже линейной. У статті висвітлені деякі можливості нового міварно-матричного підходу до розв’язання задач на графах і гіперграфах. Міварно-матричний підхід ґрунтується на відмові від повного перебору і побудови спеціальних матриць, що дозволяють аналізувати «весь лабіринт графа». Підхід дозволяє знизити обчислювальну складність алгоритмів, які вважались повно-переборними (NP-повними), до квадратичної або навіть лінійної. ru Інститут проблем штучного інтелекту МОН України та НАН України Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности Про міварно-матричний підхід до розв’язання задач пошуку мінімального розрізу та комівояжера з метою зниження обчислювальної складності Article published earlier |
| spellingShingle | О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности Варламов, О.О. Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| title | О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности |
| title_alt | Про міварно-матричний підхід до розв’язання задач пошуку мінімального розрізу та комівояжера з метою зниження обчислювальної складності |
| title_full | О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности |
| title_fullStr | О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности |
| title_full_unstemmed | О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности |
| title_short | О миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности |
| title_sort | о миварно-матричном подходе к решению задач поиска минимального разреза и коммивояжера в целях снижения вычислительной сложности |
| topic | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| topic_facet | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/7140 |
| work_keys_str_mv | AT varlamovoo omivarnomatričnompodhodekrešeniûzadačpoiskaminimalʹnogorazrezaikommivoâžeravcelâhsniženiâvyčislitelʹnoisložnosti AT varlamovoo promívarnomatričniipídhíddorozvâzannâzadačpošukumínímalʹnogorozrízutakomívoâžerazmetoûznižennâobčislûvalʹnoískladností |