Введение

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

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

Понимание решения проблем

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

TL;DR: Следующий афоризм решения задач полезен как в математике, так и в жизни:

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

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

Применимость для решения типичной практической задачи

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

Примером того, как это понимание может быть практически полезным, является сценарий планирования поездки, описанный во введении. Давайте начнем с того, что сформулируем задачу «Как спланировать хорошую длинную поездку на выходные для двоих?» как компромисс между удобством и стоимостью, поставив вопрос «Как спланировать достаточно хорошую поездку на выходные?» поездка на выходные на двоих по минимально возможной цене?»». Вместо ответа на поставленный вопрос зачастую проще ответить на следующий: «Могу ли я спланировать достаточно хорошую длинную поездку на выходные на двоих не более чем за 1000 долларов США?». Ответ на этот более простой вопрос, ориентированный на целевой бюджет, для нескольких значений бюджета поездки и выбор наименьшего бюджета с жизнеспособным решением — хороший подход к поиску решения исходной проблемы.

Мы можем применить нашу технику решения проблем рекурсивно, чтобы ответить на более простой вопрос. Если мы сформулируем вопрос «Могу ли я спланировать достаточно продолжительную поездку на выходные для двоих не более чем за 1000 долларов США?» как компромисс между удовольствием и отдыхом, его можно сформулировать так: «Могу ли я спланировать достаточно приятная длинная поездка на выходные для двоих не более чем за 1000 долларов США и максимальное время для отдыха?». Вместо ответа на этот вопрос мы можем ответить на следующий: «Могу ли я спланировать достаточно приятную длинную поездку на выходные для двоих не более чем за 1000 долларов США, выделяя при этом не менее 12 часов на сон и отдых каждый день?” . Как и прежде, мы отвечаем на последний вопрос для нескольких значений времени релаксации в сутки и выбираем наибольшее такое значение, которое допускает жизнеспособное решение.

Может случиться так, что можно сэкономить деньги, если быть излишне скупым и долго ходить пешком, а не брать машину. Чтобы избежать таких нежелательных решений, можно либо (1) применить меры здравого смысла, такие как аренда автомобиля для поездок на дальние расстояния, (2) попробовать разные значения времени отдыха в день с учетом некоторого разумного минимального требуемого значения, например 10 часов в день. (аналогично, допустимый предел бюджета составляет, скажем, 2500 долларов).

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

Для многогранных целей сначала установите цели для измеримых, контролируемых аспектов.

Применимость для решения сложной математической задачи

Как и было обещано, мы начинаем этот раздел с задачи с недавнего соревнования по программированию, не имеющей практической подоплеки. Чтобы представить сложность в некотором практическом контексте, большинство технологических компаний сочли бы эту проблему слишком сложной, чтобы задавать ее на собеседовании по программированию, но по стандартам ICPC это считается легкой задачей конкурентного программирования.



Задача C — Codeforces Round #763 (Div. 2)
codeforces.com



Мы начинаем с n кучек камней, помеченных последовательно, где кучка i изначально содержит h[i] камней. Затем мы перебираем стопки от стопки 3 до стопки n в этом порядке. Когда мы находимся в куче i, мы можем выбрать число d[i] такое, что 3d[i]≤h[i] и переместить d[i] камней из кучи i в кучку i-1 и 2d[i] камней из i в кучку i-2. В результате h[i] уменьшается на 3d[i], h[i-1] увеличивается на d[i], а h[i-2] увеличивается на 2d[i]. Цель состоит в том, чтобы «выбрать значения от d[3] до d[n] так, чтобы в конце процесса наименьшая стопка была как можно больше». Пример задачи вместе с оптимальным решением показан на соседнем рисунке 1.

Поначалу к этой проблеме трудно подойти, поскольку пространство поиска возможных наборов решений [наивная граница: (max_h/3)^(max_n)= (10⁹/3)²⁰⁰⁰⁰⁰ ›(10⁸)²⁰⁰⁰⁰⁰=10¹⁶⁰⁰⁰⁰⁰] смехотворно велико, и мы можем выполнить только ~10⁸ операции в 1-секундном ограничении времени выполнения, указанном в условии задачи. Каждое из n-2 решений от d[3] до d[n] можно рассматривать как перенести как можно больше камней, оставив при этом достаточное количество. Однако в количественном отношении неясно, что означает достаточно оставить позади.

Мы используем технику решения задач, описанную выше. Вместо попытки «выбрать значения от d[3] до d[n] таким образом, чтобы в конце процесса наименьшая стопка была как можно больше», мы отвечаем на целенаправленный вопрос «Можем ли мы выбрать значения от d[3] до d[n] так, чтобы в конце процесса наименьшая стопка была размером не менее a?». Обратите внимание, что ответ на этот вопрос Yesдля a=1 и No для a=max_h+1. По мере увеличения a с 1 до max_h+1 обратите внимание на следующее:

Существует некоторое значение q такое, что ответ равен Yes для a≤q и No для a>q .

Это значение q является ответом на исходную проблему. Если мы сможем быстро ответить на поставленный выше вопрос, скажем, за время O(n), то мы сможем выполнить двоичный поиск q и решить задачу за время O(n・log(max_h)), что удобно завершит выполнение за 1 секунду [обратите внимание, что max_n・log(max_h)≤(2・ 10⁵)・30=6・10⁶].

Мы свели проблему к задаче быстрого ответа на вопрос, ориентированный на цель. Для начала обратите внимание, что для данного целевого значения a минимального размера стопки решение d[n] является простым, поскольку h[n] не зависит ни от каких других решений. Мы выбираем d[n] как можно больше, оставляя не менее a камней в стопке n. Если h[n]<a, то делаем вывод, что цель a невыполнима, и останавливаем процесс. В противном случае мы выбираем d[n]=⌊(h[n]-a)/3⌋. Затем мы уменьшаем h[n] на 3d[n], увеличиваем h[n-1] на d[n] и h[n-2] на 2d[n].

Какое решение мы примем теперь, когда принято одно решение? Обратите внимание, что на h[n-1] влияют только d[n] и d[n-1]. Первое уже определено, что позволяет нам теперь решить последнее. Как и раньше, если h[n-1]<a, мы останавливаемся и сообщаем, что цель нежизнеспособна, а в противном случае мы оставляем достаточное количество камней, пытаясь выбрать d[n-1] как ⌊(h[n-1]-a)/3⌋. Мы уменьшаем h[n-1] на 3d[n-1], увеличиваем h[n-2] на d[n-1] и h[n-3] на 2d[n-1]. Мы продолжаем в том же духе и принимаем решения от d[n] до d[3], устанавливая d[i]=⌊(h[i]-a)/3⌋если не h[i]<a,, и в этом случае мы превентивно останавливаем нашу процедуру. Если мы достигаем конца всех итераций, мы сообщаем, что жизнеспособное решение существует, если h[i]≥a для всех i от 1 до n. Обратите внимание, что нам нужно проверить это условие только для i=1 и i=2. Этот процесс быстрый и занимает O(n) времени по желанию. Рисунок 2 изображает эту процедуру с примером. Интересно отметить следующее:

Решения выполняются слева направо, но принимаются справа налево.

Внимательный читатель заметит, что выделенное выше утверждение, ставшее ключевым для решения ориентированной на цель версии задачи, также имеет еще одно важное последствие: в изложенном до сих пор алгоритме есть ошибка. Рассмотрим вторую итерацию принятия решения. Если h[n-1]≥a , то мы хотим установить d[n-1]=⌊(h[n-1]-a)/3⌋. Обратите внимание, однако, что это может быть невозможно, как показано на рисунке 3. Это желаемое значение d[n-1] основано на значении h[n-1], уже увеличенном на d[n]. В то время, когда решение d[n-1] будет выполнено, это приращение еще недоступно для использования, а количество камней в куче n-1 равно h_initial[n-1], что совпадает с начальным размером этой кучи. Если мы выберем d[n-1]>⌊h_initial[n-1]/3⌋, решение будет недействительным, потому что из стопки n-1 потребуется вынуть больше камней, чем в этой куче, что абсурдно. Чтобы исправить эту ошибку для общего индекса i, мы выбираем d[i]=min(⌊(h[i]-a)/3⌋,⌊h_initial[i]/3⌋), а не ранее предложенное значение ⌊(h[i]-a)/3⌋. На рис. 3 на примере показано, как эта модификация устраняет проблему.

На этом описание нашего O(n・log(max_h)) решения завершено. Как указано выше, это удобно работает при ограничении времени в 1 секунду. Полный рабочий код можно найти здесь. В соседнем фрагменте 1 показана часть этого кода, которая решает целевую задачу «Можем ли мы выбрать значения от d[3] до d[n] так, чтобы в конце процесса наименьшая стопка была не меньше a?”. Функция f выполняется за O(n) времени и возвращает true, если a является жизнеспособной целью, и false в противном случае.

Есть еще несколько подобных задач, для которых этот метод решения задач с постановкой целей полезен в сочетании с бинарным поиском по ответу [1, 2, 3]. Это особенно полезно при минимизации максимального значения или максимизации минимального значения конфигурации, как в данном случае.

Как и в конце предыдущего раздела, давайте отметим еще одно понимание, которое основывается на основном понимании. В приведенной выше задаче мы столкнулись с (n-2)-мерным решением выбора величин от d[3] до d[n]. После установки целевого значения мы сначала приняли подрешение d[n], потому что оно было самым простым. После этого мы итеративно принимали подрешения в порядке убывания индекса, принимая самое простое подрешение на каждой итерации. Мы делаем следующий абстрактный вывод:

Для многомерных решений сначала примите самые простые подрешения.

Заключение

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

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

Для многогранных целей сначала ставьте цели для поддающихся количественному измерению и контролируемых аспектов.
Для многомерных решений сначала принимайте самые простые подрешения.

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