Яку
класичну задачу з інформатики бджоли можуть вирішувати ефективніше
суперкомп'ютерів?
Лабораторні дослідження показали, що бджоли вміють вибирати оптимальний
маршрут. Після локалізації розставлених в різних місцях квіток бджола робить
обліт і повертається назад таким чином, що підсумковий шлях виявляється
найліпшим. Таким чином, ці комахи ефективно справляються з класичною «завданням
комівояжера» з інформатики, на вирішення якої потужні суперкомп'ютери можуть
витрачати не один день.
Зада́ча комівояже́ра; (комівояжер — бродячий торговець; англ. Travelling
Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у
знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по
одному разу. В умовах завдання вказуються критерій вигідності маршруту
(найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці
відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через
кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових
циклів.
Немає коментарів:
Дописати коментар