Graphical method to solve combinatorial optimization problems
- 作者: Gafarov E.R.1
-
隶属关系:
- Trapeznikov Institute of Control Sciences
- 期: 卷 77, 编号 12 (2016)
- 页面: 2110-2117
- 栏目: Topical Issue
- URL: https://journals.rcsi.science/0005-1179/article/view/150489
- DOI: https://doi.org/10.1134/S000511791612002X
- ID: 150489
如何引用文章
详细
Proposed was a graphical method to solve decomposable problems of combinatorial optimization with the of use the Bellman optimality principle. In distinction to the dynamic programming algorithms based on the same principle, the graphical algorithm considers all possible system states by groups and not separately. This becomes possible if one takes into account the analytical form of the objective function, that is, handles the function “graph” and transforms it analytically at each stage. The graphical method enables one to reduce running time of solution of some problems and construct efficient approximation schemes. The results of numerical experiments corroborate efficiency of the of the graphical method.
作者简介
E. Gafarov
Trapeznikov Institute of Control Sciences
编辑信件的主要联系方式.
Email: axel73@mail.ru
俄罗斯联邦, Moscow
补充文件
