|
eaDonNTU, Donetsk >
Научные труды ДонНТУ >
Серія: Інформатика, кібернетика та обчислювальна техніка >
Випуск 1 (19) >
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://ea.donntu.ru/handle/123456789/30900
|
| Название: | Новітній метод розв’язання задач комбінаторної оптимізації великої розмірності |
| Другие названия: | Новый метод решения задач комбинаторной оптимизации большой размерности
A novel method for solving large-scale combinatorial optimization problems |
| Авторы: | Погорілий, С.Д.
Потебня, А.В.
Погорелый, С.Д.
Pogorilyy, S.D.
Potebnia, A.V. |
| Ключевые слова: | задачі комбінаторної оптимізації
мінімальна опукла оболонка
задача комівояжера
картографічні сервіси
алгоритм Джарвіса
м’який реальний час
розбиття графів
NP-складні задачі
граф
задачи комбинаторной оптимизации
минимальная выпуклая оболочка
задача коммивояжера
картографические сервисы
алгоритм Джарвиса
мягкое реальное время
разбиение графов
NP-сложные задачи
combinatorial optimization problems
minimal convex hull
travelling salesman problem
map services
Jarvis march
soft real-time
graph partition
NP-hard problems
graph |
| Дата публикации: | 2014 |
| Издатель: | ДонНТУ |
| Библиографическое описание: | Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка : збірник статей. Вип. 1(19) / ДВНЗ "ДонНТУ" ; редкол.: О.Є. Башков (голов. ред.) та ін. - Донецьк : ДВНЗ "ДонНТУ", 2014. |
| Аннотация: | Вперше запропоновано ефективний метод розв’язання складних задач оптимізації в режимі м’якого реального часу. Формування розв’язків відбувається за допомогою розподілу множини вершин графа на сукупність оболонок та їх сполучення. Виконано низку експериментальних досліджень алгоритму та показано придатність його використання для
розв’язання задачі комівояжера. Наведено рекомендації щодо застосування методу при
розв’язанні прикладних задач. |
| Описание: | In this paper an effective method is first suggested for soft real-time solving large instances of optimization problems. The new method recursively splits the input graph vertices set into hulls and merges them into final result.
A set of algorithm investigations is conducted and its suitability for solving the travelling salesman problem is
demonstrated. The developed method can produce good quality solutions quickly due to O (n^2) time complexity and linear memory usage. Another important advantage of the new algorithm is its ability to parallel execution.
The special program tool for real-time geographic routes calculation is designed based on the developed algorithm. Recommendations of method usage for applied tasks solving are provided. |
| URI: | http://ea.donntu.org/handle/123456789/30900 |
| Располагается в коллекциях: | Випуск 1 (19)
|
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.
|
