Article

Article title AN ALGORITHM FOR DIVIDING A SET BY ITS NUMBER INTO A COLLECTION OF EQUIPOTENTIAL SUBSETS
Authors V. M. Glushan, A. V. Zubritckii
Section SECTION I. DESIGN AUTOMATION
Month, Year 04, 2018 @en
Index UDC 004.021
DOI
Abstract Представлены результаты разработки алгоритма формирования (r, n)-разбиений по их номерам в лексикографической последовательности всех возможных комбинаций. На сегодняшний день существуют различные задачи комбинаторной оптимизации, для которых комбинаторное соединение типа (r, n)-разбиения может являться оптимальным решением. Теоретически оптимальное решение можно найти полным перебором всех (r, n) -разбиений, но количество возможных вариантов экспоненциально растет с увеличением числа элементов. Следовательно, для задач большой размерности необходимо сократить время вычислений, то есть сократить число возможных решений или организовать параллельный вычислительный процесс. В статье приведено обоснование формулы, позволяющей вычислить точное количество всех возможных неповторяющихся (r, n)-разбиений. Опираясь на данную формулу, предложен алгоритм построения разбиений по заданному номеру. Он позволяет проанализировать область решений и использовать методы случайного поиска решений. Работа алгоритма рассмотрена на примере. Разработан лексикографический алгоритм построения (r, n)-разбиений, который является модифицированной комбинацией двух алгоритмов: предложенного ранее рекурсивно-лексикографического алгоритма и алгоритма построения разбиений по заданному номеру. Он предназначен для решения задач оптимизации на комбинаторных объектах с сужаемыми областями поиска для тех случаев, когда мы заранее можем предсказать области оптимальных решений. Таким образом, алгоритм позволяет использовать частичный перебор вместо полного, то есть проводить исследования перспективных областей на наличие оптимального или близкого к оптимальному решения. Данный алгоритм, позволяет решать задачи большей мощности разбиваемого множества, чем рекурсивно-лексикографический алгоритм. Используя приведенную формулу для подсчета числа разбиений, можно разбить область решений на необходимое число подобластей и для каждой из них параллельно использовать предложенный алгоритм, реализовав таким образом параллельный вычислительный процесс.

Download PDF

Keywords Sets; kombinatorisches Set; lexicographic sequence; optimization.
References 1. Sergienko I.V., Shilo V.P. Zadachi diskretnoy optimizatsii: problemy, metody resheniya, issledovaniya [Problems of discrete optimization: problems, methods of solution, research]. Kiev: Scientific thought, 2003, 264 p.
2. Semenova N.V., Kolechkina L.M. Vektornye zadachi diskretnoy optimizatsii na kombinatornykh mnozhestvakh: metody issledovaniya i resheniya [Vector problem of discrete optimization on combinatorial sets: research methods and solutions], Monografiya [Monograph]. Kiev: Scientific thought, 2009, 266 p.
3. Gladkov L.A., Gladkova N.V., Bricheeva U.V. Reshenie zadach kompanovki skhem EVA na osnove vydeleniya klik [Solving the problem of layout of eva based on the selection of cliques], Trudy kogressa po intellektual’nym sistemam i informatsionnym tekhnologiyam «IS&IT'13». Nauchnoe izdanie v 4 t. T. 3. [Proceedings of the Congress on Intelligent Systems and Information Technologies «IS&IT'13». Scientific publication in 4 vol. Vol. 3]. Moscow: Fizmatlit, 2013, pp. 151-153.
4. Gladkov L.A., Shkurko V.A. Reshenie zadach razbieniya grafa na podgrafy na osnove geneticheskogo algoritma [Solution of the problem of partitioning a graph into subgraphs based on a genetic algorithm], Trudy kogressa po intellektual’nym sistemam i informatsionnym tekhnologiyam «IS&IT'14». Nauchnoe izdanie v 4 t. T. 3 [Proceedings of the Congress on Intelligent Systems and Information Technologies «IS&IT'14». Scientific publication in 4 vol. Vol. 3]. Moscow: Fizmatlit, 2014, pp. 142-146.
5. Kureychik V.M., Kazharov A.A. Roevoy intellect v reshenii grafovykh zadach [Root intelligence in solving graph tasks], Trudy mezhdunarodnoy konferentsii po myagkim vichisleniyam i izmereniyam (SCM’2013) [Proceedings of the International Conference on Soft Computing and Measurement (SCM’2013)]. Saint Petersburg, 2013, pp. 31-34.
6. Glushan V.M., Lavrik P.V. Raspredelennie SAPR. Arkhitektura i vozmozhnosti [Distributed CAD. Architecture and capabilities], Monografiya [Monograph]. Stariy Oskol: TNT, 2014, 188 p.
7. Test i obzor: Intel Core i7-4770K i Core i5-4670K – novoe pokolenie Haswell [Test and review: Intel Core i7-4770K and Core i5-4670K – new generation]. M., 2013. Available at: http://www.hardwareluxx.ru/index.php/artikel/hardware/prozessoren/26018-haswell-test-intel-core-i7-4770k-core-i5.html.
8. Gorbatov V.A Osnovy diskretnoy matematiki: ucheb. posobie dlya studentov vuzov [Basics of Discrete Mathematics: Textbook for university students]. Moscow: High School, 1986, 311 p.
9. Rastrigin L.A. Teoriya i primenenie sluchaynogo poiska [Theory and application of random search], Riga: Zinatne, 1969, 309 p.
10. Shcherbina O.A. Metaevristicheskie algoritmy dlya zadach kombinatornoy optimizatsii (obzor) [Metaheuristic algorithms for combinatorial optimization problems (review)], Tavricheskiy vestnik informatiki i matematiki [Tavrichesky messenger of computer science and mathematics], 2014, No. 1 (24), pp. 56-71.
11. Voevodin V.V., Voevodin Vl.V. Parallelnye vychisleniya [Parallel computing]. Saint Petersburg: BHV-Peterburg, 2004, 608 p.
12. Voevodin Vl.V. Raspredelennaya obrabotka dannykh [Distributed data processing], Vtoraya Sibirskaya shkola seminar po parallel’nym vychisleniyam [The Second Siberian School-Seminar on Parallel Computing], ed. by prof. A.V. Starchenko. Tomsk: Tomsk university, 2004, 108 p.
13. Zakon Amdala [Amdahl’s law]. Available at: https://dic.academic.ru/dic.nsf/ruwiki/433588.
14. Zakon Amdala i budushchee mnogoyadernih processorov [Amdahl's Law and the Future of Multi-Core Processors]. Available at: https://www.osp.ru/os/2009/04/9288815.
15. Glushan V.M., Lavrik P.V. Ogranichenie bystodeystviya vychislitel’nykh system v rezultate sovmeshcheniya zakona Amdala i gipotezi Minskogo [The limitation of the speed of computing systems as a result of the combination of the Amdahl law and the Minskiy hypothesis], Trudy kogressa po intellektual’nym sistemam i informatsionnym tekhnologiyam «IS&IT'13». Nauchnoe izdanie v 4 t. T. 1. [Proceedings of the Congress on Intelligent Systems and Information Technologies «IS&IT'13». Scientific publication in 4 vol. Vol. 1]. Moscow: Fizmatlit, 2013, pp. 129-137.
16. Lipskiy V. Kombinatorika dlya programistov [Combinatorics for programmers]. Moscow: Mir, 1988, 213 p.
17. Kureychik V.M., Glushan V.M., Shcherbakov L.I. Kombinatornye apparatnye modeli i algoritmy v SAPR [Combinatorial hardware models and algorithms in CAD]. Мoscow: Radio i svyaz’, 1990, 216 p.
18. Gerasimov V.A. Generatsiya sluchaynykh sochetaniy. Generatsiya sochetaniy po ego poryadkovomu nomeru [Generating random combinations. Generation of combinations by its serial number] RSDN jurnal [RSDN Magasine], 2010, Vol. 3.
19. Dubinin I.S., Arapov S.U., Tyagunov A.G. Ratsionalnyy metod generatsii sochetaniy dlya parallel’nykh vychisleniy v nekotorykh kombinatornykh zadachah [Rational method of generating combinations for parallel computations in some combinatorial problems], Sbornik dokladov Mezhdunarodnoy konferentsii studentov, aspirantov i molodykh uchenykh “Informatsionnye tehnologii, telekommunikatsii i sistemy upravleniya” [Collection of reports of the International conference of students, graduate students and young scientists "Information technology, telecommunications and management systems"]. Ekaterinburg: UrFU, 2015, pp. 174-178.
20. Timoshevskaya N.E. O numeratsii perestanovok i sochetaniy dlya organizatsii parallel’nykh vichisleniy v zadachakh proektirovaniya vicheslitel’nykh system [On the numbering of permutations and combinations for the organization of parallel computations in problems of designing computer systems] Izvestiya Tomskogo politekhnicheskogo uniersiteta [Bulletin of the Tomsk polytechnic university], 2004, Vol. 307, No. 6, pp. 18-20.
21. Glushan V.M., Zubrittskii A.V. Teoreticheskoe obosnovanie algoritma formirovaniya uporyadochennykh razbieniy s ravnomoshchnymi bespovtornimi viborkami [Theoretical substantiation of the algorithm of formation of ordered divisions with equipped unbeatable selections], Trudi kogressa po intellekrual’nykh sistemam i informatsionnym tekhnologiyam «IS&IT'17». Nauchnoe izdanie v 3 t. Т. 2 [Proceedings of the Congress on Intelligent Systems and Information Technologies «IS&IT'17». Scientific publication in 3 vol. Vol. 2]. Taganrog: Izdatel'stvo Stupina S.A., 2017, pp. 104-112.

Comments are closed.