Спосіб визначення маршруту в графі

Реферат: Спосіб визначення маршруту в графі, який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком. Введено правило відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. UA 92925 U (12) UA 92925 U UA 92925 U 5 Запропонована корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відомий "Спосіб послідовного призначення одиниць для наближеного рішення задачі про одномірний ранець", який вирішує задачу цілочисельного лінійного програмування з булевими змінними [1]:  f x   n  c j x j  max j 1 , (1) при виконанні умов: n  aijx j  b1 j 1 , (2)   x j  0,1 , i  1 , j  1 n , (3) , a1j  0, c j  0 . (4) 10 В даному способі як початковий розглядається нульовий вектор, в якому змінним присвоюються одиничні значення за умови, що при побудові допустимого цілочисельного рішення z 0 призначаються одиничні значення у відповідності з послідовністю  j   j  ... j , 1 починаючи з найбільшого значення. Якщо для деякого  j z0 jk k 2 n таке призначення виконати 0 15 неможливо, тоді і переходять до номеру jk 1 . Процес завершується після перегляду усіх змінних або при порушенні умови (2). Призначення одиничних значень виконується у 20 відповідності з послідовністю c j  c j  ...c j . Недоліком відомого способу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними складає 20 %. Найбільш близьким до запропонованого технічного рішення, вибрано як прототип, є "Способ решения задачи целочисленного линейного программирования с булевыми переменными на основе рангового похода", який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу, та полягає у тому, що з вершини s графа ΔD 1 2 n   r 1 будується множина шляхів m sj , j  1,n першого рангу r, що задовольняє властивості, і в 25   * r    sj    множинах визначаються шляхи максимальної довжини   за вагою функціонала c j [2]. Для кожної вершини j визначається вага  j за правилом: m r 1 sj    j  c j 1  c j  2  ...  c n ,  n  0 ; j  1 n  1 . (5) , Виключаються шляхи задовольняють нерівності:  , r sp     r r p  r,n у множині m sj поточного рангу r, довжини якої dc  sp     * r    dc  r   p  maxdc   sp  sp  c j     , (6)   30 де  p  c p 1  c p  2  ...  c n та для вершини j  n вага  j - дорівнює нулю;   - довжина шляху від вершини s до вершини р рангу r по вагах функціоналу. dc  r sp   r  r 1 Формується множина шляхів m sp , p  1,n наступного рангу, що задовольняє властивості r (5), на базі множини шляхів m sj попереднього рангу на основі рекурентного співвідношення:    r  r 1  max  r  j,p p  r  1 n j  r,n j  p , sp sj c  35 j , (7)  j,p  де - шлях з вершини s графа ΔD у вершину р, що проходить через проміжну вершину j і задовольняє правилам, тобто який одержується за рахунок приєднання до шляху r sj r sj ребра (j, p), якщо таке з'єднання не суперечить правилу відсікання неперспективних варіантів рішень. 1 UA 92925 U * r  r  1      sp     . m r  r 1 sp У визначених множинах виділяються щонайдовші шляхи Якщо визначиться декілька шляхів максимальної довжини, то серед них вибирається шлях з меншим 5 10 15 20 25 30 значенням довжини за вагою обмежень a1j . Перевіряється, чи вся множина шляхів наступного (r+1)-го рангу порожня. Якщо умова виконується, то в множинах виділяється шлях максимальної довжини і алгоритм закінчує роботу. Якщо умова не виконується, то перевіряється r=(n-1). У разі виконання рівності в множині виділяється шлях максимальної довжини і алгоритм закінчує роботу, інакше збільшується r на 1 і виконується обчислення у відповідності до формул (5-7). Недоліком способу-прототипу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу складає 12 %. В основу корисної моделі поставлена задача створити "Спосіб визначення маршруту в графі", який дозволить зменшити відносну похибку алгоритму до 8 %. Поставлена задача вирішується за рахунок того, що у спосіб-прототип, додатково введено правило відсікання неперспективних варіантів рішень на основі вибору максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком та сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. Технічний результат, який може бути отриманий при здійсненні корисної моделі полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком до 8 %. На фіг. 1 представлено граф ΔD. На фіг. 2 наведено приклад рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком. Запропонований "Спосіб визначення маршруту в графі" ґрунтується на правилі відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком та сортуванні даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. Суть способу полягає у наступному. Виконується сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження: c1 c 2 c   ...  n 1  2  n . (8)   r 1 З вершини s графа ΔD будується множина шляхів m sj , j  1,n першого рангу r, що * r      sj    задовольняє властивості, і в множинах визначаються шляхи максимальної довжини   за вагою функціонала c j . Для кожної вершини j визначається вага  j за правилом (5). m r 1 sj   35     r r r Виключаються шляхи  sp , p  r,n у множині m sj поточного рангу r, довжини якої dc  sp задовольняють нерівності (6).   r  r 1 Формується множина шляхів m sp , p  1,n наступного рангу, що задовольняє властивості r (5), на базі множини шляхів m sj попереднього рангу на основі правила відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком (7). 40 45 m r  r 1 sp * r  r  1      sp    . виділяються щонайдовші шляхи  У визначених множинах Якщо визначиться декілька шляхів максимальної довжини, то серед них вибирається шлях з меншим значенням довжини за вагою обмежень a1j . Перевіряється, чи вся множина шляхів наступного (r+1)-го рангу порожня. Якщо умова виконується, то в множинах виділяється шлях максимальної довжини і алгоритм закінчує роботу. Якщо умова не виконується, то перевіряється r=(n-1). У разі виконання рівності в множині виділяється шлях максимальної довжини і алгоритм закінчує роботу, інакше збільшується r на 1 і виконується обчислення у відповідності до формул (5-7). 2 UA 92925 U 5 Джерела інформації: 1. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. - Изд. 2-е, испр. - М.: ФИЗМАТЛИТ, 2003. - 240 с. 2. Третьяк В.Ф., Голубничий Д.Ю.,Огурцов В.В. Метод решения задачи целочисленного линейного программирования с булевыми переменными на основе рангового похода // Системи обробки інформації. Збірник наукових праць, 2009. - випуск 4 (78). - С. 152-155 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 10 Спосіб визначення маршруту в графі, який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком, який відрізняється тим, що введено правило відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. 3 UA 92925 U Комп’ютерна верстка І. Скворцова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4