Что такое оптимизация?

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

Во-первых, процесс принятия любой целевой функции к минимуму или максимуму.

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

Во-вторых, необходимо соблюдать ряд ограничений.

Как и в моем предыдущем примере, если необходимо прибыть в офис до 10:00 или если я не могу потратить на поездку более 10 рупий.

Таким образом, «Мое путешествие в офис» потребует, чтобы я выбрал кратчайший путь к своему офису, потратив не более 10 рупий, а также убедившись, что я доберусь до офиса до 10:00. Это оптимизация.

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

Решение . Нам доступно несколько, но позвольте мне начать с самого простого Алгоритма грубой силы.

Алгоритм грубой силы

Алгоритм грубой силы:

Шаг 1: Попробуйте все, все возможные комбинации предметов. То есть сгенерировать все подмножества возможных элементов. Это называется мощным набором.

Power Set «Пусть A будет множеством. Тогда вся совокупность всех подмножеств A называется Power Set».

Шаг 2: Удалите все комбинации, стоимость проезда которых превышает 10 рупий, а также удалите все комбинации, из-за которых я добираюсь до офиса после 10:00.

Это выглядит как простое решение. Однако возникает проблема, поскольку количество ограничений увеличивается, как и размер набора мощности. Например, если мне нужно выбрать из 100 элементов, тогда набор мощности будет иметь размер 1 267 650 600 228 229 401 496 703 205 376. Делая это вычислительно невозможным.

Таким образом, грубая сила не будет работать, и нам нужно что-то еще, чтобы найти мое решение, самый быстрый маршрут в мой офис с наименьшими затратами и быть там до 10:00 для посещаемости !!

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

Логика жадного алгоритма выглядит примерно так

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

Что здесь означает «лучший»?

Способ проезда, стоимость которого не превышает рупий. 10:00, а также позволяет мне добраться до офиса до 10:00.

Возьмем другой пример

Время обеда, я сажусь есть.

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

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