Back to Search
Start Over
An Efficient Algorithm of Dead-End Controls for Solving Combinatorial Optimization Problems.
- Source :
- Automation & Remote Control; Oct2021, Vol. 82 Issue 10, p1692-1705, 14p
- Publication Year :
- 2021
-
Abstract
- We propose a dead-end control algorithm for the exact solution of NP-hard combinatorial optimization problems. The efficiency of the algorithm is demonstrated by examples of solving the set-partition and 0-1 knapsack problems. The paper also shows that the use of the idea of dead-end controls when implementing the dynamic programming method can considerably reduce the number of problem state variables at each optimization step. A comparative analysis of the proposed method with known algorithms for solving these problems is carried out. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00051179
- Volume :
- 82
- Issue :
- 10
- Database :
- Complementary Index
- Journal :
- Automation & Remote Control
- Publication Type :
- Academic Journal
- Accession number :
- 153703547
- Full Text :
- https://doi.org/10.1134/S0005117921100076