Portal de Periódicos da CAPES

Analysis of the Effectiveness of Composite Versions of Backtracking Algorithms

2021; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-030-71119-1_24

1876-1119

V. O. Groppen,

Interconnection Networks and Systems

The effectiveness of two versions of backtracking algorithm solving a knapsack problem is investigated. The criterion for effectiveness is the running time to find a global optimal solution. One of the investigated algorithms is a composite version of backtracking procedure, combining backtracking branching strategy, B&B method of choosing the direction of movement by a search tree, and cutting off unpromising search directions used in dynamic programming. Since one of the research goals was to test the effectiveness of the proposed approach in relation to relatively “weak” mobile gadgets, two series of experiments were carried out with such devices. In the first series of experiments was used Microsoft Lumia 950 smartphone, with 3 GB RAM, 192 GB external memory, Windows 10 Mobile operating system, whereas in the second series with this gadget was used Samsung N150 laptop with 1 GB RAM and operating system Windows XP. The analytically obtained results of the analysis of the effectiveness of these algorithms are confirmed by a series of experiments.