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

• Published in: Доповіді НАН України
• Date: 2014
• Main Authors: Ємець, О.О., Ольховська, О.В.
• Format: Article
• Language: Ukrainian
• Published: Видавничий дім "Академперіодика" НАН України 2014
• Subjects: Інформатика та кібернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/88141
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Монотонний ітераційний метод для розв’язування задач комбінаторної оптимізації ігрового типу на переставленнях / О.О. Ємець, О.В. Ольховська // Доповiдi Нацiональної академiї наук України. — 2014. — № 8. — С. 48-52. — Бібліогр.: 6 назв. — укр.

Запропоновано монотонний iтерацiйний метод пошуку цiни гри для розв’язування задачi комбiнаторної оптимiзацiї iгрового типу на переставленнях з обмеженнями на
 стратегiї одного гравця. Монотонний iтерацiйний метод дає змогу швидко отримати
 значення цiни гри iз заданою точнiстю та оптимальну стратегiю першого гравця, причому кiлькiсть крокiв методу слабко залежить вiд вимiрностi задачi. Предложен монотонный итерационный метод поиска цены игры для решения задачи комбинаторной оптимизации игрового типа на перестановках с ограничениями на стратегии
 одного игрока. Монотонный итерационный метод позволяет быстро получить значение цены игры с заданной точностью и оптимальную стратегию первого игрока, при этом количество шагов метода слабо зависит от размерности задачи. A monotone iterative method of searching for the game price for solving the combinatorial gametype optimization problems on permutations with restrictions on the strategy of one player is
 proposed. The monotonous iterative method allows one to quickly get the price value for a game
 with the specified accuracy and the optimal strategy for the first player. Moreover, the number of
 steps of the method weakly depends on the dimension of the problem.