Часть вашей проблемы может быть вызвана мыслью о «жадных проблемах».Есть жадные алгоритмы и проблемы, где есть жадный алгоритм, который приводит к оптимальному решению.Существуют и другие сложные проблемы, которые также могут быть решены с помощью жадных алгоритмов, но результат не обязательно будет оптимальным.
Например, для задачи упаковки в бункер существует несколько жадных алгоритмов, каждый из которых имеет гораздо лучшую сложность, чемэкспоненциальный алгоритм, но вы можете быть только уверены, что получите решение, которое ниже определенного порогового значения по сравнению с оптимальным решением.
Только в отношении проблем, где жадные алгоритмы приведут к оптимальному решению, я думаюбыло бы, что индуктивное доказательство правильности чувствует себя абсолютно естественным и легким.Для каждого из ваших жадных шагов совершенно ясно, что это было лучше всего сделать.
Как правило, проблемы с оптимальными, жадными решениями в любом случае легки, а другие заставят вас придумать жадного.эвристический, из-за ограничений сложности.Обычно значимое сокращение показывает, что ваша проблема на самом деле, по крайней мере, NP-сложна, и, следовательно, вы знаете, что вам придется найти эвристику.Для тех проблем, я большой поклонник попробовать.Реализуйте свой алгоритм и попытайтесь выяснить, являются ли решения «довольно хорошими» (идеально, если у вас также есть медленный, но правильный алгоритм, с которым можно сравнивать результаты, в противном случае вам может потребоваться создать основную правду, созданную вручную).Только если у вас есть что-то, что работает хорошо, постарайтесь подумать, почему, а может быть, даже попытаться придумать доказательство границ.Может быть, это работает, может быть, вы заметите пограничные случаи, когда это не работает и нуждается в уточнении.