???????????????? ??????????? ??????? ?????? ????????? ?????? ??????????? ?? ?????????????
Електронний архів Житомирського державного технологічного університету
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 |
????
|
|