Один із підходів до розв'язання задачі про знаходження оптимальної перестановки

Loading...
Thumbnail Image
Date
2005
Authors
Рибак, Михайло
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Серед задач, не розв’язаних за поліноміальний час, існує певний підклас задач, які розв’язуються ітеративно, причому кожна ітерація покращує розв’язок, який уже знайдено після всіх попередніх ітерацій. Таким чином, за умови існування певних обмежень на оціночну функцію розв’язку (наприклад, скінченність множини її значень) можна говорити про певну "поліноміальність" розв’язку - адже час, у гіршому випадку, лінійно залежить від потужності множини значень цієї функції. У праці розглянуто одну з таких задач і наведено відповідний ітеративний алгоритм.
Among the problems which cannot be solved in polynomial time there is a subclass ofproblems that can be solved by means ofcertain iterative process where each iteration is used to improve the result achieved by all the previous ones. Hence, provided there are some certain constraintsfor the criterion function (for instance, finiteness of it s range), there is a polynomial solution in some sense - the solution is linearly dependent on the potency of the range of thisfunction. In this work one can find an example of such iterative algorithm.
Description
Keywords
оціночна функція розв'язку, інтеративний алгоритм, продуктивність кодера
Citation
Рибак М. В. Один із підходів до розв'язання задачі про знаходження оптимальної перестановки / М. В. Рибак // Наукові записки НаУКМА : Комп'ютерні науки. - 2005. - Т. 36. - С. 94-97.