Учені запропонували близьке до оптимального розв’язання асиметричної задачі комівояжера


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

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

Розв’язання даної задачі відноситься до класу NP-проблем, як і більшість окремих способів її розв’язання. Проте вчені вже пропонували розв’язання, які не перевершують оптимальну вартість більше як у 1,5 рази. Такі рішення вважаються кращими.

Асиметрична задача комівояжера

Вихідна задача комівояжера припускає, що маршрут між двома містами в обох напрямах має однакову вартість, що суперечить умовам реального світу. Прикладом служать ціни на авіаквитки між містами РФ і Європи. Саме такий тип проблем реального світу і називається асиметричною задачею комівояжера.

І, на відміну від вихідної задачі комівояжера, дослідники не могли знайти близьке до оптимального розв’язання для маршруту, що пролягає через велику кількість міст. До моменту, коли співробітники Федеральної політехнічної школи Лозанни і Лондонської школи економіки запропонували свій підхід до розв’язання проблеми.

Складність асиметричної задачі

Коли дана задача припускає, що той самий маршрут між двома точками в обох напрямах має різну вартість, то з’являється набагато більша кількість альтернативних шляхів, які необхідно розглянути.

Як говорить один з авторів статті, Ола Свенссон, розробка нового підходу почалася ще 2008 року. За цей час він придумав розв’язання для простішої проблеми об’єднання міст у групи і відвідування принаймні одного міста з кожної групи.

Ідея нового алгоритму

Потім, вже зі своїми колегами Якубом Тарнавскі і Ласло Вегхом, він почав розробку алгоритму, який ітеративно формує менші підгрупи в групах міст, до тих пір, поки не знайде оптимальні маршрути всередині кожної з них. Потім вже знайдені шляхи всередині груп, використовуючи раніше розроблений Свенссоном алгоритм, складаються в єдиний глобальний маршрут.

Думки експертів

Кен Реган з Університету Баффало визначив вклад учених:

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

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

Джерело: Quanta Magazine

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *