Как я устроился на копеечную ставку, чтобы решить нерешаемую задачу

Подмести весь супермаркет Albert Heijn? Звучит несложно. Собственно, так и должно быть.

Но я студент-информатик, и у меня есть одна проблема — склонность оптимизировать процессы, которые, быть может, оптимизации не требуют.

Поэтому вместо того, чтобы просто делать свою работу, ну то есть… подметать… я поступил так, как поступил бы любой здравомыслящий человек: превратил план этажа супермаркета в решётчатый граф, создал визуальный редактор и написал на C++ оптимизатор пути, используя алгоритм имитации отжига (simulated annealing).

Но прежде, чем переходить к рассказу о том, как всё пошло наперекосяк, и как я осознал, что из-за таких вот вещей страдаем мы все, задам вам один вопрос:

Если бы вы на один день взялись делать мою работу (я бы не советовал, но чисто теоретически), и вам нужно было бы подмести весь этаж в Albert Heijin, какой бы маршрут вы выбрали — А или B?

Я серьёзно. Рассмотрите их. Какой вам кажется более эффективным для подметания пола в супермаркете?

Если вы выбрали А, мои поздравления — вы мыслите как алгоритм и наверняка являетесь роботом. (Удачи вам с решением капчи).

Но в техническом смысле вы правы. По расстоянию путь А короче, хотя по факту он совершенно бесполезен.

Только посмотрите на эти бесконечные повороты. Просто представьте себе, что вы бы вот так ходили, всё время поворачивая. Да вы бы казались безумцем и выглядели как заглючивший Roomba (робот-пылесос, — прим. пер.).

Путь А — это то, что случается, когда вы делаете оптимизацию не с тем акцентом.

В этом и будет заключаться мораль всей истории. Но мы к ней ещё придём, а пока я объясню, как всё происходило.

Шаг 1: превращаем реальность в простейшую модель

Сначала я взял план супермаркета и превратил его в сетку. Каждая клетка сетки либо пуста (требует подметания), либо являетс?? препятствием (стена, касса, брошенный кем-то на пол пакет йогурта).

Далее я создал визуальный редактор в Processing (инструмент на базе Java для тех, кто любит всё приукрашать), чтобы можно было легко спроецировать план этажа на сетку и экспортировать полученную схему.

В общем, сделать из имевшегося плана сетку оказалось весьма просто.

Выложенная в супермаркете напольная плитка упростила деление всей площади на небольшие участки.

Теперь его можно было легко превратить в сетевую структуру, а именно граф, интерпретировав каждую клетку как узел и соединив эти узлы с соседями.  

Как видите, я допустил горизонтальное и вертикальное движение, а также диагональное (исключив перемещение сквозь стены).

Теперь оставалось только перебрать полученную сетку с условием посещения всех узлов (клеток). Полученный результат и стал бы решением моей задачи.

(Иначе эта задача называется «Задача коммивояжёра». По ссылке можете прочесть о ней [англ.] подробнее и узнать, почему её так сложно решить).

Шаг 2: написание оптимизатора

Поскольку в графе такого размера найти лучший путь через вычисление не получится, нужно использовать эвристику. Вместо поиска идеального решения (которое вряд ли возможно) эвристический подход стремится найти очень хорошее.

В итоге я реализовал на C++ оптимизатор пути и в качестве алгоритма эвристики использовал имитацию отжига.

Если вам этот алгоритм не знаком, то его механизм основан на опробовании серии небольших изменений (также называемых локальными перемещениями)

Сначала алгоритм принимает каждое небольшое изменение (даже если оно ухудшает путь), но в процессе выполнения постепенно становится всё придирчивей и допускает только те изменения, которые путь строго улучшают.

Принцип работы этого метода отражает процесс остывания металлов при отжиге. Алгоритм начинает с «высокой температуры», чтобы опробовать множес??во возможных вариантов, после чего температура постепенно снижается, и он сходится к более стабильному состоянию, выбирая лучшее решение.

Посмотрите на эту гифку. Здесь видно, что процесс начинается весьма хаотично и постепенно сходится к стабильному решению. Так работает имитация отжига.

В качестве локального перемещения я использовал метод 2-opt. Его смысл таков: вы удаляете два ребра из проложенного пути и воссоединяете ранее связанные ими узлы другими рёбрами. Если это небольшое изменение улучшает путь, сохраняете. В противном случае либо всё равно сохраняете (если температура ещё высока), либо отбрасываете. 

Потом просто делаете так миллиард раз. Вернее… ваш компьютер делает это миллиард раз.

Шаг 3: облом

Погоняв алгоритм какое-то время, я получил свой первый «оптимизированный» путь. Вот, что он мне предложил:

Только взгляните. Да у этого пути больше крутых поворотов, чем в фильме Кристофера Нолана. Ни один безумец не будет реально так подметать. Да вас в итоге стошнит, если даже попробовать.

Технически, он охватывает весь этаж. Технически, это (почти) кратчайший путь. Технически, он идеален.

Здесь есть удачные моменты, но в практическом смысле он абсолютно бесполезен.

Алгоритм сделал ровно то, что я просил (да и хорошо; страшно представить, если бы он сделал что-то совсем другое).

Просто я неправильно поставил задачу.

Шаг 4: оптимизируем под реальность

Я быстро понял, что оптимизировал не с тем акцентом. Расстояние — это не единственный важный момент.

Повороты тоже важны. Важен темп движения. Важно не выглядеть как глючный робот.

Поэтому я добавил в функцию затрат «штраф за повороты» и попросил алгоритм его минимизировать. По сути, я сказал ему: «Каждый поворот на 90° будет стоить тебе лишних баллов, а разворот на 180° — и того хуже».

В итоге маршруты стали более плавными, хотя расстояние чуть возросло.

Посмотрите. Вот так пройти уже реально. Такой маршрут можно поручить живому человеку и не бояться, что он тут же подаст заявление на увольнение.

Здесь мы оптимизируем уже не под расстояние, а под реальность.

Шаг 5: регулировка

А вот здесь начинается самое интересное.

Вы можете корректировать штраф за крутые повороты, используя это как своеобразный слайдер между «чистой эффективностью» и «реальной пользой».

И компромисс получается весьма наглядный. По мере увеличения штрафа маршрут становится плавнее, но и длиннее. Если же штраф уменьшается, то возрастает эффективность, а с ней и хаотичность.

Какой из маршрутов выбирать — решать вам. Всё зависит от того, насколько ловко вы можете поворачивать, насколько вам важно общее расстояние, и насколько устойчив ваш вестибулярный аппарат.

Шаг 6: горькая реальность

Но главная мораль истории всё же не в подметании полов.

Этот пример касается всего. К примеру, алгоритмы социальных сетей, оптимизированные на вовлечение пользователя. Они в этом реально хороши. И в чём же проблема?

Вовлечённость ? радость. Вовлечённость ? правда. Вовлечённость = клики, экранное время, помешательство и реактивность.

Какие последствия? Возмущение, распространение дезинформации, думскроллинг, тревожность.

Алгоритмы работают идеально и делают ровно то, для чего создавались. Ошибка лишь в функции затрат. (Разработчики Instagram вряд ли согласятся). Рекомендательные алгоритмы оптимизированы на увеличение времени просмотра и частоты кликов. Ваша бабушка может часами напролёт смотреть на YouTube сюжеты про теории заговоров.

Алгоритмы всё сломали. Бабушке от этого только хуже. И тут нечему удивляться.

Даже LLM вроде ChatGPT оптимизированы не на те показатели. Они ориентированы на то, чтобы звучать убедительно. Звучать так, будто они знают истинный ответ. И их задача не в том, чтобы быть правдивыми или честными.

Они обучены завершать шаблоны, а не отвечать «Я не знаю». Поэтому они просто гадают. Без малейшего стыда и грамматических ошибок. Причём всё это выходит за рамки техно-индустрии.

Вспомните о бизнесе. Большинство предприятий оптимизированы под наращивание прибыли. Наша планета, окружающая среда, мораль, этика? Все эти вещи не интегрированы в функцию затрат и в оптимизации не учитываются.

Использовал ли я этот оптимизированный путь в реальной работе?

Очевидно, нет. Я просто подметал пол, как обычный человек. Но процесс его поиска научил меня одной вещи, о которой я не забуду: нет никакого смысла в технической корректности, если вы решаете не ту задачу.

Вы можете писать идеальный код. Можете создавать безупречные системы. Можете заооптимизировать всё вусмерть с помощью функции затрат. Но на выходе всё равно может получиться отстой. Решающую роль играет не алгоритм оптимизации, а выяснение того, под какую метрику вообще нужно оптимизировать. Чаще всего мы даже не задаёмся этим вопросом. Мы просто оптимизируем процессы под то, что легко измерять, и надеемся, что сработает.

Спойлер: пожалуй, не сработает.

Если вы почерпнули из моих рассуждений что-то полезное, я рад. Если вам понравилось, как я чрезмерно усложнил простую задачу подметания пола, то и это здорово.

Так или иначе, спасибо за то, что прочли мой рассказ о попытке оптимизировать задачу, которая этого совсем не требовала.

Код моего оптимизатора доступен на GitHub.