Как доказать, что жадные подходы не сработают
Для любой данной задачи, где жадные подходы не дадут оптимального значения, мы можем найти встречный пример, чтобы опровергнуть этот подход.
Однако можно ли доказать, что для данной задачи любой жадный подход вообще не будет работать?1 ответ:
Самый общий ответ, который я могу придумать, заключается в том, что любой жадный алгоритм найдет локальные оптимумы. Если задача имеет несколько локальных оптимумов, где только один из них представляет глобальный оптимум, то любой жадный алгоритм может застрять на одном из локальных оптимумов.
Чтобы найти встречный пример, все, что вам нужно сделать, это вычислить экземпляр задачи, который имеет такой локальный оптимум, и построить его так, чтобы вы "обманули" алгоритм в этот локальный оптимум.
Я не думаю, что есть общий способ показать, что жадный подход не будет работать. Лучший способ опровергнуть алгоритм-это, вероятно, найти встречный пример, где он не дает правильного результата.