Article

Article title ADAPTIVE ALGORITHM OF THE STEINER’S TREE CREATION
Authors V.A. Litvinenko, S.A. Hovanskov, D.Yu. Maksyuta
Section SECTION III. ARTIFICIAL INTELLECT AND INDISTINCT SYSTEMS
Month, Year 07, 2014 @en
Index UDC 621.3.06
DOI
Abstract In work the adaptive algorithm of creation of a tree of Steiner on the basis of creation of the shortest connecting tree Prima and its orthogonalizations with use of a Hannan"s lattice is offered. It is offered to use genetic algorithm for a choice of orthogonal realization of edges of a tree Prima. In the developed adaptive algorithm of creation of a tree of Steiner parametrical adaptation which consists in a choice of parameter of adaptation on the basis of the analysis of external conditions of the solution of a task and information being stored in a database is used. As external conditions of the solution of a problem of creation of a tree of Steiner it is offered to use: dimension of a task; the resource of time which has been taken away on the solution of a task, and also productivity of the computer on which the problem is solved. As the parameter of adaptation it is offered to use number of iterations in genetic algorithm at application of operations of a krossingover over options of realization of an edge of a tree Prima. The developed adaptive algorithm of creation of a tree of Steiner is realized in language of the high Java 7.0 level. Pilot researches of the developed algorithm are conducted.

Download PDF

Keywords Adaptive algorithms; Steiner's tree; Hannan's lattice; adaptation parameter; decision accuracy; dimension of a task; time resource; computer productivity; database; management of accuracy.
References 1. Gilbert E.N., Pollak H.О. Steiner Minimal Trees, SIAM Journal on Applied Mathematics, 1968, Vol. 16, No. 1, pp. 1-29. Available at: http://epubs.siam.org.
2. Kristofides N. Teoriya grafov. Algoritmicheskiy podkhod [Graph theory. Algorithmic approach]. Moscow: Mir, 1978, 432 p.
3. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy. Moscow: Fizmatlit, 2013, 260 p.
4. Kureychik V.M., Lebedev B.K., Lebedev O.B. Gibridnyy algoritm razbieniya na osnove prirodnykh mekhanizmov prinyatiya resheniy [Hybrid partitioning algorithm based on natural mechanisms of decision making], Iskusstvennyy intellekt i prinyatie resheniy [Artificial intelligence and decision making], 2012, pp. 3-15.
5. Kureychik V.M., Lebedev B.K., Lebedev V.B. Planirovanie sverkhbolshikh integralnykh skhem na osnove integratsii modeley adaptivnogo poiska [Planning of very large scale integrated circuits on the basis of integration models adaptive search], Izvestiya RAN. Teoriya i sistemy upravleniya [ Izvestiya of the Russian Academy of Sciences. Theory and control system, 2013, No. 1, pp. 84-101.
6. Lebedev B.K. Protsedury suzheniya prostranstva resheniy pri postroenii dereva Shteynera [Procedures narrowing space decisions when building the tree Steiner], Izvestiya TRTU [Izvestiya TSURE], 2004, No. 3 (38), pp. 55-60.
7. Lebedev B.K. Intellektualnaya protsedura postroeniya dereva Shteynera na osnove protsedur otsechki i suzheniya [Intellectual build procedure Steiner tree on the basis of the procedures cutoff and narrowing], Izvestiya TRTU [Izvestiya TSURE], 2000, No. 1 (15), pp. 89.
8. Chernyshev Yu.O., Ventsov N.N. K voprosu o postroenii derev'ev Shteynera s razlichnoy shirinoy vetvey dlya svyazyvaniya elementov trekhmernykh SBIS [To the question about building Steiner trees with different width of the branches to map three-dimensional elements of VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, No. 4 (93), pp. 72-76.
9. Chernyshev Yu.O., Litvinenko V.A., Khovanskov S.A., Litvinenko E.V. Metody upravleniya tochnostyu resheniya ekstremalnykh zadach na grafakh [Management methods accuracy of the solution of extremal problems on graphs], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7 (108), pp. 84-91.
10. Litvinenko V.A. Primenenie adaptivnykh algoritmov opredeleniya ekstremalnykh mnozhestv grafov pri reshenii optimizatsionnykh zadach avtomatizirovannogo proektirovaniya EVA [The use of adaptive algorithms of extremal sets in graphs when solving optimization problems aided design EVA], Izvestiya TRTU [Izvestiya TSURE], 2001, No. 4 (22), pp. 361-362.
11. Litvinenko V.A. Adaptivnye algoritmy opredeleniya ekstremal'nykh mnozhestv grafov [Adaptive algorithms of definition of extreme sets of graphs], Izvestiya TRTU [Izvestiya TSURE], 2000, No. 2 (16), pp. 186-189.
12. Litvinenko V.A. Adaptive algorithms of definition of extreme sets of graphs, Proceeding of the International Scientific Conferences «Intelligent System (IEEE AIS’03)» and «Intelligent CAD’s (CAD-2003)». Scientific publication in 3 volumes, 2003, Vol. 3, pp. 52-59.
13. Litvinenko V.A., Khovanskov S.A., Litvinenko E.V. Primenenie metodov iskusstvennogo intellekta dlya upravleniya tochnostyu resheniya zadach na grafakh [Application of artificial intelligence methods to control the accuracy of the solution of the problems on graphs], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 153-159.
14. Rastrigin L.A. Adaptatsiya slozhnykh system [Adaptation of complex systems]. Riga: Zinatne, 1981, 375 p.
15. Kureychik V.M., Lebedev B.K., Lebedev O.B., Chernyshev Yu.O. Adaptatsiya na osnove samoobucheniya [Adaptation based learning: Monograph]. Rostov-on-Don: Izd-vo RGASKhM GOU, 2005.
16. Kureychik V.M., Lebedev B.K., Lebedev O.B. Poiskovaya adaptatsiya. Teoriya i praktika [[Search adaptation. Theory and practice]: Monografiya. Moscow: Fizmatlit, 2006.
17. Orlov N.N. Novyy podkhod k resheniyu zadachi Shteynera na osnove resheniya Evklidovoy zadachi [A new approach to the solution of the Steiner problem on the basis of the solution of Euclidean tasks], Trudy mezhdunarodnykh nauchnykh konferentsiy IEEE AIS 04, CAD 04 [Proceedings of international scientific conferences IEEE AIS 04, CAD 04]. Moscow: Fizmatlit, 2004.
18. Hanan M. On Steiner's problem with rectilinear distance, J. SIAM Appl, Math. 14, 1966, pp. 255-265.
19. Martin Zachariasen. A Catalog of Hanan Grid Problems Networks, 2000, Vol. 38, pp. 200-221.

Comments are closed.