Сущность жадного алгоритма, описание кодов Хаффмана. Сущность задачи об одномерной оптимальной упаковке, её математическая постановка, уравнение Беллмана. Суть метода динамического программирования. Способы представления графа в памяти компьютера.
Аннотация к работе
Жадный алгоритм и его реализация.В основу метода динамического программирования положен принцип оптимальности, сформулированный в 1957 г. американским математиком Ричардом Беллманом: «Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные состояние и решение в начальный момент времени, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения». Процесс, о котором идет речь, представляет собой управляемый процесс, т.е. имеется возможность выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге. Рассмотрим на примере задачи о рюкзаке, что понимается под шагом, состоянием, управлением и выигрышем. Общий принцип, лежащий в основе решения задач динамического программирования: каково бы ни было состояние процесса перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным. Управление, в котором достигается максимум в (4.4), и есть условное оптимальное управление Ui(s) на i-м шаге, а сама величина Wi(s) - условный оптимальный выигрыш на всех шагах, начиная с i-го и до конца.