О кратчайшем k-вершинном пути в ориентированном графе

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автори:	Стецюк, П.И., Долинский, Э.С., Парасюк, И.И.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Назва видання:	Теорія оптимальних рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/113024
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	О кратчайшем k-вершинном пути в ориентированном графе / П.И. Стецюк, Э.С. Долинский, И.И. Парасюк // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 95-102. — Бібліогр.: 5 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-113024
record_format	dspace
spelling	irk-123456789-1130242017-02-01T03:02:40Z О кратчайшем k-вершинном пути в ориентированном графе Стецюк, П.И. Долинский, Э.С. Парасюк, И.И. Приводится формулировка задачи смешанного булева линейного программирования для кратчайшего пути, который проходит через заданное количество вершин ориентированного графа. Даны результаты вычислительных экспериментов с программами решения задач дискретного программирования из NEOS-солвера. Обсуждается формулировка задачи для нахождения кратчайшего гамильтонового пути в ориентированном графе. Наводиться формулювання задачі змішаного булевого лінійного програмування для найкоротшого шляху, який проходить через задану кількість вершин орграфа. Наведено результати обчислювальних експериментів з програмами розв'язання задач дискретного програмування з NEOS-солвера. Обговорюється формулювання задачі для знаходження найкоротшого гамільтонового шляху в орієнтованому графі. We present the formulation of the mixed Boolean linear programming problem for the shortest path, which passes through the given number of nodes of the digraph. The results of numerical experiments of solution of discrete programming problems using NEOS-solver are given. We discuss the formulation of the problem for finding the shortest Hamiltonian path in a directed graph. 2016 Article О кратчайшем k-вершинном пути в ориентированном графе / П.И. Стецюк, Э.С. Долинский, И.И. Парасюк // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 95-102. — Бібліогр.: 5 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/113024 519.85 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Приводится формулировка задачи смешанного булева линейного программирования для кратчайшего пути, который проходит через заданное количество вершин ориентированного графа. Даны результаты вычислительных экспериментов с программами решения задач дискретного программирования из NEOS-солвера. Обсуждается формулировка задачи для нахождения кратчайшего гамильтонового пути в ориентированном графе.
format	Article
author	Стецюк, П.И. Долинский, Э.С. Парасюк, И.И.
spellingShingle	Стецюк, П.И. Долинский, Э.С. Парасюк, И.И. О кратчайшем k-вершинном пути в ориентированном графе Теорія оптимальних рішень
author_facet	Стецюк, П.И. Долинский, Э.С. Парасюк, И.И.
author_sort	Стецюк, П.И.
title	О кратчайшем k-вершинном пути в ориентированном графе
title_short	О кратчайшем k-вершинном пути в ориентированном графе
title_full	О кратчайшем k-вершинном пути в ориентированном графе
title_fullStr	О кратчайшем k-вершинном пути в ориентированном графе
title_full_unstemmed	О кратчайшем k-вершинном пути в ориентированном графе
title_sort	о кратчайшем k-вершинном пути в ориентированном графе
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
url	http://dspace.nbuv.gov.ua/handle/123456789/113024
citation_txt	О кратчайшем k-вершинном пути в ориентированном графе / П.И. Стецюк, Э.С. Долинский, И.И. Парасюк // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 95-102. — Бібліогр.: 5 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT stecûkpi okratčajšemkveršinnomputivorientirovannomgrafe AT dolinskijés okratčajšemkveršinnomputivorientirovannomgrafe AT parasûkii okratčajšemkveršinnomputivorientirovannomgrafe
first_indexed	2025-07-08T05:04:04Z
last_indexed	2025-07-08T05:04:04Z
_version_	1837053818918928384
fulltext	Теорія оптимальних рішень. 2016 95 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Приводится формулировка задачи смешанного булева линейного про- граммирования для кратчайшего пути, который проходит через заданное количество вершин ори- ентированного графа. Даны ре- зультаты вычислительных экспе- риментов с программами решения задач дискретного программиро- вания из NEOS-солвера. Обсужда- ется формулировка задачи для нахождения кратчайшего гамиль- тонового пути в ориентирован- ном графе.  П.И. Стецюк, Э.С. Долинский, И.И. Парасюк, 2016 УДК 519.85 П.И. СТЕЦЮК, Э.С. ДОЛИНСКИЙ, И.И. ПАРАСЮК О КРАТЧАЙШЕМ K-ВЕРШИННОМ ПУТИ В ОРИЕНТИРОВАННОМ ГРАФЕ Введение. Пусть ,n nD – полный орграф, где n – количество вершин, а 0ijd  – длина ду- ги, направленной от вершины i к вершине j , i j . Задано k – целое число, такое что 2 k n  . Обозначим 1( , , )ki i последова- тельность вершин в связном k -вершинном пути, где 1, , ki i – идущие по порядку вер- шины орграфа ,n nD . Он содержит ( 1)k  дуг, последовательно соединяющих вершины 1, , ki i . Связный k -вершинный путь, кото- рому соответствует наименьшая суммарная длина входящих в него ( 1)k  дуг, будем называть кратчайшим k -вершинным путем, а его длину обозначим * kd . Кратчайший n -вершинный путь ( k n ) – это кратчайший гамильтонов путь в орграфе ,n nD . В работе [1] рассмотрена задача смешан- ного булева линейного программирования для нахождения кратчайшего k -вершинного пути с зафиксированными начальной и ко- нечной вершинами. Если они неизвестны, то кратчайший k -вершинный путь можно найти с помощью решения задачи смешан- ного булева линейного программирования из [2]. Цель этой статьи – обсуждение данной зада- чи, ее сложности и других свойств. Мы так- же покажем, что использование современно- го программного обеспечения для задач дис- кретного программирования гарантирует нахождение k -вершинных путей для графов с несколькими десятками вершин за время, П.И. СТЕЦЮК, Э.С. ДОЛИНСКИЙ, И.И. ПАРАСЮК 96 Теорія оптимальних рішень. 2016 которое является достаточным для построения оперативного диалогового режи- ма. 1. Обозначения и переменные задачи. Для того, чтобы сформулировать задачу о кратчайшем k -вершинном пути, будем рассматривать орграф ,D схематически показанный на рис. 1. Он включает орграф ,n nD и вершину ,a связанную направленными дугами ( , )a i и ( , )i a с каждой вершиной i из множе- ства вершин орграфа ,n nD . РИСУНОК 1. Орграф D (включает орграф ,n nD и вершину a ) Если для всех 1,...,i n длины дуг ( , )a i и ( , )i a положить равными нулю, то нахождение кратчайшего k -вершинного пути в орграфе ,n nD равносильно нахождению в орграфе D кратчайшего цикла, который начинается и заканчи- вается в вершине a и проходит через k вершин орграфа , .n nD Пусть найден кратчайший цикл для орграфа .D Тогда дуга этого цикла, исходящая из верши- ны ,a определяет начальную вершину, а дуга, входящая в вершину ,a опреде- ляет конечную вершину для кратчайшего k -вершинного пути в орграфе , .n nD При формулировке задачи будем использовать такие переменные. Булева переменная ijx равна единице, если в цикл входит дуга, которая начинается в вершине i и заканчивается в вершине ,j и равна нулю в противном случае (т. е. дуга не входит в цикл). Обозначим aix и iax – булевы переменные такого же ти- па, как ,ijx но для дуг из вершины a в вершину i и из вершины i в вершину .a Количество переменных ,aix iax и ijx равно ( 1) ( 1)n n n n n n     . Булева переменная iy равна единице, если цикл проходит через вершину ,i и равна нулю в противном случае. Количество таких переменных равно .n Неотрица- тельная переменная ijz задает величину потока некоторого продукта от верши- О КРАТЧАЙШЕМ k -ВЕРШИННОМ ПУТИ В ОРИЕНТИРОВАННОМ ГРАФЕ Теорія оптимальних рішень. 2016 97 ны i к вершине ,j а неотрицательная переменная aiz задает величину потока от вершины a к вершине .i Количество этих переменных равно 2( 1) .n n n n   2. Формулировка задачи и ее свойства. Кратчайший k -вершинный цикл в орграфе D (кратчайший k -вершинный путь в орграфе ,n nD ) – это решение следующей задачи смешанного булевого линейного программирования: найти * , , 1 1, min i ij ij n n k ij ij y x z i j j i d d x             (1) при ограничениях 1 1 1, 1 n n ai ia i i x x      , (2) 1, 1, , , 1, , n n ai ji i ij ia i j j i j j i x x y x x y i n           , (3) 1 n i i y k   , (4) 0, 1,...,ai aiz kx i n   , (5) 1 n ai i z k   , (6) ( 1) 0, , 1,..., ,ij ijz k x i j n i j     , (7) 1, 1, , 1, , n n ai ji ij i j j i j j i z z z y i n          , (8) 0 1, 1, ,iy i n   , (9) 0 1, 0 1, 1, , , 0 1, , 1,..., ,ai ia ijx x i n x i j n i j         , (10) 0, 1,..., , 0, , 1,..., ,ai ijz i n z i j n i j     . (11) Минимизация целевой функции в (1) соответствует нахождению кратчай- шего (минимального по длине) цикла из вершины ,a который проходит через k вершин орграфа , .n nD При этом * kd соответствует длине этого цикла, что равно- значно длине кратчайшего k -вершинного пути в орграфе , .n nD Чтобы обеспе- чить связность k -вершинного цикла в орграфе ,D в задаче используется идея моделирования задачи о потоке аналогично тому, как это сделано в работе [1]. П.И. СТЕЦЮК, Э.С. ДОЛИНСКИЙ, И.И. ПАРАСЮК 98 Теорія оптимальних рішень. 2016 Теорема [2]. Если k – целое число, удовлетворяющее неравенствам 2 k n  , то для орграфа D ограничения (2) – (11) описывают все возможные циклы, которые проходят через вершину a и через k вершин орграфа , .n nD Справедливость теоремы обеспечивается за счет наличия двух групп ограниче- ний: ограничения (2) – (4), (9), (10) и ограничения (5) – (8), (11). Ограничения (2) – (4) имеют следующее объяснение. Ограничение (4) задает в точности k вершин ор- графа , ,n nD через которые должен проходить цикл из вершины .a Этим вершинам соответствуют значения 1,iy  и для них ограничения (3) описывают однократный вход в вершину и однократный выход из вершины. Ограничения (2) описывают од- нократный выход из вершины a и однократный вход в вершину .a Однако ограничения (2) – (4) в сочетании с булевыми ограничениями (9) и (10) не обеспечивают связности искомого цикла. Для 3k  на рис. 2 показаны два допустимых решения, удовлетворяющие ограничениям (2) – (4). Левое из них является связным циклом, проходящим через вершины 1 2 3, ,i i i , а правое со- стоит из двух несвязных подциклов 3,a i и 1 2,i i . РИСУНОК 2. Связный цикл (слева), два несвязных подцикла (справа) Чтобы избежать подобных ситуаций и обеспечить связность искомого цик- ла, используется группа ограничений (5) – (8), (11). Здесь ограничения (5) гарантируют перевозку продукта между вершинами a и i только тогда, если 1,aix  а ограничения (7) гарантируют перевозку продукта между вершинами i и j только тогда, если 1.ijx  Ограничения (6) и (8) означают, что из вершины a нужно развезти k единиц продукта, оставляя ровно единицу продукта в каж- дой из тех вершин орграфа , ,n nD через которые проходит искомый цикл. Задача (1) – (11) является задачей смешанного булева линейного програм- мирования. Она содержит 2 ( 1)n n переменных, из которых 2 2n n являются О КРАТЧАЙШЕМ k -ВЕРШИННОМ ПУТИ В ОРИЕНТИРОВАННОМ ГРАФЕ Теорія оптимальних рішень. 2016 99 булевыми, а 2n – неотрицательными, и 2 3 4n n  ограничений, из которых 3 4n – линейные равенства, а 2n – линейные неравенства. Задача (1) – (11) справедлива для неполного орграфа, если его дополнить отсутствующими дуга- ми со значениями длин равными сумме длин всех дуг неполного орграфа. 3. О сложности задачи. Чем меньше значение величины ,k тем меньше до- пустимых решений имеет задача (1) – (11). Поэтому, на первый взгляд, решение задачи при 2k n должно быть проще, чем при .k n Однако для современ- ных реализаций метода ветвей и границ в задачах дискретного линейного про- граммирования это оказывается не так. Данный факт подтверждают результаты вычислительных экспериментов для нахождения кратчайших путей в графе 20,20D [3] с помощью программ, имеющихся на NEOS-солвере [4]. Для описания задачи (1) – (11) использовался язык AMPL [5]. Здесь для графа 20,20D , где вершинами являются 20 наиболее посещаемых пунктов виноделия Малопольской винной дороги, рассчитаны все кратчайшие пути для 2,...,20.k  Значения их длин (в километрах) приведены во второй колонке табл. 1. С третьей по седьмую колонку приводится время решения задач (в секундах) для пяти программ из NEOS-солвера: 1t – для gurobi 6.5.0; 2t – для cplex 12.6.2.0; 3t – для xpress-mp 26.01; 4t для cbc 2.9.4; 5t – для программы mosek. Из табл. 1 видно, что время решения задачи (1) – (11) при 10k  значи- тельно больше, чем время решения задачи при 20k  . ТАБЛИЦА 1. Программы NEOS-солвера для кратчайших путей в графе 20,20D k * kd 1t 2t 3t 4t 5t 2 0.35 0.05 0.05 0.05 0.04 0.12 3 1.65 0.02 0.02 0.05 0.03 0.09 4 16.05 0.09 0.15 0.07 0.63 1.58 5 27.75 0.20 0.27 0.18 0.81 1.56 6 40.65 0.32 0.44 0.14 2.25 2.25 7 57.85 1.08 0.68 0.37 1.69 8.81 8 92.95 2.04 1.51 0.80 6.06 55.55 9 128.25 1.98 3.18 1.05 8.71 155.78 10 138.75 3.58 2.93 1.24 5.92 143.14 11 150.65 1.29 2.19 1.96 7.14 96.73 12 162.25 0.70 0.75 1.29 3.41 23.33 13 179.45 0.80 0.72 1.05 2.26 63.11 14 204.25 0.72 0.63 0.87 2.97 28.37 15 232.55 1.96 0.81 0.83 2.93 23.33 16 263.55 1.03 0.78 0.43 2.30 18.77 17 299.25 1.09 0.83 0.53 2.43 15.94 http://12.6.2.0/ П.И. СТЕЦЮК, Э.С. ДОЛИНСКИЙ, И.И. ПАРАСЮК 100 Теорія оптимальних рішень. 2016 18 346.25 1.10 0.82 0.56 1.76 14.82 19 393.85 0.60 0.66 0.31 1.34 6.05 20 447.85 0.30 0.29 0.10 1.03 2.80 Эту же тенденцию можно проследить и для нахождения кратчайших путей в графах 100,100,D о чем свидетельствуют результаты экспериментов из табл. 2. ТАБЛИЦА 2. Программа cplex 12.6.2.0 для кратчайших путей в графе 100,100D k kro100A kro100B * kd 1t 2t * kd 1t 2t 10 1118.0 134.26 9.24 1125.0 125.24 12.95 20 2858.0 138.02 30.00 2719.0 71.99 29.37 30 4609.0 675.14 50.25 4397.0 116.02 37.50 40 6369.0 85.82 44.42 6366.0 220.44 48.81 50 8326.0 161.23 113.14 8464.0 387.09 132.91 60 10409.0 1192.27 116.66 10578.0 437.02 209.30 70 12548.0 280.69 142.33 12676.0 213.77 136.47 80 14700.0 380.12 119.73 14943.0 159.36 53.16 90 17012.0 307.46 82.88 17538.0 593.05 62.12 100 20405.0 654.17 43.70 20912.0 101.53 33.16 Здесь рассматриваются два известных графа kro100A и kro100B из библио- теки TSPLIB. Для них в колонках 2 и 5 даны значения длин кратчайших путей при значениях 10,20,...,90,100.k  Здесь 1t и 2t – затраты по времени (в секун- дах) для программы cplex 12.6.2.0 (на 04.03.2016) для двух форм записи задачи (1) – (11). Они вычислялись с помощью функции "_solve_time". Первая форма соответствует задаче (1) – (11) и более экономна по количеству ненулевых эле- ментов, чем вторая форма, где ограничения (2) и (3) переписаны так, что вклю- чают равенство для входящих в вершину и выходящих из вершины дуг. 4. Кратчайший гамильтонов путь. Если ,k n то из ограничения (4) сле- дует, что все булевы переменные iy равны единице, т. е. n -вершинный путь в орграфе ,n nD совпадает с гамильтоновым путем. Нахождению кратчайшего га- мильтонова пути соответствует решение следующей задачи смешанного булева линейного программирования: найти * , , 1 1, min i ij ij n n k ij ij y x z i j j i d d x             (12) при ограничениях http://12.6.2.0/ http://12.6.2.0/ О КРАТЧАЙШЕМ k -ВЕРШИННОМ ПУТИ В ОРИЕНТИРОВАННОМ ГРАФЕ Теорія оптимальних рішень. 2016 101 1 1 1, 1 n n ai ia i i x x      , (13) 1, 1, 1, 1, 1, , n n ai ji ij ia j j i j j i x x x x i n           , (14) 0, 1,...,ai aiz nx i n   , (15) 1 n ai i z n   , (16) ( 1) 0, , 1,..., ,ij ijz n x i j n i j     , (17) 1, 1, 1, 1, , n n ai ji ij j j i j j i z z z i n          , (18) 0 1, 0 1, 1, , , 0 1, , 1,..., ,ai ia ijx x i n x i j n i j         , (19) 0, 1,..., , 0, , 1,..., ,ai ijz i n z i j n i j     . (20) Здесь ограничения (15) означают, что по дуге из вершины ,a для которой 1,aix  перевозится не больше, чем n единиц продукта. Поскольку в каждой из тех вершин орграфа ,n nD , через которые проходит путь, требуется оставлять ровно единицу продукта, то ограничения (17) означают, что по дуге между вер- шинами i и j , если 1ijx  , достаточно перевозить не более, чем ( 1)n единиц продукта. Если в ограничениях (17) границу на потоки по дугам сделать равны- ми ,n то задачу для нахождения гамильтонового пути можно записать в более экономной форме, чем задача (12) – (20). Для орграфа, включающего орграф ,n nD и «нулевую» вершину, эта задача имеет следующий вид: найти * , , 1 1, min i ij ij n n k ij ij y x z i j j i d d x             (21) при ограничениях 0, 0, 1, 1, 0,1, , n n ji ij j j i j j i x x i n         , (22) 0, , 0,1,..., ,ij ijz nx i j n i j    , (23) 0 1 n i i z n   , (24) 0, 1, 1, 1, , n n ji ij j j i j j i z z i n         , (25) 0 1, 0, , 0,1,..., ,ij ijx z i j n i j     . (26) Выводы. Для нахождения кратчайшего пути, который проходит через заданное количество вершин полного орграфа в статье рассмотрена формули- П.И. СТЕЦЮК, Э.С. ДОЛИНСКИЙ, И.И. ПАРАСЮК 102 Теорія оптимальних рішень. 2016 ровка задачи смешанного булева линейного программирования. Она справедли- ва для неполного орграфа, если его дополнить отсутствующими дугами, а зна- чения длин для них установить равными сумме длин дуг неполного орграфа. Если путь должен проходить через все вершины орграфа, то решение построен- ной задачи определяет кратчайший гамильтонов путь в ориентированном графе. Для небольших орграфов предложенную модель можно использовать при выборе оптимальных маршрутов в режиме реального времени. Ее можно при- менять и тогда, когда начальная и конечная вершины заданы. Для этого доста- точно зафиксировать равными единице значения дуг, которые связывают вер- шину a с начальной и конечной вершинами орграфа ,n nD . Работа выполнена при поддержке проектов НАН Украины (№ 0114U001055) и МОН Украины (№ 0115U001906). П.І. Стецюк, Е.С. Долинський, І.І. Парасюк ПРО НАЙКОРОТШИЙ k -ВЕРШИННИЙ ШЛЯХ У ОРІЄНТОВАНОМУ ГРАФІ Наводиться формулювання задачі змішаного булевого лінійного програмування для найко- ротшого шляху, який проходить через задану кількість вершин орграфа. Наведено результати обчислювальних експериментів з програмами розв'язання задач дискретного програмування з NEOS-солвера. Обговорюється формулювання задачі для знаходження найкоротшого гамільтонового шляху в орієнтованому графі. P.І. Stetsyuk, E.S. Dolynskyi, I.I. Parasiuk ON THE SHORTEST K-NODE PATH IN A DIRECTED GRAPH We present the formulation of the mixed Boolean linear programming problem for the shortest path, which passes through the given number of nodes of the digraph. The results of numerical experi- ments of solution of discrete programming problems using NEOS-solver are given. We discuss the formulation of the problem for finding the shortest Hamiltonian path in a directed graph. 1. Стецюк П.И. Формулировки задач для кратчайшего k-вершинного пути и кратчайшего k-вершинного цикла в полном графе // Кибернетика и системный анализ. – 2016. – № 1. – С. 78 – 82. 2. Стецюк П.И., Долинский Э.С. Кратчайший k-вершинный путь в ориентированном графе // Інформатика та системні науки (ІСН-2016): матеріали VII Всеукр. наук.-практ. конф. за міжнародною участю (м. Полтава, 10 – 12 березня 2016 року) /за ред. Ємця О.О. – Полтава: ПУЕТ, 2016. – С. 293 – 299. 3. Стецюк П.И., Лефтеров А.В., Федосеев А.И. Кратчайший k-вершинный путь // Компью- терная математика. – К.: Ин-т кибернетики имени В.М. Глушкова НАН Украины. – 2015. – № 2. – С. 3 – 11 4. NEOS Solver [Электронный ресурс]: http://www.neos-server.org/neos/solvers/. – Режим доступа: свободный. http://www.neos-server.org/neos/solvers/ О КРАТЧАЙШЕМ k -ВЕРШИННОМ ПУТИ В ОРИЕНТИРОВАННОМ ГРАФЕ Теорія оптимальних рішень. 2016 103 5. Fourer R. AMPL A Modeling Language for Mathematical Programming, Second Edition / R. Fourer, D. Gay, B. Kernighan. – Belmont: Duxburry Press, 2003. – 517 p. Получено 12.04.2016

О кратчайшем k-вершинном пути в ориентированном графе

Репозитарії

Схожі ресурси