Traveling Salesdog Problem: как собака решила задачу коммивояжёра быстрее, чем твой CI
Учёные доказали: собаки интуитивно находят короткие маршруты, а разработчикам остаётся только завидовать хвостатым оптимизаторам.
Пока мы мучаемся над NP-полными задачами и пишем велосипеды для TSP, учёные решили посмотреть, как с этим справляются собаки. Спойлер: они нас обставили.
Исследователи из Университета Западного Вайоминга (да, есть и такой) поставили эксперимент: собаке нужно было собрать мячики, разбросанные по полю, и вернуться к хозяину. Результат? Пёс находил маршрут, близкий к оптимальному, без единой строчки кода и без жалоб на отсутствие документации.
Алгоритм на четырёх лапах
Оказывается, собаки используют эвристику "ближайший сосед" — но с поправкой на нюх и лень. Вместо того чтобы перебирать все варианты (как мы любим), они просто бегут к ближайшему мячу, потом к следующему, и так далее. И это работает! Среднее отклонение от оптимального маршрута составило всего 12% — для NP-трудной задачи это практически идеально.
Разработчики, которые когда-либо писали свой TSP-решатель, сейчас чувствуют себя немного глупо. Особенно те, кто использовал генетические алгоритмы с 1000 поколений. Собака делает это за секунду, а ты сидишь и ждёшь, пока нейросеть дообучится.
Но не спешите увольнять свою команду Data Science. У метода есть ограничения: собака не работает с графами из 1000 городов и не умеет учитывать пробки. Зато она умеет вилять хвостом и не требует ревью кода.
Комментарий студии METABYTE: Если ваш продакшн можно оптимизировать так же интуитивно, как собака собирает мячики, — может, пора пересмотреть архитектуру? А если серьёзно, мы тоже за элегантные решения без лишнего оверкодинга.