розглядається алгоритм локалізації лінійної функції, заданої на конфігурації сполучень, з урахуванням її подання у вигляді неориентированного графа. Наведено числовий приклад реалізації алгоритму.

Анотація наукової статті з математики, автор наукової роботи - Нагірна А. М.


This paper considers the localization algorithm of a linear function on the configuration of combinations taking into account its representation in the form of an undirected graph. A numerical example of algorithm realization is given.


Область наук:

  • Математика

  • Рік видавництва: 2014


    Журнал: Інститут проблем математичних машин і системи


    Наукова стаття на тему 'локалізація значення лінійної Функції, заданої на множіні сполучень'

    Текст наукової роботи на тему «локалізація значення лінійної Функції, заданої на множіні сполучень»

    ?УДК 519.8 А.М. НАГ1РНА *

    ЛОКАЛ1ЗАЦ1Я значення Л1Н1ЙНО1 ФУНКЦП, ЗАДАНО1 НА МНОЖІН1 сполучення

    Украшській державний унiверситет фшанав та мiжнародноl торгiвлi, Кі! В, прикрашаючи

    Анотація. Розглядаеться алгоритм локалгзацІлШйног функцп, заданоi на конфггурацІ сполучень, з урахуванням ii представлення у вігляд1 неор1ентованого графа. Наведено числовий приклад реа-л ^ зацІ алгоритму.

    Ключовi слова: функція, локал1зац1я, конф1гурац1я сполучень, генерування, неор1ентованій граф, дерево, поддерево, корти, гамтьтотв шлях.

    Анотація. Розглядається алгоритм локалізації лінійної функції, заданої на конфігурації сполучень, з урахуванням її подання у вигляді неорієнтованого графа. Наведено числовий приклад реалізації алгоритму.

    Ключові слова: функція, локалізація, конфігурація поєднань, генерування, неорієнтований граф, дерево, поддерево, корінь, гамільтонів шлях.

    Abstract. This paper considers the localization algorithm of a linear function on the configuration of combinations taking into account its representation in the form of an undirected graph. A numerical example of algorithm realization is given.

    Keywords: function, localization, configuration of combinations, generation, undirected graph, tree, subtree, root, Hamilton path.

    1. Вступ

    Оптім1зацшш комбшаторш задач1 е одними з найбшьш Важко з Обчислювальна! точки зору. У бшьшосп віпадюв методи ix розв'язання зводяться до полного перебору вар1ант1в, что НЕ е ефективного для задач велике! розм1рносп. Тому при розв'язанш практичних завдань часто вінікае необхщшсть розробляті нов1 та удосконалюваті юнуюч1 методи, як точш, так i набліжеш, як були б застосовш до завдань бшьшо! розм1рносп, ШЖ метод полного перебору [1, 2].

    У процес розробки i реалiзащi алгоритму природним чином розкривають влади-сприймали, что вщображають комбшаторш характеристики, яю вікорістовуваліся в модіфша-цп з новімі шдходамі [3-5]. Графи як абстрактш математічнi моделi можна використо-вувати при розв'язаннi комбiнаторніх завдань рiзноi розмiрностi, оскiльки смороду е уяви багатогранно! Структури питань комерційної торгівлі комбшаторніх конфiгурацiй. Тому представлення комбшаторніх множини у виглядi графiв дозволяе отріматі новi пiдході та методи вірь шення [6-8].

    При врахуванш взаємозв'язку мiж комбiнаторнімі конфiгурацiямі i 1х графові моделі вівчаються структури властивостi допустимо! областi, якi забезпечують знахо-дження розв'язки задачi за лiченi кроки.

    Дана робота продовжуе дослщження робiт [6-10]. В нш опісуеться! Застосування нового пiдходу до розв'язання комбшаторніх завдань локалiзацii функцп на комбшаторнш конф ^ урацп сполучень.

    2. Алгоритм локалiзацil значень лшшноУ функцп на конф ^ рацн сполучень

    Нехай дано множини A = (1,2, ..., n). Сполучення без повторень з n елементiв по r - це r -елементна пiдмножіна множини A. Оскiльки порядок запису елеменпв множини неюто-тній, то запішемо елементи в кожному сполученш у порядку зростання. сполучення

    © НАПрН А.М., 2014

    ISSN 1028-9763. Математічш машини i системи, 2014 року, № 3

    ( «1, $ 2, ..., аг) розглядатімемо як рядок чисел а ^, ..., аг, де а1 < «2 < ... < аг. Сп - кшь-кють усiх сполучень без повторень з п елементiв по г, де п, г - додатш цiлi числа, при-чому г < п. За данім сполучення можна найти Наступний вщповщно до лексікографiчно-го порядку.

    Алгоритм побудова лексікографiчно следующего сполучення [5]:

    1. Знайте в рядку а \, «2, ..., аг перший праворуч елемент а ^ такий, что аг- ф п - г + /.

    2. Для знайденого елемента Виконати прісвоювання а ^ = аг- +1.

    3. Для] = I +1,1 + 2, ..., г Виконати а] - = а ^ +] -1 або а ^ = а] -1 +1.

    Наступний алгоритм генеруе нд до - елементнi пiдмножіні так, что Кожна наступна тдмножіна утворюеться з попередньо'1 з відаленням одного елемента i Додавання шшо-го. Розглянемо алгоритм у рекурсівнш формі

    Позначімо через 0 (п, к) список, Який травні нд до - елементн пiдмножіні множини {1, ..., п}, в якiй дерло пiдмножіною е {1, ..., до}, последнего - {1,2, ..., до - 1, п}, i Кожна наступна тдмножіна утворюеться з попередньо'1 з відаленням Деяк елемента i Додавання іншого. Зазначімо, что если 0 (п - 1, к) i О (п - 1, до - 1) Вже побудоваш, то 0 (п, к) мо-

    жна

    : *

    візначіті

    таким

    чином:

    в (п, к) = в (п - 1, до - 1), О * (п - 1, до - 1) і {п},

    де

    Про * (п - 1, до - 1) і {п} означае список, Утворення з О (п - 1, до - 1) змшою порядку елемешів списку на зворотнього та наступна Додавання елемента п до кожно'1 множини. Списком О (п, к), як i у випадка генерування вах тдмножін, можна поставити у вщповщшсть де-який гамiльтонiв шлях у графi [6].

    Розглянутi вищє методи генерування комбшаторнох конф ^ урацп сполучень НЕ так-ють можлівостi побудуваті упорядкування за значенням щльово'1 функцп. Тому слiд різок-лянуті новi методи генерування комбшаторнох конф ^ урацп сполучень, як дають можли-вiсть, у залежносп вiд складностi задачi, представіті елементи комбшаторно! конф ^ урацп у виглядi графа.

    Даній метод генерування полягае у віборi елементiв з задано! упорядковано! множини за зростанням, тобто вібіраються елементи для прикладу по два - перший, другий; перший, третш; перший, четвертий i т.д. Таким чином будует верхнш тдграф загально-го графа послщовносп, далi - другий, третiй; другий, четвертий т.д.

    *-

    12 13

    23 24 25 26 27 28

    34

    35

    45

    36

    46

    56

    -* ->

    14 15 16 17 18

    37

    47

    57

    38

    48

    58

    67 68

    1

    Мал. 1. Граф сполучень з п по 2

    1п

    2п

    3п

    4п

    5п

    6п

    пп

    Дерево на рис. 1 можна представіті у виглядi Расписание на тддерева, тодi Кожне тддерево формуеться з вершин, в якіх елемент на последнего мющ фiксуeться i е вібро-ним з початково! множини про ^, а 2, ... ап як максимальний, а залишуся перебіраються рекурсією-вним методом.

    Слiд Зазначити, что данє дерево е орiентованім, в якому визначення корiнь - най-нижчих вершина последнего тддерева i яка е лексікографiчно бшьша за всiх iнших.

    Тодi алгоритм побудова следующего сполучення полягае у Виконання таких крокiв.

    Крок 1. Знайте в рядку а1, а2, ... аг перший праворуч елемент а1 такий, что АI ф п - г + г.

    Крок 2. Для знайденого елемента Виконати прісвоювання а ^. = Аг +1.

    Крок 3. Для] = г + 1, г + 2, ..., г Виконати а; = аг- +] - г (або, что ті ж самє,

    Даній алгоритм дае можлівють будуваті Наступний по порядку сполучення. Рядок чисел, Яким подано лексікографiчно Наступний сполучення, вiдрiзняеться вщ рядка, что зо-зображують данє сполучення, з позіцп г, бо в даного сполучення в позіщях г +1, г + 2, ..., г е

    максимально можлівi числа. Отже, аг +1 - найменша можливе число, Пожалуйста можна Записати в позіщю г, если Хочемо отріматі сполучення бiльше вщ даного. Тодi аг + 2, ..., аг + г - г +1 - найменша можлівi числа, якi можна Записати в позіщях вщ г +1 до

    Важлівють запропонованого методу генерування комбшаторно! конф ^ урацп спо-лучанин у тому, что одержуемо граф (дерево), Який можна використовуват для розв'язування комбшаторніх завдань, оскшькі граф складаеться iз УАХ елементiв сполучення.

    Метод, что об'єднує засоби комбшаторного аналiзу та теорп графiв, передбачало по-слiдовне Виконання таких пункпв [9]:

    - вибiр способу генерування у певнш послiдовностi всiх елеменпв задано! комбша-торно! конф ^ урацп, Який найбшьше прістосованій до задано! функцп цiлi;

    - представлення множини комбшаторно! конф ^ урацп у виглядi орiентованого графа, де дуга вщповщае спадання значень щльово! функцп;

    - побудову полiномiального алгоритму розв'язки задачi на частково упорядкованіх вершинах графа.

    Цей метод Було застосовано для розв'язання задач з лшшною та дробові-лшшною цiльовімі функщямі на перестановках, розбіттях, комбiнацiях та розмщеннях. Продо-втискаючись дослiдження з метою создания вщповщного алгоритму для розв'язання комбша-торно'1 задачi на конф ^ рацп сполучень.

    Згiдно з методом генерування, елементи множини конф ^ урацп сполучень можна зобразіті у виглядi дерева, неорiентованого графа, что НЕ травні ци ^ в, тобто такого, в якому Кожна пара вершин з'еднана одним пробачимо шлях - Ланцюг.

    Дерево можна орiентуваті, Вибравши для цього довшьну вершину, як корiнь i ребрах пріпісаті таку орiентацiю, щоб Кожна вершина з'еднувалася з коренем тшькі одним пробачимо Шляхи. Тодi елементи конф ^ урацп сполучень будут розмщеш у виглядi орiен-товно дерева, де тддерево визначаеться початкових елементом у вершить.

    Слщ Зазначити, что при розв'язування екстремальних завдань на множить сполучень НЕ травні значення порядок розмщення елеменпв, а тшькі 1'х вибiр з віхщно! множини, в якiй елементи впорядковаш за зростанням, тому екстремального значення функцп всегда можна візначіті.

    г.

    Нехай задано числове значення функцп f (xq) = yo. Необхщно найти точки конф гурацп сполучень, в якіх досягаеться данє числове значення.

    Алгоритм локалiзащi значення лшшно'1 функцп на конф ^ урацп сполучень полягае

    У:

    1) формуванш множини сполучень: Aj (aj, a2, ..., a ^), i = 1, ..., к; введеннi n, r (n > r),

    r n!

    візначенш кiлькостi елементiв Cn = -;

    n до! (n - к)!

    2) побудовi базового дерева конф ^ урацп сполучень: візначенш кшькосп вершин

    базового дерева C1n, пiддерев (пiдплощін) d = n - r +1;

    3) візначенш початково'1 i кшцево'1 крайнiх точок пiдграфiв та знаходженш max f (Xj), min f (xi) у ціх точках вщповщного пiддерева;

    4) візначеннi множини точок пщдерева, что задовольняють умову f (Xj)> f (x0), де

    x0 - точка, для яко'1 f (x0)> y0, а xi, i e Nk - множини точок, значеннi щльово'1 функцп

    f (x), у якіх бшьше заданого;

    5) візначенш множини вершин тддерева, для якіх віконуеться Умова f (xj) < f (x0), де x0 - точка, для яко'1 'віконуеться Умова f (x0) < y0; а xj, j e Nn-k - множини точок, для якіх значення щльово'1 функцп f (x) менше заданого;

    6) знаходженш множини пщдерев, Утворення Шляхом перетин множини п. 5-6;

    7) формуванш множини точок - елеменпв сполучень, что задовольняють умовi f (xo) = Уо. Если всi точки знайденi, тобто среди множини тддерев візначеш, i завдання розв'язано. В iншому випадки - перехщ до следующего п. 8;

    8) візначенш тддерева, для которого віконуеться Умова f (xj) < yo < f (xj);

    9) n: = n -1, перехщ до п. 1.

    Розглянемо числовий приклад! Застосування алгоритму.

    3. Приклад! Застосування алгоритму

    Дано цшьову функщю I (х) = х2 + Х3 + х2х3 на конф ^ урацп сполучень СП, де п = 6,

    АI = (1,2,3,4,5,6), г = 3. Тодi Сб = 20 - кшькють точок дерева. Вiдповiдно, кшьюсть пiддерев у де-ревi рiвна d = 4. Визначення значення функцп 'I (х) = 47.

    Необхщно найти точки - елементи конф ^ урацп сполучень, в якіх досягаеться завдання значення щльово '' функцп.

    ?6

    Розв 'язання

    5б Для конф ^ урацп сполучень елементи множини зобразімо у виглядi дерева, что складаеться iз трьох пiддерев. Елементи конф ^ урацп сполучень, 56 розмiщуемо у виглядi неорiентованого графа без ціклiв. Вібіраемо довшьну вершину як корiнь для орiентацп дерева. Ребрах пріпісуемо таку 456 орiентацiю, щоб Кожна вершина з'еднувалася з Рис. 2. Огандартній вигляд базового коренем тiльки одним пробачимо Шляхи. Елементи дерева Про конф1гурацп сполучень З |

    конф ^ урацп сполучень будут розмщет у виглядi орieнтовного дерева, де пiддерево ві-значаеться початкових елементом у вершить.

    Вiдповiдно, базове орiентовне дерево iз трьох пiддерев (пiдплощін), Утворення мно-

    жіною сполучень без повторень

    / (1,2,3) = 11 / (2,3,4) = 26 / (3,4,5) = 47

    Про,

    О2

    Про

    / (1,5,6) = 41

    / (2,5,6) = 52

    / (3,5,6) = 63

    Про

    з шести елементiв по три, буде мати такий вигляд.

    На рис. 3 структурна схема дерева Про конф ^ урацп сполучень розбіваеться на тд-дерева О !, О2, О3, О4, де вщ-мiченi крайт точки пiддерев (пiвплощін). Злiва знаходяться вершини, в якіх досягаються мiнiмальнi значення функцп вь

    / (4,5,6) = 74

    Мал. 3. Структурна схема дерева сполучень для / (х)

    дповiдного пiддерева, а праворуч - максимальн значення функцп / (х).

    Користуючися базовим деревом конф ^ урацп сполучень, будуемо структурних дерево розв'язюв.

    Завдання значень щльово!

    / (2,3,4) = 26 ° 21 / (2,3,6) = 36 функцп / (х) = 47 досягаеться в • -Щ точках (3, 4, 5) вщповщно пiд-

    / (2,4,5) = 38

    / (2,4,6) = 44

    / (2,5,6) = 52

    Мал. 4. Структурна схема тддерева сполучень О2

    дерева О2, де

    / (2,3,4) < / (Х) < / (2,5,6) i О3, / (3,4,5) = / (х) < / (3,5,6) мо-жуть мютіті завдання значення у вщповщніх вершинах.

    Розглянемо тддерево

    О2.

    Пiддерева О21, О22 НЕ мiстять необхiдно точок, а єдина точка (2,5,6) тддерева О23 набувае значення / (2,5,6) = 52, что значний бшьше / (х) = 47.

    Зпдно з рис. 2, тддерево О3 складаеться iз трьох вершин: (3,4,5), (3,4,6), (3,5,6).

    Оскшькі / (3,4,5) = 47, тодi значення функцп / (х) в Наступний вершинах Рiвне / (3,4,6) = 54, / (3,5,6) = 63, что НЕ задовольняе умову.

    Отже, функщя / (х) досяжними значення 47 у вершить (3,4,5).

    4. Висновки

    У робот описано та дослщжено алгоритм локалiзацii лшшно'1 функцп на конф ^ урацп сполучень, елементи яко'1, з урахуванням методу генерування, представлений у виглядi неорiен-тованого графа, что НЕ травні ци ^ в. За рахунок структурних схем пiддерев сполучень зага-льного базового дерева знаходяться або вершини, або вiдповiднi пiддерева, что мютять НЕ-обхiднi значення функцп. Если локальне значення функцп НЕ потрапляе в чісловi екстрім-мінімальних iнтервалі вiдповiдно пiддерев, то розглядаються наступнi пiддерева i т.п. Если ж не юнуе конкретно! вершини базового дерева, что забезпечуе Досягнення даного числового значення функцп, то тодi розв'язком буде ребро вщповщного тддерева, в екстремальний штервал которого потрапляе значення функцп.

    Алгоритм об'єднує засоби комбшаторного аналiзу та теорп графiв i нада можли-вють НЕ делать повний перебiр елеменпв конф ^ урацп сполучень, на якiй розглядаеться задача.

    У результат наукового дослщження Було Розглянуто приклад задачi на конф ^ ура-цп сполучень, представлено! у виглядi неорieнтованого дерева.

    Подальшi дослiдження будут спрямоваш на адаптацiю Нових пiдходiв та алгоритми-MiB розв'язання комбiнаторніх завдань на шшіх конфiгурацiях з нелшшнімі функцiю з можливiсть зростання потужносп множини iз ЗАСТОСУВАННЯ графових моделей та про-грамно! реалiзацii методiв.

    СПИСОК Л1ТЕРАТУРІ

    1. Баранов В.І. Екстремальні комбінаторні задачі та їх застосування / В.І. Баранов, Б.С. Стекти-кін. - М .: Наука, 1989. - 160 с.

    2. Сергієнко І.В. Моделі і методи розв'язання на ЕОМ комбінаторних задач оптимізації / І.В. Сергієнко, М.Ф. Каспшіцкая. - К .: Наукова думка, 1981. - 288 с.

    3. Семенова Н.В. Пол1едральній тдхщ до розв'язання одного класу векторних задач комбшаторно! ошгашзацп / Н.В. Семенова, Л.М. Колечкша, А.М. НАПрН // Доповщ НАН Укра! -Ні. - 2009. - № 6. - С. 46 - 53.

    4. Колєчкіна Л.М. Багатокритеріальні комбінаторні задачі оптимізації на множині поліразмещеній / Л.М. Колєчкіна, Е.А. Родіонова // Кібернетика і системний аналіз. - 2008. - № 2. -С.152 - 160.

    5. Колечкша Л.М. Властівост завдань багатокрітер1ально! оптім1зац1! на комбшаторніх множини та методи! х розв'язання / М.Л. Колечкша. - Полтава: РВВ ПУСКУ, 2008. - 162 с.

    6. Донець Г.А. Побудова гамільтонова шляху в графах переставних многогранників / Г.А. Донець, Л.М. Колєчкіна // Кібернетика і системний аналіз. - 2010. - № 1. - С. 10 - 16.

    7. Донець Г.А. Екстремальні покриття графів / Г.А. Донець, А.Я. Петренюк. - Кіровоград: ВАТ «Юровоградське видавництво», 2009. - 170 с.

    8. Донець Г.А. Про один підхід до вирішення комбінаторної задачі оптимізації на графах / Г.А. Донець, Л.М. Колєчкіна // Керуючі системи та машини. - 2009. - № 4. - С. 36 - 42.

    9. Донець Г.А. Локалізація значення лінійної функції, заданої на перестановках / Г.А. Донець, Л.М. Колєчкіна // Радіоелектроніка та інформатика. - 2009. - № 1. - С. 76 - 81.

    10. Донець Г.А. Метод упорядкування значень лінійної функції на множині перестановок / Г.А. Донець, Л.М. Колєчкіна // Кібернетика і системний аналіз. - 2009. - № 2. - С. 50 - 61.

    Стаття над1йшла до редакцп 13.06.2014


    Ключові слова: ФУНКЦІЯ /ЛОКАЛІЗАЦІЯ /КОНФІГУРАЦІЯ поєднанні /генерування /неорієнтовані графів /ДЕРЕВО /піддерево /Корінь /Гамільтон ШЛЯХ /FUNCTION /LOCALIZATION /CONFIGURATION OF COMBINATIONS /GENERATION /UNDIRECTED GRAPH /TREE /SUBTREE /ROOT /HAMILTON PATH

    Завантажити оригінал статті:

    Завантажити