Мне заплатили минимальную зарплату за решение неразрешимой проблемы.

Подметаем весь пол Альберта Хейна. Звучит просто. И должно было быть просто.

Но я студент факультета информатики, и у меня есть проблема: я не могу перестать пытаться оптимизировать вещи, которые (вероятно) не нуждаются в оптимизации.

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

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

Если бы вы взяли на себя мою работу на один день (я бы не рекомендовал это, но гипотетически) и вам нужно было подмести весь пол Альберта Хейна, вы бы выбрали путь А или Б?

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

Если вы выбрали путь А: поздравляю, вы мыслите как алгоритм и, скорее всего, являетесь роботом. (Удачи в вопросах CAPTCHA.)

Но технически вы правы. Путь А короче по расстоянию. Однако это абсолютно бесполезно.

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

Путь А — это то, что происходит, когда вы оптимизируете не то, что нужно.

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

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

Я построил визуальный редактор в Обработка (инструмент Java для людей, которым нравится, чтобы все выглядело круто), поэтому я мог легко составить карту магазина и экспортировать полученный график.

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

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

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

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

Единственное, что нужно было сделать дальше, — это найти цикл через эту сеть, при этом обязательно посетив все узлы (тайлы). Тогда это было бы решением моей проблемы с подметанием.

(Эту проблему еще называют Задача коммивояжераподробнее см. статью и почему это так сложно «решить».)

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

Поэтому я реализовал оптимизатор пути на C++.

Базовый эвристический алгоритм: имитация отжига.

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

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

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

Посмотрите эту гифку. Видите, как все начинается хаотично и постепенно превращается во что-то стабильное? Это имитация отжига, делающая свое дело.

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

Затем просто сделайте это 1 миллиард раз. Или ну… пусть ваш компьютер сделает это 1 миллиард раз.

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

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

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

В нем есть несколько хороших моментов, но практически он абсолютно бесполезен.

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

Я просто задал неправильный вопрос.

Я быстро понял, что оптимизировал не для того. Расстояние – это еще не все.

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

Поэтому я добавил к функции стоимости «штраф за поворот» и попросил ее также минимизировать его. По сути, говоря алгоритму: “Поворот на 90 градусов стоит вам дополнительных очков. Поворот на 180 градусов? Вы с ума сошли”.

Это привело к более плавным маршрутам, даже если это немного увеличило расстояние.

Посмотрите на это. На самом деле… по нему можно ходить. Вы могли бы дать этот путь реальному человеку, и он не сдался бы на месте.

Мы больше не оптимизируем расстояние. Мы оптимизируем реальность.

Вот где это становится весело.

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

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

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

Однако речь идет не только о подметании полов.

Это обо всем.

Алгоритмы социальных сетей оптимизируют взаимодействие. Они действительно хороши в этом. Проблема?

Помолвка ≠ счастье. Вовлеченность ≠ правда. Вовлеченность = клики, время перед экраном, ярость и реакция.

Последствия? Возмущение, дезинформация, обреченность, тревога.

Алгоритмы работают идеально. Он делает именно то, для чего был разработан. Функция затрат просто неверна. (Инстаграм, вероятно, подумает иначе.)

Алгоритмы рекомендаций оптимизируют время просмотра и рейтинг кликов. Твоя бабушка уже 6 часов смотрит теории заговора на YouTube.

Алгоритм раздавил его. Она чувствует себя дерьмом.

Никаких сюрпризов.

Даже LLM (большие языковые модели), такие как ChatGPT, оптимизируются не для того. Они оптимизируют звучание, чтобы звучать уверенно. За то, что они звучат так, будто знают ответ.

Не за то, что он прав. Не за честность.

Их учат заполнять шаблоны, а не говорить: «Я не знаю». Так что они просто догадываются. Без всякого стыда и с идеальной грамматикой.

Это относится даже к вещам, выходящим за рамки технологий.

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

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

Нет. Очевидно, нет. Я просто подмел пол, как нормальный человек.

Но создание этого проекта научило меня кое-чему, о чем я постоянно думаю: техническая правильность бесполезна, если вы решаете неправильную задачу.

Вы можете написать идеальный код. Вы можете построить безупречные системы. Вы можете оптимизировать свою функцию затрат. И у вас все равно может получиться что-то отстойное.

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

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

Спойлер: скорее всего, нет.

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

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

Хотите больше подобных экспериментов? Больше алгоритмов, интересных технологий и периодических разглагольствований о продуктивности и экономике внимания? Подпишитесь бесплатно ниже! (Без спама, только 1/2 раза в месяц)

Репозиторий GitHub (код): здесь