Вирішення транспортної задачі за допомогою квантового комп’ютера
Тип публікації :
Бакалаврська робота
Дата випуску :
2022
Автор(и) :
Турченко Євгеній Олександрович
Мова основного тексту :
ua
eKNUTSHIR URL :
Цитування :
[APA 7] Турченко, Є. О. (2022). Вирішення транспортної задачі за допомогою квантового комп’ютера [Бакалаврська робота, Київський національний університет імені Тараса Шевченка]. eKNUTSHIR. https://ir.library.knu.ua/handle/123456789/2796
[ДСТУ] Турченко Є. О. Вирішення транспортної задачі за допомогою квантового комп’ютера : кваліфікаційна робота бакалавра : 12 Інформаційні технології. Київ, 2022. 25 с. URL: https://ir.library.knu.ua/handle/123456789/2796 (дата звернення: 25.07.2026).
В роботі був написаний та проаналізований алгоритм для квантового комп’ютера, що виконує задачу комівояжера, тобто шукає найбільш оптимальний маршрут обходу графу із поверненням в початкову точку. Були проведені тести програми із різними варіантами вирішення задачі і порівняний час виконання алгоритму квантовим комп’ютером і класичним. Із результатів тестів видно, що навіть із усіма недоліками теперішніх квантових комп’ютерів, вони вже можуть значно краще виконувати такого роду задачі. Так, для пошуку шляху в графі з 50 вершин, квантовому комп’ютеру знадобилося всього 7.5 секунд, в той час як класичному – 829 секунд. Крім того, навіть із стандартними параметрами методу оптимізації, складність алгоритму для квантового комп’ютера складає 𝑂(𝑛 log (𝑛)), а в класичного з використанням генетичного алгоритму - 𝑂(𝑛^2).
Завдяки тому, що алгоритм реалізовано з використанням мови програмування Python, його можна легко змінювати для виключення маршрутів, зміни початкової і кінцевої точки маршруту. Крім того, можливо передавати результат виконання алгоритму зовнішнім програмам, для їх подальшого використання, наприклад, для візуалізації маршруту на карті.
Завдяки тому, що алгоритм реалізовано з використанням мови програмування Python, його можна легко змінювати для виключення маршрутів, зміни початкової і кінцевої точки маршруту. Крім того, можливо передавати результат виконання алгоритму зовнішнім програмам, для їх подальшого використання, наприклад, для візуалізації маршруту на карті.
Галузі знань та спеціальності :
12 Інформаційні технології
123 Комп’ютерна інженерія
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
949.34 KB
Контрольна сума :
(MD5):6c1cc1beba9b3444aa1d8c569b21ec06
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution-NonCommercial 4.0 International