???????????????? ??????????? ??????????? ?????? ??????????? ????????? ?????? ???????????
Електронний архів Житомирського державного технологічного університету
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
???????????????? ??????????? ??????????? ?????? ??????????? ????????? ?????? ???????????
Experimental research of an approximate method of common problem solution of travelling salesman |
|
| Creator |
????????, ????? ????????
Levchenko, A.Yu. |
|
| Subject |
???????? ?????? ???????????
?????????? ????? ?ommon travelling salesman problem approximate method |
|
| Description |
????????? ???????????????? ??????????? ???????????? ??????????? ?????? ??????????? ????????? ?????? ??????????? (???) ?? ??????? ????? ???????? ??????? ?? ???? ?????????? ?? ???????? ???????????? ? ??????????? ???????????. ?????????? ????? ??????????? ? ??? ??????. ?? ?????? ?????? ??? ????????????? ????????? ?? ??????????? ?????? ??????????? (???). ?? ?????? ?????? ??????????? ?????????????? ?????????? ???????? ???, ????????? ?????? ????? ?????????????? ? ?????????? ????????? ???. ???????????????? ?????? ???????? ?????????? ?????????? ?????? ??????? ? ??????? ? ???????????????? ???????? ?????? ???????????: ????? ?????? ??????? ??? ??????? ????? ???????? ???????. ?? ???????? ????????? ????????????????? ????? ?????????? ? ?????????? TSPLIB. ?? ???? ??????? ???????????? ??????? ????? ?????????? ???????? ??? ???????? ??????????? ?????? ??? ?????, ??? ???????? ?????????? ??????. ??????? ??????????? ?????????? ??????????? ?????? ??? ? ???????????? ???????, ?? ????????? ???????????? ?????? ??????? ??????????? ? ?????? ????????? ?????????????? ????????. Experimental research of approximate Common Travelling Salesman Problem (CTSP) solution method with input data of big size is conducted. Also the comparison of the method with well-known approximate and heuristic algorithms is performed. Approximate method is executing in two stages. On the first stage CTSP is transformed to Symmetric TSP (STSP) in polynomial time. On the second stage polynomial approximate algorithm of STSP is executed, and its results are transformed to approximate solution of CTSP. Experimental estimations of approximate solution cost are difficult enough because of exponential nature of TSP: it is hard to find optimum for input data of large size. Selected samples from the TSPLIB library were used as etalon solutions. Optimization of the implementation of the CTSP approximate method is possible, which allows solving of tasks of larger size in limited computational resources conditions. Keywords: ?ommon travelling salesman problem; approximate method. |
|
| Date |
2016-06-24T12:45:27Z
2016-06-24T12:45:27Z 2015 |
|
| Type |
Article
|
|
| Identifier |
http://eztuir.ztu.edu.ua/123456789/4302
|
|
| Language |
uk
|
|
| Relation |
?????? ????. ????? : ???????? ?????;4(75)
|
|
| Publisher |
????
|
|