ПРО СПОСОБИ ЗВЕДЕННЯ НЕРОЗВ’ЯЗНИХ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ДО РОЗВ’ЯЗНИХ

  • Н. К. Тимофієва Міжнародний науково-навчальний центр інформаційних технологій та систем НАН та МОН України
Ключові слова: підкласи розв’язних задач, функція натурального аргументу, комбінаторна функція, комбінаторна оптимізація, складність розв’язання задач, цільова функція, комбінаторна конфігурація

Анотація

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

Біографія автора

Н. К. Тимофієва, Міжнародний науково-навчальний центр інформаційних технологій та систем НАН та МОН України
науковий співробітник відділу комплексних досліджень інформаційних технологій

Посилання

1. Дейнеко В. Г. Розв’язність в комбінаторній оптимізації. Розв’язні випадки проблеми комівояжера та еврістичні алгоритми : автореф. дис. на здобуття наук. ступеня докт. фіз.мат.. наук: 01.05.01 / В. Г. Дейнеко. — Ін-т кібернетики ім. В. М. Глушкова НАН України. — К., 1995. — 48 с.
2. Демиденко В. М. Об экстремальных задачах на подстановках : автореф. дис. на здобуття наук. ступеня канд. физ.-мат. наук: 01.01.09 / В. М. Демиденко. — Ин-т математики АН БССР. — Минск, 1980. — 14 с.
3. Тимофієва Н. К. Теоретико-числові методи розв’язання задач комбінаторної оптимізації : автореф. дис. на здобуття наук. ступеня докт. техн. наук / Н. К. Тимофієва. — Ін-т кібернетики ім. В. М. Глушкова НАН України, Київ. — 2007. — 32 с.
4. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц ; пер. с англ. — М. : Мир, 1985. — 510 с.
5. Сергиенко И. В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации / И. В. Сергиенко,
М. Ф. Каспшицкая. — К. : Наук. думка, 1981. — 281 с.
6. Корбут А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкельштейн. — М. : Наука, 1969. — 368 с.
7. Михалевич В. С. Оптимизационные задачи производственно-транспортного планирования / В. С. Михалевич,
В. А. Трубин, Н. З. Шор. — М. : Наука, 1986. — 264 с.
8. Тимофеева Н. К. О некоторых свойствах разбиений множества на подмножества / Н. К. Тимофеева // УСиМ. — 2002. — № 5. — С. 6—23.
9. Тимофеева Н. К. Зависимость целевой функции задач комбинаторной оптимизации от упорядочения комбинаторных конфигураций / Н. К. Тимофеева // Компьютерная математика : сб. науч. тр. — 2005. — № 2. — С. 135—146.
10. Тимофієва Н. К. Метод структурно-алфавітного пошуку та підкласи розв’язних задач із класу задачі комівояжера / Н. К. Тимофієва // УСиМ — 2008. — № 4 — С. 20—36.
Опубліковано
2010-11-12
Як цитувати
[1]
Н. К. Тимофієва, ПРО СПОСОБИ ЗВЕДЕННЯ НЕРОЗВ’ЯЗНИХ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ДО РОЗВ’ЯЗНИХ, Вісник Вінницького політехнічного інституту, № 3, с. 240-244, Лис 2010.
Номер
Розділ
Фундаментальні науки