Белгілі бір торлық есеп үшін динамикалық программалау əдісін қолдану

Abstract

В статье рассматривается задача нахождения кратчайшего расстояния от источника к стоку. Данная задача может быть реализована двумя способами: методом дискретного программирования на основе комбинаторики путем последовательного перебора всех вершин заданной сети и методом динамиче- ского программирования, основанном на функциональном уравнении Беллмана, распадающемся на два этапа: условная оптимизация и безусловная оптимизация. При нахождении оптимального решения сетевой задачи метод динамического программирования является более рациональным и эффектив- ным по отношению к другим методам, причем на каждом этапе итерационного процесса не происхо- дит ошибок вычислений.

The problem of a finding the shortest distance from a source to a drain is considered in the article. The given problem can be realized in two ways: a method of discrete programming on the basis of combination theory by consecutive search of all tops of the set network. Other way is a method of the dynamic programming, based on the functional equation of Bellman which breaks up to two stages: the first stage is a conditional optimization; and the second — unconditional optimization. The method of dynamic programming is more rational and effective in relation to other methods, and at each stage of iterative process there are no errors of calculations at a finding of the optimum decision of a network problem.