Что такое оптимизация?
Оптимизацию можно определить как задачу, состоящую из двух частей.
Во-первых, процесс принятия любой целевой функции к минимуму или максимуму.
Реальным примером оптимизации может быть поиск кратчайшего пути от моего дома до моего офиса.
Во-вторых, необходимо соблюдать ряд ограничений.
Как и в моем предыдущем примере, если необходимо прибыть в офис до 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.
Возьмем другой пример
Время обеда, я сажусь есть.
У меня есть ценность для еды, которую я ем, я ценю сладости больше, чем мои овощи. Тем не менее, у меня есть бюджет калорий, который я не могу превысить тысячу калорий за один прием пищи. Теперь, это проблема оптимизации. То, что мне нужно контролировать, это мое желание хорошей еды с учетом дневного лимита калорий.
Я могу выбирать разные продукты в зависимости от своего вкуса и лимита калорий. Однако мы должны быть готовы к различным ответам, поскольку локальные оптимальные решения никогда не являются глобальными оптимальными решениями, как показано на рисунке ниже.