Про подібність задач комбінаторної оптимізації та універсальність алгоритмів

Тимофієва, Н. К.

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

Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"


	Наукова періодика України		Системні дослідження та інформаційні технології