Если вы спрашиваете, можете ли вы использовать жадный подход для решения проблемы, которая не имеет оптимального свойства подструктуры, короткий ответ - нет, не совсем.Позвольте мне объяснить:
- Жадные алгоритмы в основном берут все данные в задаче и затем устанавливают правило, которое они используют, чтобы определить, какие данные добавить в решение на каждом этапе этого алгоритма (по сути,Жадный метод выбирает локально оптимальные данные для добавления к решению в надежде, что это приведет к глобально оптимальному решению).
- Задача, имеющая свойство оптимальной подструктуры, означает, что (глобально) оптимальное решение может быть построено из (локально) оптимальных решений ее подзадач.
- Учитывая, что это свойство, по сути, является ключом к тому, что делает жадный подход, я бы сказал, что было бы плохой идеей использовать жадный подход для задачи «неоптимального единого решения».Надеюсь, это поможет!