2024, випуск 2, c. 31-38
Одержано 11.03.2024; Виправлено 25.04.2024; Прийнято 28.05.2024
Надруковано 09.06.2024; Вперше Online 14.06.2024
https://doi.org/10.34229/2707-451X.24.2.3
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Про одну реалізацію природного підходу до вирішення задачi комівояжера
Державний університет Молдови, Кишинів
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Актуальність задачi комівояжера пов'язана з необхідністю розробки обчислювальних схем для використання в ситуаціях, що потребують аналізу інформації досить великого обсягу. Багатогранність досліджень щодо задачі комівояжера дозволяє розкривати багато властивостей і виявляти необхідні умови оптимальності рішення. Один із підходів теоретичних та практичних досліджень ґрунтується на комп'ютерній технології модифікованого розподільчого методу.
Мета роботи. Розробка умови оптимальності рішення та поняття триелементних операцій заміни для побудови відповідного алгоритму та отримання прийнятного рішення за невелику кількість застосовуваних операцій.
Результати. Введено поняття триелементна операція заміни. Наводиться необхідна умова оптимальності даного рішення та спеціальний спосіб конструювання допустимого циклічного рішення транспортної задачі, що відповідає задачі комівояжера. Пошук оптимального рішення здійснюється як перехід від одного циклічного рішення до іншого циклічного рішення триелементними операціями заміни. Такі операції заміни здійснюються для нульових елементів допустимого рішення з позитивним значенням матриці оцінок.
Висновки. У зв'язку з виникненням задач дискретної оптимізації з необхідністю аналізу досить великого обсягу інформації, потрібна розробка нових обчислювальних схем, що дають стабільно хороші результати. Дослідження в цьому напрямку проводяться на прикладі задачі комівояжера, для якої із застосуванням триелементних операцій заміни, можливе отримання прийнятного розв'язання задач.
Ключові слова: модифікований метод розподілу, триелементна операція заміни, природний підхід, задача комівояжера.
Цитувати так: Terzi D. On One Implementation of a Natural Approach to Solving the Traveling Salesman Problem. Cybernetics and Computer Technologies. 2024. 2. P. 31–38. https://doi.org/10.34229/2707-451X.24.2.3
Список літератури
1. Lazarev A.A., Werner F., et al. Special Issue “Recent Advances of Discrete Optimization and Scheduling”. Mathematics. 2024. 12. 793. https://doi.org/10.3390/math12060793
2. https://www.researchgate.net/topic/Travelling-Salesman-Problem/publications (звернення: 01.03.2024)
3. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.
4. Terzi D. A Natural Approach to Solving the Traveling Salesman Problem. Cybernetics and Computer Technologies. 2023. No. 4. P. 43–51. https://doi.org/10.34229/2707-451X.23.4.6
5. MATLAB Programming Fundamentals, R2023a, MathWorks, 2023. https://www.mathworks.com/products/matlab.html (звернення: 01.03.2024)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна