Study of algorithms for tracing connections between pins

Don State Technical University, 1, Gagarina Square, Rostov-on-Don, 344010, Russia

^* Corresponding author: ddf_1@mail.ru

Abstract

Tracing is mathematically the most complicated problem of choosing the optimal solution from a huge number of variants. The development of methods and algorithms for solving the tracing problem has been carried out for many years, but it is still urgent. It is connected, first of all, with the fact that this problem is NP-complete, and it is difficult to develop a universal algorithm allowing one to find the exact optimal solution for an acceptable time. The emergence of new and more advanced means of computing technology, giving powerful computing resources, as well as increased requirements to the designed devices, all this is an incentive to develop new algorithms for solving the problem of tracing. There are several approaches to solving NP -complete problems. The first class of algorithms includes, explicitly or implicitly providing for the possibility of exponential running time of the algorithm, such methods as the method of complete enumeration, linear and nonlinear programming, etc. The second class includes the so-called heuristic algorithms that allow to obtain good solutions in an acceptable time. The third class includes random-directed search algorithms based on modeling principles (Lebedev, 2012). We propose a swarm algorithm for reallocating connections between leads based on the integration of models of adaptive behavior of an ant colony and collective alternative adaptation. The essence of integration consists of the fact that during the execution of the search procedure, the alternation of separate procedures of the ant algorithm and collective alternative adaptation is performed. Experimental studies were carried out that confirm the effectiveness of the proposed paradigm.