Record Details

???????????????? ??????????? ??????? ?????? ????????? ?????? ??????????? ?? ?????????????

Електронний архів Житомирського державного технологічного університету

View Archive Info
 
 
Field Value
 
Title ???????????????? ??????????? ??????? ?????? ????????? ?????? ??????????? ?? ?????????????
Experimental research of properties of an exact method of common travelling salesman problem solution with decomposition
 
Creator ????????, ?.?.
Levchenko, A.Yu.
 
Subject ???????? ?????? ???????????
?????? ?????
???????????? ?????
common travelling salesman problem
exact method
graph?s decomposition
 
Description ????????? ???????????????? ??????????? ??????? ?????? ??????????? ????????? ??????
??????????? (???) ?? ????????????? ???????? ????? ?? ?????. ???????? ????????? ???? ??????
?????? ??????? ??? ????????? ??????. ??? ??????? ??????????? ?????? ???? ??????? ?? ?????????
?????? ???????????, ?? ???????????? ?????? ? ??????. ??? ?????? ???????? ??????? ?????? ??
?????????????? ???????, ?????????? ????????? ??????????, ?? ???????? ?? ??????? ? ????
?????????. ???????? ??????? ??????????? ??? ?????? ?? ???? ????? ? ???????????. ???????? ?
?????? ???????? ???????????? ? ?????? ??????? ?? ?????????????? ???. ???????????? ???
??????? ??????? ????? ???? ???????????, ??????? ??? ??????????? ???????? ?????, ?? ?????????
?????? ? ?????, ??? ?????????? ??? ??????????? ????????????????. ???? ???? ?? ??????? ??????,
??? ?????? ?????? ?? ????????????? ??? ?????????? ???????? ????????? ?????, ?? ???????????
??????????????? ????, ?? ????????? ?? ????? ??????????? ????????????. ?????????? ???????
????????? ??????, ???????? ??? ???????????? ???, ?????: ????, ??????, ????? ???????????. ???
????, ?? ??????? ???????, ???? ??? ???? ? ??????, ?? ????????????.
Experimental research of an exact solution method of Common Travelling Salesman Problem (CTSP) with decomposition of input graph was performed. Reduction of method?s execution time depending on blocks number were shown. A large size of CTSP may be decomposed to smaller subtasks, which are corresponding to blocks in a graph. This approach allows to reduce requirements to computational resources, execute subtasks in parallel, leading to execution time decreasing. Travelling salesman?s tours costs in bridges and forest of trees are constant. Tours in blocks are united to CTSP tour in polynomial time. CTSP decomposition significantly holds execution time growth and depends on input graph size, and number of blocks in the graph, but complicity of CTSP remain still exponent. If graph doesn?t contains blocks the method?s execution time doesn?t differ from the classical variant of Little?s algorithm, excluding polynomial time of decomposition?s possibility searching. Frequency of appearance of significant for decomposition blocks: forest, bridges, adjacency points, were researched. The case when the graph is a block itself weren?t taken into consideration.
 
Date 2016-04-05T11:29:15Z
2016-04-05T11:29:15Z
2015
 
Type Article
 
Identifier http://eztuir.ztu.edu.ua/123456789/2546
 
Language uk
 
Relation ?????? ????: ?????: ???????? ?????;3(74)
 
Publisher ????