Šakų ir rėžių lygiagrečiųjų algoritmų analizė ir taikymai

Abstract

Baigiamajame magistro darbe analizuojami trys Šakų ir rėžių metodo lygiagretieji šablonai: Statinės dekompozicijos lygiagretusis šablonas; Statinės dekompozicijos lygiagretusis šablonas su geriausio sprendinio apsikeitimu; Valdytojas-vykdytojo (angl. Master-Slave) lygiagretusis šablonas. Šiame darbe jie pritaikomi Keliaujančio pirklio uždavinio sprendimui ir nustatomi lygiagrečiųjų algoritmų spartumas bei efektyvumas. Pateikiami C++ kalba parašyti algoritmai, skaičiavimų rezultatai bei patogi grafinė vartotojo sąsaja. Darbą sudaro 7 dalys: įvadas, globaliojo optimizavimo uždaviniai, lygiagrečiųjų kompiuterių ir algoritmų apžvalga, Šakų ir rėžių metodo bei šio metodo lygiagrečiųjų šablonų analizė, algoritmų testavimas sprendžiant Keliaujančio pirklio uždavinį, pateikiamas grafinės vartotojo sąsajos aprašymas bei literatūros sąrašas. Darbo apimtis – 31 p. teksto be priedų, 19 iliustr., 5 lent., 19 bibliografiniai šaltiniai. Atskirai pridedami darbo priedai.

The present Master’s Degree Thesis analyses the three parallel patterns of the Branch and Bound method: parallel pattern of static domain decomposition; parallel pattern of static domain decomposition with the exchange of the best solution; Master-Slave parallel pattern. In this paper, they are applied to solving of the travelling salesman problem (TSP) , besides the speed and efficiency of parallel algorithms are identified. Algorithms written in the C ++ language, the results of calculations and user-friendly graphical user interface (GUI) are provided here. The paper consists of 7 parts: introduction, global optimization tasks, overview of parallel computers and algorithms, branch-and-bound method, as well as the analysis of the parallel patterns of this method, testing of algorithms when solving TSP, the description of GUI and the references. Paper scope - 31 pages of text without enclosures, 19 illustrations, 5 tables, 19 bibliographic sources.