Координатний метод локалізації значення лінійної функції, заданої на перестановках
Розглядається задача локалізації лінійної функції на перестановках. Пропонується метод її розв'язання, який є новим та кращим серед відомих. Рассматривается задача локализации линейной функции на перестановках. Предлагается координатный метод ее решения, который является новым и лучшим среди из...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/46786 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Координатний метод локалізації значення лінійної функції, заданої на перестановках / А.Г. Донець, І.Е. Шулінок // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 142-149. — Бібліогр.: 2 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859604489709813760 |
|---|---|
| author | Донець, А.Г. Шулінок, І.Е. |
| author_facet | Донець, А.Г. Шулінок, І.Е. |
| citation_txt | Координатний метод локалізації значення лінійної функції, заданої на перестановках / А.Г. Донець, І.Е. Шулінок // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 142-149. — Бібліогр.: 2 назв. — укр. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Розглядається задача локалізації лінійної функції на перестановках. Пропонується метод її розв'язання, який є новим та кращим серед відомих.
Рассматривается задача локализации линейной функции на перестановках. Предлагается координатный метод ее решения, который является новым и лучшим среди известных.
The problem of localization of a linear function on permutations is considered. We propose the coordinate method of its solution, which is new and best known.
|
| first_indexed | 2025-11-28T03:04:16Z |
| format | Article |
| fulltext |
142 Теорія оптимальних рішень. 2011, № 10
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Розглядається задача локалізації
лінійної функції на перестановках.
Пропонується метод її розв’я-
зання, який є новим та кращим
серед відомих.
А.Г. Донець, І.Е. Шулінок, 2011
ÓÄÊ 519.8
À.Ã. ÄÎÍÅÖÜ, ².Å. ØÓ˲ÍÎÊ
ÊÎÎÐÄÈÍÀÒÍÈÉ ÌÅÒÎÄ ËÎÊÀ˲ÇÀÖ²¯
ÇÍÀ×ÅÍÍß Ë²Í²ÉÍί ÔÓÍÊÖ²¯,
ÇÀÄÀÍί ÍÀ ÏÅÐÅÑÒÀÍÎÂÊÀÕ
Багато екстремальних задач комбінаторної
оптимізації, такі як планування роботи
підприємства, розподіл ресурсів, задача
управління, мережеве планування опису-
ються моделями дискретної оптимізації. Із
задач дискретного моделювання виділяють-
ся задачі комбінаторної оптимізації, які
виникають у найрізноманітніших галузях
людської діяльності. Загальна задача комбі-
наторної оптимізації полягає у відшуканні
екстремуму довільної цільової функції на
довільних комбінаторних конфігураціях.
Застосування теорії графів до розв’язання
таких задач дає в багатьох випадках можли-
вість отримати розв’язок з меншими витра-
тами комп’ютерних ресурсів. Як відомо [1],
множину перестановок можна представити у
вигляді графа перестановок ( )nG P , який є
об’єднанням підграфів меншої розмірності.
Кожній послідовності з множини перестано-
вок ( )P A ставимо у відповідність вершину
графа ( )nG P . Для такого графа дві вершини
будемо визнавати суміжними, якщо коди
відповідних перестановок відрізняються
одноразовою транспозицією двох елементів.
З’єднуючи відповідні вершини по ходу
генерації перестановок, одержуємо спочатку
неорієнтований граф. Якщо в кожній вер-
шині графа знайти відповідне значення
заданої цільової функції ( )F x , то стосовно
значень функції можна побудувати орієнто-
ваний граф, зорієнтувавши його ребра у
напрямі від більшого значення функції до
меншого.
КООРДИНАТНИЙ МЕТОД ЛОКАЛІЗАЦІЇ ЗНАЧЕННЯ ЛІНІЙНОЇ ФУНКЦІЇ...
Теорія оптимальних рішень. 2011, № 10 143
Особливо це ефектно виходить щодо лінійних упорядкованих функцій, які
мають вигляд ( )
1
n
i i
i
F x c x
=
=∑ , де 1 2 ... nc c c≤ ≤ ≤ (рис. 1).
1
2 3
4 5
6
РИС. 1. Структура значень ( )F x для 3n =
Стосовно цих функцій легко довести таке твердження.
Лема 1. Якщо з перестановки ( ) ( )1 1 2, ,... np i i i P A= ∈ одержана перестанов-
ка ( )2p P A∈ транспозицією двох чисел k li i< , де k l< , то ( ) ( )1 2F p F p≥ .
На графі перестановок досить часто виникає наступна задача: знайти мно-
жину перестановок, на яких значення цільової функції дорівнює заданому зна-
ченню, тобто знайти
* arg ( )
x Pn
x f x
∈
= , де ( )*f x y= . (1)
Також має сенс розглянути аналогічну задачу, якщо не завжди існують перес-
тановки, в яких цільова функція приймає задане значення. Тоді зформульована
вище проблема постане як задача: визначити множину пар перестановок ( ),x x ,
для яких за заданого y має місце
( )
arg min ( )
f x y
x f x
>
= ,
( )
arg min ( )
f x y
x f x
<
= . (2)
Задачі (1)-(2) мають спільну назву задачі локалізації значень цільової функції
на перестановках. У роботі [2] описано горизонтальний метод розв’язання цієї
задачі.
Слід зазначити, що значення функції на графі перестановок у напрямку
знизу вверх зростає, а зверху вниз – спадає при рівномірному розподілі значень
1 2 3
2 1 3 1 3 2
3 2 1
3 1 2 2 3 1
А.Г. ДОНЕЦЬ, І.Е. ШУЛІНОК
144 Теорія оптимальних рішень. 2011, № 10
коефіцієнтів. Це обумовлено ієрархічною будовою цього графа та лінійністю
цільової функції. При цьому поняття „верх”, або „низ” мають стабільний струк-
турний зміст у відношенні підграфів у рамках об’єднуючого графа. Так, напри-
клад, підграф G(P3), зображений на рис.1, є складовою частиною всіх графів з
більшою кількістю координат. Чотири підграфа G(P3), як показано на рис. 2,
складають граф G(P4) ), п’ять підграфів G(P4), або 20 підграфів G(P3), скла-
дають G(P5) і так далі. Це означає, що для довільного n значення цільової функ-
ції в шести вершинах підграфа G(P3), у яких до координат справа дописані
числа 4, 5, 6, ..., n-1, n, складають шість найбільших серед n! значень функції.
Починаючи з одної із цих вершин, можна визначити множину шляхів, на яких
значення функції спадає.
РИC. 2. Структура значень ( )F x для n = 4
КООРДИНАТНИЙ МЕТОД ЛОКАЛІЗАЦІЇ ЗНАЧЕННЯ ЛІНІЙНОЇ ФУНКЦІЇ...
Теорія оптимальних рішень. 2011, № 10 145
Це і є підґрунтям для координатного методу локалізації функції. Розглянемо
його суть на прикладі з такою функцією 1 2 3 4 5 6( ) 4 8 2 7 3 6f x x x x x x x= + + + + + .
Треба знайти перестановки x*, в яких f(x*)=y*=109. Після упорядкування ця
функція має вигляд f(x) = 2x1 + 3x2 + 4x3 + 6x4 +7x5 + 8x6.
Будемо поступово розглядати підграфи Gi, тобто підграфи, у яких фіксована
остання координата – у даному прикладі n = 6, а x6 =1,2,3,4,5,6, або x6 ∈N6.
Кожній вершині графа на рис.1, в залежності від її типу, можна поставити у
відповідність свій підграф Gi (рис. 3). Під типом вершини розуміється наступне:
якщо шоста координата для всього графа постійна (на рис.3 це 2), то п’ята і
четверта змінюються від більшої можливої до меншої. Якщо три старші коор-
динати вже вибрані, то порядок перших трьох, який відповідає одній з шести
вершин на рис.1, визначає тип вершини. Пояснимо побудову і структуру рис. 3.
x5=6 x5=5 x5=4 x5=3 x5=1
(341562)
x4 = max{N6\x5, 2}
(361542)
(564312)
РИС.3. Схема підграфа G2 для типу вершин (231)
Граф представляє мережу, де витоком є найвища і найлівіша вершина, а
стоком – найнижча і найправіша вершина. Нехай на рис.3 як тип вибрано вер-
шину (231). Тоді координати витока такі: x6 = 2, x5 = 6, x4 = 5. Упорядкуємо інші
координати, що залишилися. i1=1, i2 =3, i3 =4. Тип вершини зобов’язує, щоб
нижні індекси перших трьох координат були відповідно (231), тобто код витоку
має вигляд (341562). Аналогічно знаходимо координати стоку.Ясно, що тут
четверта і п’ята координати вибираються як найменші можливі, тобто x6 = 2, x5
= 1, x4 = 3. Для перших трьох координат маємо i1=4, i2 =5, i3 =6, і код стоку має
вигляд (564312). Для довільної вершини цього підграфа (на рис. 3 вона заштри-
хована) застосовується той же принцип. Для неї x6 = 2, x5 = 4, а x4 = 5 як друге за
величиною значення серед залишених 1,3,5,6. Звідси код виділеної вершини
(361542).
Тепер будемо розв’язувати поставлену задачу, при цьому дотримуючись та-
ких правил: а) якщо в даній вершині значення функції менше заданого, то далі
треба шукати це значення в сусідній вершині, збільшуючи четверту або п’яту
А.Г. ДОНЕЦЬ, І.Е. ШУЛІНОК
146 Теорія оптимальних рішень. 2011, № 10
координату; б) якщо в даній вершині значення функції більше заданого, то далі
треба шукати це значення в сусідній вершині, зменшуючи четверту або п’яту
координату.
Покажемо, що для розв’язування задачі не обов’язково розглядати всі коди
підграфів типу на рис. 3 і обчислювати в них значення функції, а достатньо
обчислити її значення у витоках мереж, які відповідають підграфам з фіксова-
ним значенням шостої координати. Наприклад, виберемо тип вершини (213).
Розглянемо підграфи Gi і для кожного обчислимо значення функції у витоках
цих під графів (табл. 1).
ТАБЛИЦЯ 1
Підграф Код витоку Значення f(x)
G6 213456 126
G5 213465 125
G4 213564 123
G3 214563 119
G2 314562 113
G1 324561 108
Із табл. 1 видно, що підграф G1 можна не розглядати, так як максимальне
значення функції менше того значення, яке ми шукаємо. Отже, розглянемо інші
підграфи, наприклад G6 і дослідимо в ньому п’яту координату. Вона послідовно
приймає значення 5⇒ 4⇒ 3⇒ 2⇒ 1. Відповідно до вектора коефіцієнтів
функції c = (2,3,4,6,7,8) це призведе до зменшення значення функції послідовно
на (c5-c4)=1, (c5-c3)=3, (c5-c1)=5, (c5-c2)=4, а в сумі на 13. Тобто найменше зна-
чення при x4 = 4 функція приймає у вершині (324516), а саме 126-13=113. Треба
зменшувати значення x4 . Це досягається транспозицією єлементів 5 і 4 та змен-
шенням значення функції на (c4-c3)=2, і воно стане рівним111.Але це все одно
більше 109, тому знову замінюємо значення x4 на 3, що зменшить значення
функції на (c5-c2)=4, тобто до 107, у вершині (425316). Тепер це менше 109, тому
треба збільшувати x5 до 2, що досягається транспозицією чисел 2 та 1 і зростан-
ням функції у вершині (415326) на (c4-c1)=4, тобто до 111. Знову зменшуємо
значення x4 до 1 шляхом транспозиції чисел 3 та 1.У вершині (435126) отримає-
мо зменшення функції на (3-1)(c4-c2)=6, тобто до 105. Необхідно збільшити x5 до
3, переставляючи числа 2 і 3. Отримаємо значення функції 105 + (c5-c2)=109, що
і було потрібно. Оскільки x4 у цій вершині найменше, то більше в підграфі G6
таких вершин не існує. Переходимо до i< 6.
Зробимо деякі узагальнення. Розв’язання задачі провадиться для всіх типів
вершин. Для фіксованого типу вершин послідовно для кожного підграфу знахо-
дяться необхідні вершини x*, в яких f(x*) = y*. Будемо далі називати вершину-
виток початковою вершиною графа Gi. Алгоритм пошуку необхідної вершини
для підграфу Gi (i = 1,2,...., n ) можна поділити на три етапи. Перший етап: побу-
КООРДИНАТНИЙ МЕТОД ЛОКАЛІЗАЦІЇ ЗНАЧЕННЯ ЛІНІЙНОЇ ФУНКЦІЇ...
Теорія оптимальних рішень. 2011, № 10 147
дова коду початкової вершини для Gi. Другий етап: розгортання графа вздовж
координати x4. Третій етап: розгортання графа вздовж координати x5.
Опишемо кожний етап.
I. Нехай вибрано тип вершини (i1, i2, i3), де i1 ∪ i2 ∪ i3={1,2,3}, та номер підг-
рафу i. Тоді покладемо: x6 = i; x5 = max{N6\x6}, x4 = max{N6\( x5, x6)}. Упорядкує-
мо числа {N6\( x4 ,x5, x6)} по зростанню j1 < j2 < j3 . Тоді x1=
1i
j , x2 =
2i
j , x3 =
3i
j . Це
і буде код головної виршини мережі Gi, який позначимо p1(або q1). Обчислимо
значення цільової функції в цій вершині f(p1).
II. Розглянемо в цьому коді значення xk (k = 1,2,3,4) та упорядкуємо їх за
спаданням x4 = j4 > j3 > j2 > j1. Розгортанням графа вздовж координати x4 (або вниз)
назвемо послідовність транспозицій j4 ⇔ j3 ⇔ j2 ⇔ j1, які крім коду головної
вершини приводять до створення ще трьох кодів, які позначимо p2, p3 та p4 і
запишемо один під одним. Щоб знайти значення функції на цих перестановках,
не обов’язково використовувати всі її координати. Достатньо знайти різницю
значень функцій у сусідніх вершинах. Позначимо µ(λ) номер місця числа jλ в
коді перестановки p1 (λ = 1,2,3). Тоді значення f(p2) буде менше f(p1) на величину
1∆ = (j4 - j3)(c4 - cµ(3) ). У другому множнику постійно буде величина c4 , тому що
в транспозиції завжди бере участь координата x4. Аналогічно знаходимо другу
та третю різниці. Очевидно, що в процесі подальшого пошуку необхідно вико-
ристовувати тільки ті перестановки, для яких f(p1) ≥ y*.
III. Розглянемо в коді вершини pk (яку позначимо q1, (к=1,2,3,4) значення x5,
x4, x3, x2, x1 та упорядкуємо їх за спаданням. x5 = j5 > j4 > j3 > j2 > j1. Розгортанням
графа вздовж координати x5 (або праворуч) назвемо послідовність транспозицій
j5 ⇔ j4 ⇔ j3 ⇔ j2 ⇔ j1, які крім коду головної вершини мають привести до
створення ще чотирьох кодів, які позначимо q2, q3, q4 та q5. Але ці коди створю-
вати не обов’язково Так само, як і при розгортанні графа вниз, значення функції
f(q2) у вершині q2 буде меншим від значення f(q1) на величину δ1=(j5-j4)(c5 - cµ(4)).
За цією формулою знаходимо інші різниці. Послідовно віднімаючи δλ (4 ≥ λ ≥ 1)
від f(q1), можемо отримати дві такі ситуації:
1. Всі значення функцій більші y*. У цьому випадку переходимо до розгор-
тання наступного коду pk .
2. На деякому кроці λ* отримаємо значення функції у вершині рівне y*( або
менше y*). У першому випадку запам’ятовуємо код відповідної вершини. Пере-
ходимо до розгортання наступного коду pk , при цьому кількість кроків обмежу-
ється до λ*–1.
Після розгортання всіх pk (к=1,2,3,4) пошук необхідних вершин підграфа Gi
з фіксованим i закінчується.
Проведемо необхідні обчислення для всіх підграфів, наведених в табл. 1,
використовуючи описані три етапи.
Для G6 отримали вершину (425136), в якій f(425136) = 109. Розглянемо те-
пер G5 і відповідну розгортку графа в табл..2, де перші числа – це значення
А.Г. ДОНЕЦЬ, І.Е. ШУЛІНОК
148 Теорія оптимальних рішень. 2011, № 10
функції у перестановці, а далі наведено її код. Для G5 p1= q1 = (213465), f(q1) =
125, (6 ⇔ 4 ⇔ 3 ⇔ 2 ⇔ 1).
ТАБЛИЦЯ 2
125 - 213465 123 - 213645 120 -214635 115 – 314625 111 – 324615
123 - 214365 117 - 216345 116 -216435 111 - 316425 107- 326415
119 - 314265 113 - 316245 108 -416235 107 - 416325 103 - 426315
116 - 324165 110 -326145 105 -426135 101 - 436125 100 - 436215
Різниця значень пробігає числа (6-4)(7-6)=2, 7-4=3, 7-2=5, 7-3=4, у сумі до-
рівнює 14, тобто найменше значення функції при постійному значенні x4 буде
125–14=111>109. Розгортаємо код p2, для якого f(214365) = 123,
(6 ⇔ 4 ⇔ 3 ⇔ 2 ⇔ 1) і різниця значень пробігає числа (6-4)(7-4) = 6, 1, 5, 4, у
сумі = 16. Значення функції спадають 123 – 117 – 116 – 111 – 107. Тут немає
шуканої вершини, тому переходимо до коду p3, при цьому будемо розгортати
код на крок менше. Це дає значення функції f( p3) = f (314265) = 119,
(6 ⇔ 4 ⇔ 3 ⇔ 2). Різниця їх значень пробігає числа (6-4)(7-4) = 6, 5, 1, а зна-
чення функції спадають 119 – 113 – 108 – 107. Тут також немає шуканої верши-
ни, тому переходимо до коду p4, в якому перевіряємо тільки один крок f( p4) =
= f (324165) = 116. Сусідня вершина відрізняється транспозицією чисел 6 і 4, а
функція на 6 менша, або дорівнює 110 < 109. Отже, у підграфі G5 немає шуканих
вершин.
Для G4 p1= (213564), f(p1)= 123, (6 ⇔ 5 ⇔ 3 ⇔ 2 ⇔ 1). Різниця значень
пробігає числа (7-6)=1, 2(7-4)=6, 7-2=5, 7-3=4, що дає послідовність спадання
функції 123 – 122 – 116 – 111 – 107. Переходимо до p2= (215364), f(p2)= 119, а
кроків робимо на один менше (6 ⇔ 5 ⇔ 3 ⇔ 2). Різниця значень пробігає
числа (7-4)=3, 2(7-6)=2, 7-2=5, а функція спадає 119 – 116 – 114 – 109. Це зна-
чення шуканої вершини, а її код легко обчислити – (316524) за трьома транспо-
зиціями над кодом p2. Переходимо до коду p3=(315264) і робимо два кроки–
f(p3)=115, (6 ⇔ 5 ⇔ 3). Це дає різниці 7-4=3, 2(7-2)=10, тобто спадання функції
112-102. Це означає, що при даному значенні x4 шуканої вершини немає. Пере-
ходимо до коду p4=(325164) і робимо один крок (6 ⇔ 5). Це дає різницю 7-4=3,
або значення функції 112-3=109. Так що в підграфі G4 отримаємо дві шуканих
вершини.
Переходимо до G3 , де код p1= (214563), f(p1)= 119, (6 ⇔ 5 ⇔ 4 ⇔ 2 ⇔ 1).
Різницями будуть числа 1, 3, 10, 4. Спадання функції 119 – 118 – 115 – 105 – 101.
Тут немає шуканої вершини, а в наступному коді робимо два кроки. f(p2)= 117,
а p2 = (215463), (6 ⇔ 5 ⇔ 4), що відповідає різницям 3, 1. При цьому функція
спадає –117 – 114 – 113. Для p4 відразу отримуємо f(p3)= 109, тому на цьому по-
шук в G3 закінчується.
Залишилося зробити пошук у підграфі G2. Код його головної вершини p1=
=(314562), f(p1)= 113, (6 ⇔ 5 ⇔ 4 ⇔ 3 ⇔ 1). Різниці складають числа 1, 3, 5, 8.
КООРДИНАТНИЙ МЕТОД ЛОКАЛІЗАЦІЇ ЗНАЧЕННЯ ЛІНІЙНОЇ ФУНКЦІЇ...
Теорія оптимальних рішень. 2011, № 10 149
Спадання функції наступне – 113 – 112 – 109 – 104 – 96. Тут маємо одну шукану
вершину f(x*) = y*, де x* = (315642). Переходимо до коду вершини p2= (315462),
f(p2) = 111, робимо один крок (6 ⇔ 5). Це приводить до транспозиції зі змешен-
ням функції до 108. На цьому і закінчиться пошук на підграфі G2, а тим самим
на підграфі, що відповідає типу вершини (213). Внаслідок цього для даного типу
вершини було знайдено 5 вершин, значення функції в яких дорівнює 109.
Схема пошуку необхідних вершин серед підграфів з фіксованим типом ве-
ршин не відрізняється від наведеної.
Слід зазначити такі відмінності алгоритму пошуку необхідних вершин ко-
ординатним методом від горизонтального: перш за все, останній метод потребує
менше обчислень. Необхідно обчислювати лише різниці значень функції, тоді як
у попередньому методі кожний раз необхідно обчислювати значення функції в
новій вершині, при цьому кожен раз відтворювати код вершини. Крім того,
останній метод дозволяє декілька модифікацій, пов’язаних з обчисленням не
тільки в кодах головних вершинах (витоках), а і симетричним підходом стосов-
но вершин-стоків та інших.
А.Г. Донец, И.Э. Шулинок
КООРДИНАТНЫЙ МЕТОД ЛОКАЛИЗАЦИИ ЗНАЧЕНИЯ ЛИНЕЙНОЙ ФУНКЦИИ,
ЗАДАННОЙ НА ПЕРЕСТАНОВКАХ
Рассматривается задача локализации линейной функции на перестановках. Предлагается
координатный метод ее решения, который является новым и лучшим среди известных.
A.G. Donets, I.E. Shulіnok
COORDINATE METHOD FOR LOCALIZATION VALUES OF LINEAR FUNCTIONS
DEFINED ON PERMUTATIONS
The problem of localization of a linear function on permutations is considered. We propose the
coordinate method of its solution, which is new and best known.
1. Донец Г.А., Колечкина Л.Н. Построение гамильтонова пути в графах перестановоч-
ных многогранников // Кибернетика и системный анализ. – 2010. – № 1. – С. 10–16.
2. Донец Г.А., Колечкина Л.Н. Локализация значения линейной функции заданной на
перестановках // Радиоэлектроника и информатика. – 2009. − № 1. – С. 76–81.
Получено 15.04.2011
|
| id | nasplib_isofts_kiev_ua-123456789-46786 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Ukrainian |
| last_indexed | 2025-11-28T03:04:16Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донець, А.Г. Шулінок, І.Е. 2013-07-06T17:32:54Z 2013-07-06T17:32:54Z 2011 Координатний метод локалізації значення лінійної функції, заданої на перестановках / А.Г. Донець, І.Е. Шулінок // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 142-149. — Бібліогр.: 2 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46786 519.8 Розглядається задача локалізації лінійної функції на перестановках. Пропонується метод її розв'язання, який є новим та кращим серед відомих. Рассматривается задача локализации линейной функции на перестановках. Предлагается координатный метод ее решения, который является новым и лучшим среди известных. The problem of localization of a linear function on permutations is considered. We propose the coordinate method of its solution, which is new and best known. uk Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Координатний метод локалізації значення лінійної функції, заданої на перестановках Координатный метод локализации значения линейной функции, заданной на перестановках Coordinate method for localization values of linear functions defined on permutations Article published earlier |
| spellingShingle | Координатний метод локалізації значення лінійної функції, заданої на перестановках Донець, А.Г. Шулінок, І.Е. |
| title | Координатний метод локалізації значення лінійної функції, заданої на перестановках |
| title_alt | Координатный метод локализации значения линейной функции, заданной на перестановках Coordinate method for localization values of linear functions defined on permutations |
| title_full | Координатний метод локалізації значення лінійної функції, заданої на перестановках |
| title_fullStr | Координатний метод локалізації значення лінійної функції, заданої на перестановках |
| title_full_unstemmed | Координатний метод локалізації значення лінійної функції, заданої на перестановках |
| title_short | Координатний метод локалізації значення лінійної функції, заданої на перестановках |
| title_sort | координатний метод локалізації значення лінійної функції, заданої на перестановках |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/46786 |
| work_keys_str_mv | AT donecʹag koordinatniimetodlokalízacííznačennâlíníinoífunkcíízadanoínaperestanovkah AT šulínokíe koordinatniimetodlokalízacííznačennâlíníinoífunkcíízadanoínaperestanovkah AT donecʹag koordinatnyimetodlokalizaciiznačeniâlineinoifunkciizadannoinaperestanovkah AT šulínokíe koordinatnyimetodlokalizaciiznačeniâlineinoifunkciizadannoinaperestanovkah AT donecʹag coordinatemethodforlocalizationvaluesoflinearfunctionsdefinedonpermutations AT šulínokíe coordinatemethodforlocalizationvaluesoflinearfunctionsdefinedonpermutations |