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

Автор(и)

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

Ключові слова:

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

Анотація

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

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

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

науковий співробітник відділу комплексних досліджень інформаційних технологій

Посилання

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.

##submission.downloads##

  • PDF
    Завантажень: 63
Переглядів анотації: 104

Опубліковано

2010-11-12

Як цитувати

[1]
Н. К. Тимофієва, «ПРО СПОСОБИ ЗВЕДЕННЯ НЕРОЗВ’ЯЗНИХ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ДО РОЗВ’ЯЗНИХ», Вісник ВПІ, вип. 3, с. 240–244, Листоп. 2010.

Номер

№ 3 (2011)

Розділ

Фундаментальні науки

Метрики

Завантаження

Дані завантаження ще не доступні.

Ліцензія

Автори, які публікуються у цьому журналі, згодні з такими умовами:

  • Автори зберігають авторське право і надають журналу право першої публі­кації.
  • Автори можуть укладати окремі, додат­кові договірні угоди з неексклюзив­ного поширення опублікованої журналом версії статті (наприклад, розмістити її в інститутському репозиторії або опубліку­вати її в книзі), з визнанням її первісної публікації в цьому журналі.
  • Авторам дозволяється і рекомендується розміщувати їхню роботу в Інтернеті (наприклад, в інституційних сховищах або на їхньому сайті) до і під час процесу подачі, так як це може привести до продуктивних обмінів, а також скорі­шого і ширшого цитування опубліко­ва­них робіт (див. вплив відкритого доступу).