Abstract (ukr):
Проведено експериментальне дослідження точного методу розв’язання загальної задачі
комівояжера (ЗЗК) із декомпозицією вхідного графа на блоки. Показано зменшення часу роботи
методу залежно від кількості блоків. ЗЗК великої розмірності можуть бути розбиті на підзадачі
меншої розмірності, що відповідають блокам у графах. Цій підхід дозволяє знизити вимоги до
обчислювальних засобів, виконувати підзадачи паралельно, що призведе до виграшу в часі
виконання. Вартості обходів комівояжера для мостів та лісу дерев є константами. Знайдені у
блоках маршрути об’єднуються в єдиний маршрут за поліноміальний час. Декомпозиція ЗЗК
суттєво стримує зріст часу розв’язання, залежно від розмірності вхідного графа, та кількості
блоків у ньому, але складність ЗЗК залишається експоненціальною. Якщо граф не містить блоків,
час роботи методу не відрізняється від класичного варіанта алгоритму Літла, за виключенням
поліноміального часу, що витрачено на пошук можливостей декомпозиції. Досліджено частоту
з’явлення блоків, суттєвих для декомпозиції ЗЗК, тобто: ліса, мостів, точок зчленування. Той
факт, що існують випадки, коли сам граф є блоком, не враховувався.
Abstract (eng):
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.
