Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод

Розглянуто постановку та математичну модель ігрової задачі сільськогосподарського виробництва з обмеженнями-переставленнями, що накладаються на стратегії обох гравців. Поширено ітераційний метод на задачі комбінаторної оптимізації ігрового типу з обмеженнями, що визначаються переставленнями на стра...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
Hauptverfasser:	Ємець, О.О., Ольховська, О.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2012
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Методи оптимізації, оптимальне управління і теорія ігор
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/50198
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:	Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод / О.О. Ємець, О.В. Ольховська // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 80-93. — Бібліогр.: 16 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50198
record_format	dspace
spelling	irk-123456789-501982013-10-07T03:06:15Z Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод Ємець, О.О. Ольховська, О.В. Методи оптимізації, оптимальне управління і теорія ігор Розглянуто постановку та математичну модель ігрової задачі сільськогосподарського виробництва з обмеженнями-переставленнями, що накладаються на стратегії обох гравців. Поширено ітераційний метод на задачі комбінаторної оптимізації ігрового типу з обмеженнями, що визначаються переставленнями на стратегії обох гравців. Метод ґрунтується на розігруванні гри, за умови, що кожен гравець прагне досягнути своєї мети. Запропоновано критерії зупинки та процедури визначення результату. На основі розробленого програмного продукту проведено обчислювальні експерименти, які показують наближення платежів до ціни гри, що дає можливість наближеного знаходження мішаних стратегій гравців. Проведено теоретичну та експериментальну оцінку кількості операцій запропонованого ітераційного алгоритму. Рассмотрена постановка и математическая модель игровой задачи сельскохозяйственного производства с ограничениями-перестановками, которые накладываются на стратегии обоих игроков. Распространен итерационный метод на задачи комбинаторной оптимизации игрового типа с ограничениями, которые определяются перестановками на стратегии обоих игроков. Метод основан на розыгрыше игры, при условии, что каждый игрок стремится достичь своей цели. Предложен критерий остановки и процедуры определения результата. На основе разработанного программного продукта проведены вычислительные эксперименты, которые показывают приближение платежей к цене игры, что дает возможность приближенного определения смешанных стратегий игроков. Приведена теоретическая и экспериментальная оценка количества операций предложенного итерационного метода. The definition and the mathematical model of a game problem for agricultural production with permutations-restrictions that are imposed on the strategies of both players, are considered. The iterative method is extended for combinatorial optimization problems of the gaming type with the restrictions, defined by permutations on the strategies of both players. The method is based on drowing the game, under the condition that each player tries to achieve his goal. A criterion of stopping and the procedures of determination of the oresult are suggested. On the basis of the developed software computational experiments, which show approaching of payments to the game price, which enables the approximate determination of mixed strategies of the players, are performed. A theoretical and experimental evaluation of the operations of the proposed iterative method is given. 2012 Article Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод / О.О. Ємець, О.В. Ольховська // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 80-93. — Бібліогр.: 16 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50198 519.83 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор
spellingShingle	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор Ємець, О.О. Ольховська, О.В. Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод Системні дослідження та інформаційні технології
description	Розглянуто постановку та математичну модель ігрової задачі сільськогосподарського виробництва з обмеженнями-переставленнями, що накладаються на стратегії обох гравців. Поширено ітераційний метод на задачі комбінаторної оптимізації ігрового типу з обмеженнями, що визначаються переставленнями на стратегії обох гравців. Метод ґрунтується на розігруванні гри, за умови, що кожен гравець прагне досягнути своєї мети. Запропоновано критерії зупинки та процедури визначення результату. На основі розробленого програмного продукту проведено обчислювальні експерименти, які показують наближення платежів до ціни гри, що дає можливість наближеного знаходження мішаних стратегій гравців. Проведено теоретичну та експериментальну оцінку кількості операцій запропонованого ітераційного алгоритму.
format	Article
author	Ємець, О.О. Ольховська, О.В.
author_facet	Ємець, О.О. Ольховська, О.В.
author_sort	Ємець, О.О.
title	Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод
title_short	Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод
title_full	Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод
title_fullStr	Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод
title_full_unstemmed	Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод
title_sort	розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2012
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	http://dspace.nbuv.gov.ua/handle/123456789/50198
citation_txt	Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод / О.О. Ємець, О.В. Ольховська // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 80-93. — Бібліогр.: 16 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT êmecʹoo rozvâzuvannâkombínatornihzadačígrovogotipuzobmežennâmiperestavlennâmiuobohgravcívíteracíjnijmetod AT olʹhovsʹkaov rozvâzuvannâkombínatornihzadačígrovogotipuzobmežennâmiperestavlennâmiuobohgravcívíteracíjnijmetod
first_indexed	2025-07-04T11:46:04Z
last_indexed	2025-07-04T11:46:04Z
_version_	1836716722976980992
fulltext	© О.О. Ємець, О.В. Ольховська, 2012 80 ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.83 РОЗВ’ЯЗУВАННЯ КОМБІНАТОРНИХ ЗАДАЧ ІГРОВОГО ТИПУ З ОБМЕЖЕННЯМИ-ПЕРЕСТАВЛЕННЯМИ У ОБОХ ГРАВЦІВ: ІТЕРАЦІЙНИЙ МЕТОД О.О. ЄМЕЦЬ, О.В. ОЛЬХОВСЬКА Розглянуто постановку та математичну модель ігрової задачі сільськогоспо- дарського виробництва з обмеженнями-переставленнями, що накладаються на стратегії обох гравців. Поширено ітераційний метод на задачі комбінаторної оптимізації ігрового типу з обмеженнями, що визначаються переставленнями на стратегії обох гравців. Метод ґрунтується на розігруванні гри, за умови, що кожен гравець прагне досягнути своєї мети. Запропоновано критерії зупинки та процедури визначення результату. На основі розробленого програмного продукту проведено обчислювальні експерименти, які показують наближення платежів до ціни гри, що дає можливість наближеного знаходження мішаних стратегій гравців. Проведено теоретичну та експериментальну оцінку кількос- ті операцій запропонованого ітераційного алгоритму. ВСТУП Різноманітні комбінаторні оптимізаційні задачі часто виникають під час мо- делювання на виробництві, у сільськогосподарській діяльності тощо. Ці за- дачі потребують розв’язання, а тому розробки необхідних методів. Теорія комбінаторної оптимізації містить алгоритми та методи розв’язання задач такого типу [1–13]. Праці [7–13] присвячені дослідженню задач комбінатор- ної оптимізації ігрового типу. У [7–13] розглянуто розв’язування цього кла- су задач ітераційним методом за умови, коли на стратегії тільки одного гравця накладаються обмеження, що визначені переставленнями [7], або розміщеннями [10, 13]. У [7] сформульовано математичні моделі у вигляді задач комбінаторної оптимізації ігрового типу, на які накладаються обме- ження, що визначаються переставленнями, на стратегії обох гравців. Такі задачі, як відомо з [7], зустрічаються на виробничих підприємствах, у сфері обслуговування, а тому потребують методів для свого розв’язання. Поки що таких методів не існує. Мета роботи — поширення ітераційного методу [11, 13] для розв’язування задач комбінаторної оптимізації ігрового типу за умови, що на стратегії накладаються обмеження, які визначені переставленнями для обох гравців. Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями … Системні дослідження та інформаційні технології, 2012, № 4 81 ПОСТАНОВКА ЗАДАЧІ Розглянемо задачу з роботи [7]. Нехай є два підприємства, які займаються вирощуванням сільськогосподарських культур. Перше господарство на сво- їх m полях вирощує m різних культур. Поля різної площі, тому кількість кожної вирощеної культури залежить від того, на якому полі її буде поса- джено. У другого господарства є відповідно l полів, на яких вирощується l різних культур. Кожне поле в обох господарствах засівають повністю од- нією культурою. Восени вирощену культуру реалізують, саме тому прибут- ки обох підприємств залежать від кількості вирощеної продукції кожним господарством. Потрібно скласти оптимальні плани вирощування культур в обох господарствах. Складемо математичну модель задачі, що розглядається, пояснивши одночасно оптимальність плану. Позначимо x iP — відношення площі i -го поля до суми площ усіх по- лів господарства. Вектор ),...,,( 21 x m xxx PPPP = показує, яку частину від за- гальної суми площ складає площа кожного з полів. Оскільки xP — це час- тини від загальної суми площ, то m x i JiP ∈∀≥ ;0 : 1 1 =∑ = m i x iP , де m — натуральні числа mJm =},...,2,1{ . Покладемо ),...,,( 21 mxxxX = . Компонен- та вектора з номером i показує, яку частину від максимально можливої кількості продукції i -го типу виростили, тобто цей вектор характеризує об- сяги вирощування продукції першим господарством. На кожному з полів вирощується тільки одна культура, тобто ком- понента i вектора X буде відповідати тій компоненті з ,xP що відповідає полю, на якому вирощено культуру i -го типу. Отже, компоненти векто- ра X є переставленням компонент вектора xP : ),(),...,,( 21 x mm PExxxX ∈= де )( x m PE — множина переставлень із елементів вектора .xP Для другого господарства введемо аналогічні вектори: ),...,,( 21 y l yyy PPPP = — вектор для якого виконується: l y j JjP ∈∀≥ ;0 ; .1 1 =∑ = l j y jP Вектор ),...,,( 21 lyyyY = характеризує обсяги вирощування продукції другим господарством, а отже компоненти цього вектора є переставленнями з yP : ).(),...,,( 21 y ll PEyyyY ∈= Складемо матрицю )( ijaA ′=′ , елемент ija′ — показує перевищення (різницю) прибутків другого підприємства порівняно з першим тоді, коли перше господарство вирощувало на всіх своїх полях тільки i -ту культуру, а друге — тільки j -ту культуру. Позначимо ),( YXF функцію: .),( 1111 ∑∑∑∑ ==== ′=′= l j jiij m i l j jij m i i yxayaxYXF (1) Функція прибутку є функцією переставлень X та .Y О.О. Ємець, О.В. Ольховська ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 82 Перший гравець — завдяки своїм можливостям вибору вектора X прагне мінімізувати свій максимальний програш, отже треба знайти таке X за якого досягається величина ),(maxmin )()( YXF ylxm PEYPEX ∈∈ =α , яку назива- тимемо нижньою ціною гри. Другий гравець, у свою чергу, завдяки вибору Y прагне максимізувати свій мінімальний виграш, тобто визначає величи- ну ),(minmax )()( YXF xmyl PEXPEY ∈∈ =β , яку називатимемо верхньою ціною гри. Таким чином, можна записати математичну модель цієї задачі, яка вперше була розглянута в [7]. Знайти оптимальні стратегії гравців X та ,Y де =X )(minarg )( XFx PEX x m∈ = ; ),(max)( )( YXFXF y l PEY x ∈ = ; )(maxarg )( YFY y PEY y l∈ = ; ),(min)( )( YXFYF x m PEX y ∈ = . За обмежень: • ),(),...,,( 21 x mm PExxxX ∈= ;1:),...( 1 1 == ∑ = m i im xxxX • вектор ),,...,,( 21 x m xxx PPPP = задовольняє умовам 0≥x iP mJi∈∀ ; • )(),...,,( 21 y ll PEyyyY ∈= , ;1:),...,,( 1 21 == ∑ = l j jl yyyyY • вектор ),,...,,( 21 y l yyy PPPP = задовольняє умовам 0≥y jP lJj∈∀ , де функція ),( YXF має вигляд (1), )( lmij JjJia ∈∀∈∀ — задані дійсні числа. Задачі, які мають описану математичну модель, назвемо задачами ком- бінаторної оптимізації ігрового типу з переставними обмеженнями на стра- тегії обох гравців. Якщо існують X та Y , то вважатимемо, що задача зв’язок у чистих стратегіях. Інакше, як і у випадку класичної матричної гри, введемо в розгляд мішані стратегії. Для цього складемо нову платіжну мат- рицю )( ijaA = вимірності nk × , де !mk = , !ln = . Платіж ija у цій матриці нехай обчислюється так: ∑∑ = = ′= n j jtit m t tjij yxaa 1 1 , kJi∈∀ , nJj ∈∀ , де i — но- мер відповідного вектора ),...,,( 21 imiii xxxX = — це переставлення з множини )( x m PE , а j — номер відповідного вектора ),...,,( 21 lj yyyY = — переставлення з множини )( y l PE . Таким чином, ija — платіж (перевищен- ня прибутку) першого гравця над другим, коли перший гравець обирає стра- тегію-переставлення iX , а другий — стратегію-переставлення jY . Позначимо ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ≥=== ∑ = 0,1),,...,,( 1 21 i k i ikk pppppPS ; Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями … Системні дослідження та інформаційні технології, 2012, № 4 83 ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ≥=== ∑ = 0,1),,...,,( 1 21 j n j jnn qqqqqQS . Мішаною стратегією першого гравця є елемент kSp∈ , мішаною стра- тегією гравця 2 — елемент nSq∈ . Якщо гравець 1 застосовує свою мішану стратегію ),...,( 1 kppP = , а 2 — ),...,( 1 nqqQ = , то платою гравця 1 гравцю 2 є величина ),( QPF , яка є математичним сподіванням випадкової величи- ни, що приймає значення ija kJi∈∀ , nJj∈∀ : ( ) 1 1 , n k ij i j j i F P Q a p q = = =∑ ∑ , де добуток ji qp — ймовірність випадкової події, що полягає в одночасному настанні випадкової події iX для першого гравця та jY — другого. Гравець 1 може забезпечити собі програш не більше ∑∑ ==∈∈ k i jiij n jSQSP qpa nk 11 maxmin , а гра- вець 2 — не менше .minmax 1 1 ∑∑ = = ∈∈ n j k i jiijSQSP qpa nk Якщо ),( ** QP — сідлова точка функції ),( QPF , що визначається ),( QPF , тобто виконуються нерівності ≤),( * QPF ),(),( * QPFQPF ≤≤ , то , QP називають оптимальними мі- шаними стратегіями гравців 1 та 2 відповідно. У цьому випадку, як відо- мо [14], значення платіжної функції в сідловій точці: =),( QPF ),(maxmin),(minmax QPFQPF nkkn SPSQSQSP ∈∈∈∈ == . При цьому задача комбінаторної оп- тимізації ігрового типу з переставними обмеженнями на стратегії обох грав- ців має розв’язок у мішаних стратегіях, а ),( QPF — ціна гри. Таким чи- ном, можна ставити задачу знаходження ймовірностей застосувань стратегій–переставлень першим та другим гравцями. Зауважимо, що ця постановка включає в себе і знаходження чистих стратегій (коли всі ймовір- ності крім однієї є нулями, а одна — одиницею). ІТЕРАЦІЙНИЙ НАБЛИЖЕНИЙ МЕТОД ЗНАХОДЖЕННЯ МІШАНИХ СТРАТЕГІЙ Далі пропонується ітераційний метод для розв’язування в мішаних стратегі- ях задач комбінаторної оптимізації ігрового типу, в яких на чисті стратегії накладаються обмеження, що визначені переставленнями для обох гравців. Розглянемо матрицю )( ijaA = , елемент ija якої показує перевищення (різницю) прибутків другого гравця порівняно з першим. Вимірності цієї матриці — nm× , де m — кількість рядків, n — кількість стовпців матриці. На стратегії першого гравця накладаються обмеження, що визначені переставленнями. Ці переставлення є переставленнями елементів із мульти- множини xP ; на стратегії другого гравця накладаються обмеження, які теж визначені переставленнями з елементів мультимножини .yP О.О. Ємець, О.В. Ольховська ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 84 Ідея ітераційного методу, як і для класичної матричної гри, зводиться до наступного [14]. Розігрується гра, в якій супротивники застосовують один проти одного свої стратегії. Експеримент складається з послідовності ходів. Починається з того, що один із гравців обирає довільно одну зі своїх стратегій, інший на це відповідає своєю стратегією, котра найменш вигідна для першого гравця тощо. У кожній партії, коли настає черга гравця обирати стратегію, інший відповідає своєму опоненту тією ж чистою стратегією, яка є найгіршою для противника з урахуванням усіх його попередніх виборів. Ходи розглядаються, як своєрідна «мішана стратегія», де чисті стратегії змішані в пропорціях, які відповідні частоті їх застосування в минулому. Такий спосіб є моделлю реального практичного «взаємного навчання» грав- ців, коли кожен із них на досвіді досліджує спосіб поведінки супротивника і вчиться на його та своїх помилках. АЛГОРИТМ МЕТОДУ Всі наступні обчислення представлені табл. 1. Перший стовбець N табли- ці — це номер одного етапу розіграшу гри, на якому гравці по черзі роблять свої кроки (обирають по черзі свої стратегії). Курсивом в описі алгоритму зображено табличну реалізацію методу. Т а б л и ц я 1 . Розв’язування комбінаторної задачі ігрового типу ітерацій- ним методом № X B1 B1X B2 B1X Nv v Y A1 A1Y A2 A2Y A3 A3Y Nv v υ 1 0,1 7 0,7 3 0,3 0,2 7 1,4 1 0,2 3 0,6 0,1 1 0,3 5 1,5 0,8 3 2,4 5 4 4 3,2 0,6 3 1,8 4 2,4 sum_r 3,8 4,2 3,8 sum_l 2,8 4,2 SUM_R 3,8 4,2 3,8 SUM_L 2,8 4,2 NextX 0,3 0,1 0,6 3,84 3,84 3,88 NextY 0,2 0,8 3,92 3,92 2 0,3 7 2,1 3 0,9 0,2 7 1,4 1 0,2 3 0,6 0,1 1 0,1 5 0,5 0,8 3 2,4 5 4 4 3,2 0,6 3 1,8 4 2,4 sum_r 3,8 4,2 3,8 Sum_l 4 3,8 SUM_R 7,6 8,4 7,6 SUM_L 6,8 8 NextX 0,3 0,1 0,6 7,68 3,84 3,86 NextY 0,2 0,8 7,76 3,88 … … … 12 0,1 7 0,7 3 0,3 0,2 7 1,4 1 0,2 3 0,6 0,1 1 0,3 5 1,5 0,8 3 2,4 5 4 4 3,2 0,6 3 1,8 4 2,4 sum_r 3,8 4,2 3,8 sum_l 2,8 4,2 SUM_R 48 48 45 SUM_L 43,2 47,2 NextX 0,3 0,1 0,6 46,2 3,85 3,85 NextY 0,2 0,8 46,4 3,87 Крок 1. Першу стратегію (переставлення X ) 1-й гравець обирає випад- ково із множини переставлень )( x m PE . Запишемо її покоординатно в сто- впець X таблиці. (Тут і далі курсивом викладено дії алгоритму в табличній формі). Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями … Системні дослідження та інформаційні технології, 2012, № 4 85 Крок 2. У таблиці в стовпці jB , де jb ( nJj∈∀ ) записуємо вектор- стовпець із номером j з матриці A . Обчислимо скалярні добутки векторів- стратегій jB другого гравця та вектора обраної стратегії першого гравця. У таблиці це зручно оформлювати, ввівши стопці: XBj — вектор, що складається з поелементних добутків векторів X та jB , nJj∈ . Ці век- тори ),,( XBBX jj займають m рядків табл. 1. У наступному рядку _sum l у стовпцях XBj записуємо скалярні добутки векторів jB та X (як сума елементів стовпця XB j табл.1). Крок 3. Знаходимо значення LSUM _ — накопичені суми скалярних добутків (у лівій частині табл. 1). У рядку LSUM _ табл.1 записуємо суму значень елементів рядка lsum _ та рядка LSUM _ із попереднього ( )1( −N -го) етапу. На першому кроці (коли 1=N ) рядок SUM збігається з рядком lsum _ цього етапу. Крок 4. Стратегія YNext другого гравця обирається з умови отримання ним максимального сумарного за N етапів платежу, як розв’язок задачі максимізації цільової функції на множині переставлень [2]. Практично це означає впорядкування елементів вектора xP так же як і елементи рядка LSUM _ (найменшому значенню з рядка LSUM _ — відповідне найменше значення з xP , тощо). Крок 5. Знаходимо значення vN — максимальний накопичений виграш другого гравця. Максимальне значення vN обчислюється як скалярний до- буток рядка SUM та стратегії .YNext Записуємо його в цьому ж рядку в стовпці vN . Крок 6. Знаходимо значення v . Обчислюємо значення за формулою N vNv = . Результат записуємо в цьому ж рядку в стовпці .v Крок 7. У стовпець Y записуємо значення стратегії другого гравця. У стовпець Y поокординатно заносимо значення рядка YNext лівої части- ни табл. 1. Крок 8. У правій частині табл. 1 у стовпці iA mJi∈∀ , записуємо век- тор стратегії першого гравця — рядок i з матриці .A Обчислюємо скалярні добутки вектора-стратегії другого гравця на вектори стратегій першого гравця — стовпці iA mJi∈∀ . У табл. 1 це зручно оформлювати, ввівши стопці: YAi — вектори, які складаються з поелементних добутків векто- рів Y та iA , mJi∈ . Вектори YAAY ii ,, займають n рядків табл. 1. Крок 9. Обчислюємо значення rsum _ та RSUM _ . У наступному ряд- ку rsum _ в стовпцях YAi записуємо скалярні добутки векторів iA та Y (як сума елементів стовпця YAi табл.1). На першому етапі (коли 1=N ) рядок RSUM _ правої частини табл. 1 збігається з попереднім рядком rsum _ правої частини табл.1. У наступному рядку RSUM _ табл.1 запи- суємо суму значень елементів рядка sum та рядка RSUM _ із попередньо- го ( )1( −N -го) етапу. О.О. Ємець, О.В. Ольховська ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 86 Крок 10. Стратегія NextX (права частина табл.1) першого гравця оби- рається з умови отримання ним мінімального сумарного за N етапів плате- жу (програшу), тобто розв’язок задачі мінімізації цільової функції на мно- жині переставлень [2]. Практично це означає впорядкування елементів вектора yP так само як і елементи рядка RSUM _ (найбільшому значенню з рядка RSUM _ — відповідає найменшому значенню з вектора ,yP тощо). Обрана стратегія записується в рядок XNext правої частини табл.1 та стов- пець X . Крок 11. Знаходимо значення vN — мінімальний накоплений програш другого гравця. Мінімальне значення vN правої частини табл.1 обчислю- ється як скалярний добуток рядка RSUM _ та стратегії NextX (правої частини табл. 1), його записуємо в цьому ж рядку в стовпці vN . Крок 12. За формулою N vNv = обчислюємо v . Обчислене значення за- носимо у стовпець v табл. 1. Крок 13. За формулою 2 vv + =υ обчислюємо .υ Отримане значення заносимо у стовпець υ табл. 1. Крок 14. Перевіряємо критерій завершення роботи алгоритму. Переві- ряється умова, що мінімальне зі знайдених значень v дорівнює максималь- ному зі знайдених значень v : vv maxmin = (рівність максимального вигра- шу першого гравця мінімальному програшу другого гравця). Якщо цей критерій завершення виконується, то алгоритм зупиняється. Інакше перехо- димо на крок 10 алгоритму, обравши за стратегію 1-го гравця стратегію .XNext За ціну гри приймають vv ==υ . Роботу алгоритму також можна завершити, якщо проведено вказану кількість ітерацій, або коли досягнута задана точність ε≤−=∆ vv maxmin , де 0ε > — задана величина, а vmin — мінімум зі знайдених v , vmax — максимум зі знайдених v або при \|)max\|\|min(\|)2/1( vv + ∆ =δ . При цьому ціна гри )max(min)2/1( vvV += . Наближені значення ,P Q (оптимальні мішані стратегії першого та другого гравців) — це вектори частот застосування своїх чистих стратегій– перставлень гравцями. Логічно вважати, що для забезпечення більшої точ- ності знаходження чистих стратегій гравцями, проводиться якомога більша кількість ітерацій. ІЛЮСТРАТИВНИЙ ПРИКЛАД РОБОТИ АЛГОРИТМУ Розглянемо роботу ітераційного методу розв’язування комбінаторних опти- мізаційних задач ігрового типу на переставленнях, коли на стратегії обох гравців накладаються комбінаторні обмеження. Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями … Системні дослідження та інформаційні технології, 2012, № 4 87 Нехай ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = 43 51 37 A , на стратегії першого гравця накладаються обмежен- ня, що визначаються переставленнями з множини }6,0;3,0;1,0{=xP , тобто { ),1,0;3,0;6,0(),1,0;6,0;3,0(),6,0;1,0;3,0(),6,0;3,0;1,0()(3 =xPE )3,0;6,0;1,0( }.)3,0;1,0;6,0( На стратегії другого гравця теж накладаються комбінаторні обмеження з множини }8,0;2,0{=yP , що визначені розміщеннями, тобто { }.)2,0;8,0(),8,0;2,0()(2 =yPE У табл. 1 вноситимемо результати розрахунків на кожній ітерації методу. Всі розрахунки (ітерації) будемо заносити в табл. 1, в якій N — номер кроку; X — вибрана стратегія першого гравця; nBBB ,...,, 21 — стратегії другого гравця; XBXBXB n,...,, 21 — скалярний добуток векторів; vN — максимальний накопичений виграш (максимальний із накопичених скаляр- них добутків LSUM _ та XNext ); N vNv = ; Y — вибрана стратегія другого гравця; mAAA ,..., 21 — стратегії другого гравця; числа в рядку з назвою LSUM _ — сума значень елементів рядка _sum l та рядка LSUM _ із по- переднього ( )1( −N -го) кроку; RSUM _ — сума значень елементів рядка _sum r та рядка RSUM _ із попереднього ( )1( −N -го) кроку. Коли 1N = рядок RSUM _ збігається з попереднім рядком цієї правої (лівої) частини табл.1 XNext — обрана стратегія першого гравця; YNext — обрана стра- тегія другого гравця; Nν — мінімальний накопичений платіж (програш) (скалярний добуток елементів векторів RSUM _ та Next Y ); N vNv = , N vNv = , 2 * vv + =υ . Першу чисту стратегію першого гравця виберемо довільно — нехай це, ).6,0;3,0;1,0( Перші дві та останній 120-й етап показано в табл. 1. Після 12 ітерації виконався критерій зупинки алгоритму рівності мак- симального виграшу першого гравця мінімальному програшу другого грав- ця. Отримаємо .85,3)()( ** == YFXF yx Стратегія )6,0;3,0;1,0( першого грав- ця використовувалась 3 рази, )6,0;1,0;3,0( — 9 разів. Для другого гравця: перша стратегія )8,0;2,0( використовувалась 11 разів, а )2,0;8,0( — 1 раз. Наближені значення мішаних стратегій ,P Q такі: для першого грав- ця частота використання стратегії )6,0;3,0;1,0( становить 25,0 12 3 = , отже, 25,01 ≈p , )6,0;3,0;1,0( дорівнює 75,0 12 9 = , 75,02 ≈p частоти застосувань усіх інших можливих стратегій — переставлень рівні 0 ( 0... 63 === pp ). Для другого гравця частоти застосування стратегії )8,0;2,0( — становить О.О. Ємець, О.В. Ольховська ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 88 12 11 1 =q , а стратегії )2,0;8,0( — 12 1 2 =q .Частоти приймаються за наближе- не значення ймовірностей. РЕЗУЛЬТАТИ ЧИСЛОВИХ ЕКСПЕРИМЕНТІВ За допомогою розробленої програмної реалізації цього методу, проведено числовий експеримент з метою виявлення залежності часу обчислень від вимірності задачі. Результати експерименту внесено в табл. 2, де: t — загальний час серії в секундах (с); серt — середній час задачі в секундах (с) або мілісекундах (мс); imt — середній час ітерації в мілісекундах (мс); vv maxmin −=∆ ; \|)max\|\|min\|()2/1( vv + ∆ =δ ; minδ — мінімальне δ в серії обчислень; maxδ — максимальне δ в серії обчислень. Для цього класу задач розв’язано по 100 задач вимірності nm× , при- чому nm = . Елементи ija матриці генерувалися як рівномірно розподілені цілі числа в інтервалі ],[ ba вказаному в стовпці інтервалів табл. 2. Елементи мультимножин xP , yP генерувалися за рівномірним розподілом за умов 1 1 =∑ = m i ix , 1 1 =∑ = n j jy . Максимальна кількість ітерації 1000. Вимірність задач задавалась в інтервалі від 10 до 700 (від 10 до 100 через 10; від 100 до 700 Т а б л и ц я 2 . Результати першої серії експериментів № m= =n ],[ ba t серt imt (мс) ∆ серє minδ maxδ серδ 10–4 10–5 1 10 [1,200] < 1 c 470мс <1 0,0119 1,06E–5 0,000354 0,000129 100 39 2 20 [1,400] 1 с 14 мс <1 0,0177 2,52E–5 0,000164 8,99E–5 100 66 3 30 [1,600] 3 с 30 мс <1 0,0246 3,27E–5 0,000164 8,26E–5 100 82 4 40 [1,800] 5 с 50 мс <1 0,0279 3,8E–5 0,000114 7,02E–5 100 94 5 50 [1,1000] 7 с 74 мс <1 0,0306 4,22E–5 9,85E–5 6,12E–5 100 100 6 60 [1,1200] 10 с 101 мс <1 0,0334 3,37E–5 8,33E–5 5,58E–5 100 100 7 70 [1,1400] 13 с 136 мс <1 0,0366 3,19E–5 7,12E–5 5,24E–5 100 100 8 80 [1,1600] 17 с 167мс <1 0,0394 3,44E–5 6,76E–5 4,93E–5 100 100 9 90 [1,1800] 21 с 214 мс <1 0,0419 3,27E–5 6,66E–5 4,65E–5 100 100 10 100 [1,2000] 25 с 255 мс <1 0,0451 3,12E–5 6E–5 4,51E–5 100 100 11 200 [1,4000] 3 хв,21с 1 с 1 0,0651 2,38E–5 4,13E–5 3,26E–5 100 100 12 300 [1,6000] 5 хв,4 2с 4 с 4 0,0831 2,21E–5 3,49E–5 2,77E–5 100 100 13 400 [1,8000] 10 хв,51с 6 с 6 0,106 2,18E–5 3,83E–5 2,65E–5 100 100 14 500 [1,10000] 17 хв,32с 10 с 10 0,129 2,06E–5 4,24E–5 2,6E–5 100 100 15 600 [1,12000] 24 хв,44с 14 с 15 0,206 2,07E–5 7,1E–5 3,48E–5 100 100 16 700 [1,14000] 35 хв,24с 21 с 21 0,201 2,05E–5 5,73E–5 2,88E–5 100 100 Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями … Системні дослідження та інформаційні технології, 2012, № 4 89 через 100). У кожній серії проведено 100000 ітерацій. У стовпцях 310− ( 410− , 510− ) вказано відсоток розв’язаних задач із зазначеною точністю по δ 310− , 410− , 510− відповідно. Із використанням пакета CurveExpert Professional 1.2.1 [15] побудовано аналітичний вигляд та графік регресійної залежності часу обчислень від ви- мірності задачі та величини δ від вимірності задачі для кожного з експери- ментів. Для першої серії експериментів залежності часу обчислень від ви- мірності задачі аналітичний вигляд функції такий: −= 20,00007)( mmT m2400,0− , при цьому коефіцієнт кореляції .99,0=r Аналітичний вигляд залежності величини δ від вимірності задачі такий: ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⋅= mm 1 292900004,0)(δ ; коефіцієнт кореляції .91,0=r У другій серії експериментів елементи ija матриці генерувалися як рівномірно розподілені цілі числа на проміжках від ]200,200[− до ]1400,1400[− , параметри nm = (вимірність) приймали значення від 10 до 700 відповідно. Час обчислень задач збільшувався зі збільшенням вимірнос- ті задачі від 1 сек до 35 хв, значення ∆ (середнє по 100 задачам вимірності) зростало від 0,026 до 0,418. Аналітичний вигляд залежності часу обчислень від вимірності задачі такий: 0,179+0,0060,00007)( 2 mmmT −= , коефіцієнт кореляції 98,0=r . У третій серії експериментів вимірність задач nm× )( nm = задавалась в інтервалі від 10 до 700 (від 10 до 100 через 10; від 100 до 700 через 100). Для кожної серії генерувалося по 100 задач. Елементи ija генерувалися, як рівномірно розподілені цілі числа в інтервалі ]100,100[− . Для кожної вимір- ності розв’язано по 100 задач. Час обчислень задач збільшувався зі збіль- шенням вимірності задачі від 1 сек до 5 хв, значення ∆ (середнє по 100 за- дачах вимірності) зростало від 0,013 до 0,00287. Аналітичний вигляд залежності часу обчислень від вимірності задачі одержано такий: 0,094+0,004 0,00007)( 2 mmmT −= , коефіцієнт кореляції .99,0=r У четвертій серії експериментів елементи ija матриці генерувалися, як рівномірно розподілені цілі числа в інтервалі ]10000,10000[− , при чому па- раметри nm = приймали значення від 10 до 700 відповідно (від 10 до 100 через 10; від 100 до 700 через 100). Для кожної серії генерувалося по 100 задач. Час обчислень задач збільшувався зі збільшенням параметрів задачі від 1 сек до 35 хв, значення ∆ (середнє по 100 задачах вимірності) змінюва- лося від 1,21 до 0,289. Аналітична функція залежності часу обчислень від вимірності задачі одержана така: 0,1950,0060,00007)( 2 +−= mmmT , кое- фіцієнт кореляції .99,0=r У п’ятій серії експериментів розв’язано по 100 задач вимірності ,nm× причому nm = , вимірність задач задавалась в інтервалі від 10 до 700 відпо- відно (від 10 до 100 через 10; від 100 до 700 через 100). Елементи ija матри- О.О. Ємець, О.В. Ольховська ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 90 ці генерувалися нормально розподілені цілі числа з параметрами ],[ xxM σ , де xM — математичне сподівання, xσ — середнє квадратичне відхилення. Параметри генерації ],[ xxM σ становить [0,3]. Час обчислень задач збіль- шувався зі збільшенням параметрів задачі від 1 сек до 35 хв, значення ∆ (середнє по 100 задачах вимірності) змінювалося від 0,000485 до 0,000128. Значення величини δ змінювалося від 0,0083 до 0,1430. Кількість розв’язаних задач із точністю 310− по δ у відсотковому співвідношенні для першої серії експериментів становила 86 % та зменшувалася до 5% розв’язаних задач при .700== nm Кількість розв’язаних задач із точністю 410− по δ у відсотковому співвідношенні було зафіксовано лише для 10== nm та становила 21 %, 20== nm — 5 %, 30== nm — 2 %. Для всіх інших серій цього експерименту не було розв’язаних задач. Аналітич- ний вигляд залежності часу обчислень від вимірності задачі для п’ятої серії експериментів одержано такий: , 0,192 0,0005+0,00007)( 2 −= mmmT коефіцієнт кореляції .98,0=r Проведено також експерименти з параметрами генерації ],[ xxM σ , що становлять [0,30]. Розв’язано по 100 задач вимірності nm× , причому .nm = Вимірність задач задавалась в інтервалі від 10 до 700 відповідно (від 10 до 100 через 10; від 100 до 700 через 100). Час обчислень задач збільшувався зі збільшенням параметрів задачі від 1 сек до 35 хв, значення ∆ (середнє по 100 задачах вимірності) змінювалося від 0,00686 до 0,0015. Значення вели- чини δ змінювалося від 0,00895 до 0,1430. Кількість розв’язаних задач із точністю 310− по δ у відсотковому співвідношенні для першої серії експе- риментів становила 83 % та зменшувалася до 1 % розв’язаних задач при .700== nm Кількість розв’язаних задач із точністю 410− по δ у відсотко- вому співвідношенні була зафіксована лише для 10== nm та становила 14 %, 20== nm — 6%, 30== nm — 1 %, для всіх інших серій цього екс- перименту не було розв’язано задач із точністю 10-4 по .δ Аналітичний ви- гляд залежності часу обчислень від вимірності задачі для п’ятої серії екс- периментів отримано такий: 0,188 +0,0060,00008)( 2 mmmT −= , коефіцієнт кореляції .99,0=r Під час дослідження проведених експериментів із параметрами генера- ції [ ]xxM σ, , що становлять ]300,0[ , розв’язано по 100 задач вимірності nm× , причому .nm = Вимірність задач задавалась в інтервалі від 10 до 700 відповідно (від 10 до 100 через 10; від 100 до 700 через 100). Час обчислень задач збільшувався зі збільшенням параметрів задачі від 1 сек до 36 хв, зна- чення ∆ (середнє по 100 задачах вимірності) змінювалося від 0,0642 до 0,0147. Значення величини δ змінювалося від 0,0108 до 0,0966. Кількість розв’язаних задач із точністю 310− по δ у відсотковому співвідношенні для першої серії експериментів становила 92 % та зменшувалася до 1 % розв’язаних задач при .700== nm Кількість розв’язаних задач із точністю 410− по δ у відсотковому співвідношенні була зафіксована лише для 10== nm та становила 15 %, 20== nm — 5%, для всіх інших серій цього Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями … Системні дослідження та інформаційні технології, 2012, № 4 91 експерименту задачі не розв’язувалися. Аналітичний вигляд залежності часу обчислень від вимірності задачі для п’ятої серії експериментів отримано та- кий: 0,187+0,0070,00008)( 2 mmmT −= , коефіцієнт кореляції .99,0=r Елементи мультимножини ,xP yP генерувалися за рівномірним розпо- ділом за умов 1 1 =∑ = m i ix , 1 1 =∑ = n j jy . Максимальна кількість ітерації 1000. У серії проведено 100000 ітерацій. Отже, усі проведені експерименти показують наближення платежів до ціни гри, що дає можливість наближеного знаходження ,P .Q ОЦІНКА СКЛАДНОСТІ АЛГОРИТМУ Для розрахунку складності алгоритму [16] складемо табл. 3, де у стовпці «Алгоритм» записано програмну реалізацію ітераційного методу (одна іте- рація) для розв’язування комбінаторних оптимізаційних задач ігрового типу на перестановках, в яких накладаються обмеження, що визначаються пере- ставленнями, на стратегії обох гравців. Час виконання різних рядків алго- ритму різний, але один і той рядок i виконується за час ic , де ic — конс- танта. Позначимо через jτ — кількість раз виконання умови. Під час розрахунку складності алгоритму потрібно визначити асимпто- тичну верхню границю з точністю до постійного множника [16]. Для функ- ції )(ng позначка )())(( nfngO = з [16] означає множину функцій таких, що існує додатня константа с і 0n така, що )()(0 nсgnf ≤≤ для всіх 0nn ≥ . Підрахуємо : 39 1 ∑ = = i jjcT τ ++++++++++= )(1 333231302516151181 ccccccccccT ++++++++++ )( 1413121097632 cccccccccn +++++++++++ )( 29282726242322211817 ccccccccccm )()()log()log()( 10201954 nTmTmmOnnOccccnm ++++++++ або ),()()log()log()()()()1( 00 mTmTmmOnnOnmOmOnOOT +++++++= якщо )()(),()( 10 nOnTmOmT == , то )()()log()log()()()()1( nOmOmmOnnOnmOmOnOOT +++++++= . Враховуючи, що ))(())((:0 nfOnfcOc =>∀ , то ),log()log()()()( mmOnnOnmOmOnOT ++++= якщо ∞<= ∞→ c ng nf n )( )(lim , то ))()(())(())(( ngnfOngOnfO +=+ , отже О.О. Ємець, О.В. Ольховська ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 92 ),log()log()()( mmOnnOnmOmnOT ++++= якщо ∞= ∞→ )( )(lim ng nf n , то )),(())(())(( nfOngOnfO =+ отже ).loglog( mmnnnmOT ++= Продовження табл. 3 № Алгоритм Час jc Кількість раз iτ 19 s := 0; 18c m 20 for j :=1 to cN do 19c nm begin – 21 s := s + cAy[j, i]; 20c nm end; – 22 cSumY[i] := s; 21c m 23 cSumYn[i] := cSumYn[i] + s; 22c m end; – 24 for i:=1 to cM do 23c m 25 IndArr[i] := i; 24c m 26 MakeInd(IndArr, cSumYn, cM, 0); 1 ( log )O m m [16] 27 cN_v := 0; 25c 1 28 for i:=1 to cM do 26c m begin – 29 cNextXp[i] := cNextX[i]; 27c m 30 cNextX[IndArr[i]] := cPx[i]; 28c m 31 cN_v := cN_v + cNextX[IndArr[i]] cSumYn[IndArr[i]]; 29c m end; – 32 c_v := cN_v / cIter- Num; 30c 1 33 cmax_v := max (c_v, cmax_v); 31c 1 34 cv_s := (cv_+ c_v) / 2; 32c 1 35 CheckStrat(0); 1 )(0 mT [16] 36 CheckStrat(1); 1 )(1 mT [16] 37 Result := CheckEval(aBreak Type, aMaxIter); 33c 1 Т а б л и ц я 3 . Оцінка складності алгоритму № Алгоритм Час jc Кількість раз iτ 1 inc(cIterNum); 1c 1 2 for i:=1 to cN do 2c n begin – 3 s := 0; 3c n 4 for j:=1 to cM do 4c nm begin – 5 s := s + cBx[j, i]; 5c nm end; – 6 cSumX[i] := s; 6c n 7 cSumXn[i] := cSumXn[i] + s; 7c n end; – 8 SetLength(IndArr, max (cN, cM) + 1); 8c 1 9 for i:=1 to cN do 9c n 10 IndArr[i] := i; 10c n 11 MakeInd(IndArr, cSumXn, cN, 1); 1 ( log )O n n [16] 12 cNv_ := 0; 11c 1 13 for i:=1 to cN do 12c n begin 14 cNextY[IndArr[i]] := cPy[i]; 13c n 15 cNv_:= cNv_+ cNextY[IndArr[i]] SumXn[IndArr[i]]; 14c n end; – 16 cv_:= cNv_/cIterNum; 15c 1 17 cminv_ := min (cv_, cminv_); 16c 1 18 for i:=1 to cM do 17c m begin – Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями … Системні дослідження та інформаційні технології, 2012, № 4 93 ВИСНОВКИ Для розв’язання комбінаторних оптимізаційних задач ігрового типу з обме- женнями-переставленнями, що накладаються на стратегії обох гравців, по- ширено ітераційний метод [8, 11]. Подано експериментальну та теоретичну оцінки кількості операцій та експериментально оцінено точність методу. Доцільним напрямом подальших досліджень є доведення збіжності запро- понованого ітераційного методу знаходження ймовірностей для стратегій- переставлень у задачі, що розглядається. ЛІТЕРАТУРА 1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комби- наторных задач оптимизации. — К.: Наук. думка, 1981. — 288 с. 2. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптиміза- ції. — К.: Інститут системних досліджень освіти, 1993. — 188 с. 3. Емец О.А., Колечкина Л.Н. Задачи комбинаторной оптимизации с дробно- линейными целевыми функциями. — К.: Наук. думка, 2005. — 117 с. 4. Емец О.А., Романова Н.Г. Оптимизация на полиперестановках. — К.: Наук. думка, 2010. — 105 с. 5. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. — К.: Наук. думка, 2008. — 159 с. 6. Павлов A.A., Павлова Л.А. Основы методологии проектирования ПДС- алгоритмов для труднорешаемых комбинаторных задач // Проблема ин- форматики и управления. — 1995. — № 4. — С. 135–141. 7. Емец О.А., Устьян Н.Ю. Исследование математических моделей и методов решения задач на перестановках игрового типа // Кибернетика и сист. ана- лиз. — 2007. — № 6. — С. 103–114. 8. Ємець О.О., Устьян Н.Ю. Розв’язування ігрових задач на переставленнях // Наукові вісті НТУУ «КПІ». — 2007. — № 3. — С. 47–52. 9. Емец О.А., Устьян Н.Ю. Решение некоторых задач комбинаторной оптимиза- ции на размещениях и перестановках игрового типа // Проблемы управле- ния и информатики. — 2006. — № 3. — С. 37–47. 10. Емец О.А., Устьян Н.Ю. Исследование задач комбинаторной оптимизации иг- рового типа на размещениях // Проблемы управления и информатики. — 2007. — № 1. — С. 26–36. 11. Ємець О.О., Устьян Н.Ю. Один ітераційний метод розв’язування ігрових задач на переставленнях // Наук. вісті НТУУ «КПІ». — 2008. — № 3. — С. 5–10. 12. Емец О.А., Устьян Н.Ю. Игры с комбинаторными ограничениями // Киберне- тика и сист. анализ. — 2008. — № 4 . — С. 134–141. 13. Емец О.А., Ольховская Е.В. Итерационный метод решения комбинаторных оп- тимизационных задач игрового типа на размещениях // Проблемы управле- ния и информатики. — 2011. — № 3. — С. 69–78. 14. Вентцель Е.С. Элементы теории игр. — 2-е изд. стереотип. — М.: Физматгиз, 1961. — 68 с. 15. Hyams Daniel G. Curve Expert Software. — 2011. — http://www.curveexpert.net. 16. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ: пер. с англ. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. Надійшла 11.05.2011

Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох гравців: ітераційний метод

Institution

Ähnliche Einträge