???????????? ????????? ?????? ??????????? ?? ?????????? ????? ?? ?????????
Електронний архів Житомирського державного технологічного університету
View Archive Info| Field | Value | |
| Title |
???????????? ????????? ?????? ??????????? ?? ?????????? ????? ?? ?????????
Decomposition of the total traveling salesman problem and its solutions approximate method |
|
| Creator |
????????, ?.?.
Levchenko, ?.Yu. |
|
| Subject |
?????? ???????????
???????????? ??????????? ???????? |
|
| Description |
????????????? ?????? ?? ???????????? ????????? ?????? ??????????? (???) ?? ?????? ?????? ???????????, ?? ???????? ??????? ?????????? ????????? ?????? ?????????. ???? ????, ???????????? ???????????? ?????????? ????? ????????? ???, ???? ??????? ? ???????????? ????????? ???? ??????? ?????????? ????????????? ???????????. ???????? ??? ????????? ?? ????????? ??????????? ?????? ??????????? (???) ?????????????? ????????????? ????????? ????????? ????? ? ?????? ????????? ????. ????? ??????????? ????????? ??????? ????????? ???, ?? ???????? ????????? ??????? ???????. The article offers the approach to the decomposition of the common traveling salesman problem (CTSP) to the smaller size problems, which can significantly speed up the solution search. In addition, a fast approximate method for solving the CTSP is offered, which is a sequential execution of two well known algorithms of combinatorial optimization. CTSP is reduced to metric symmetric traveling salesman problem by polynomial transformation of the original weighted graph to the full metric graph first. Then we find an approximate solution of the metric travelling salesman problem that allows to get the desired route. |
|
| Date |
2016-05-27T10:45:59Z
2016-05-27T10:45:59Z 2011 |
|
| Type |
Article
|
|
| Identifier |
http://eztuir.ztu.edu.ua/123456789/3656
|
|
| Language |
uk
|
|
| Relation |
?????? ????. ?????: ???????? ?????;3(58)
|
|
| Publisher |
????
|
|