середу, 18 листопада 2015 р.

Яку класичну задачу з інформатики бджоли можуть вирішувати ефективніше суперкомп'ютерів?

Лабораторні дослідження показали, що бджоли вміють вибирати оптимальний маршрут. Після локалізації розставлених в різних місцях квіток бджола робить обліт і повертається назад таким чином, що підсумковий шлях виявляється найліпшим. Таким чином, ці комахи ефективно справляються з класичною «завданням комівояжера» з інформатики, на вирішення якої потужні суперкомп'ютери можуть витрачати не один день.

Зада́ча комівояже́ра; (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.