Здравствуйте. У меня стоит задача рассмотреть транспортную задача и задачу коммивояжера в совокупности. Но есть дополнительное условие, чтобы ко всей этой модели можно было применить жадный алгоритм. В связи с этим у меня вопрос, есть у кого-нибудь какие-либо мысли что нужно изменить, чтобы этот алгоритм был применим?
Также у меня возник вопрос по поводу применимости. Чтобы жадный алгоритм необходимо выполнение принципа жадного выбора и оптимальность для подзадач.
Доказательство принципа жадного алгоритма состоит в том, чтобы доказать на 1 шаге, что не теряется оптимальность глобального решения, а затем по индукции для
-случая. Вот меня и интересует вопрос, как же доказывается что оптимальность не теряется?
Мне бы саму идею подогнать, поиски по интернету не увенчались успехом.
