Как сбалансировать краткосрочные и долгосрочные цели

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

  1. Первый игрок выбирает число из начала или конца списка.
  2. Второй игрок выбирает число из начала или конца списка.
  3. Результатом каждого игрока является сумма выпавших чисел.
  4. Игра заканчивается, когда список пуст.

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

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

def optimize_output(numbers):
  # initialize the sum to zero
  total_sum = 0

  # keep track of the index of the first and last elements in the list
  start_pointer = 0
  end_pointer = len(numbers) - 1
  my_turn = True

  # keep going until the list is empty
  while start_pointer <= end_pointer:
    # if the first element is larger, select it
    if numbers[start_pointer] > numbers[end_pointer]:
      selected_value = numbers[start_pointer]
      start_pointer += 1
    # otherwise, select the last element
    else:
      selected_value = numbers[end_pointer]
      end_pointer -= 1
    
    if my_turn:
        total_sum += selected_value
    
    my_turn = not my_turn

  return total_sum

Преимущества

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

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

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

Ограничения

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

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

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

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

Пример

Предположим, у нас есть следующий список чисел:[5, 6, 9, 7]

Если мы используем жадный подход, первый игрок выберет число 7, а второй игрок выберет число 9. Максимальный результат для первого игрока будет 7 + 6 = 13.

Однако если вместо этого первый игрок выберет число 5, а второй игрок выберет число 7, максимальный результат для первого игрока будет 5 + 9 = 14. Это лучший результат, чем тот, который получен при использовании жадного подхода.

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

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

Узнайте больше об оптимизации с помощью Numbrail.

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