Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 132 стр.

UptoLike

Составители:

Рубрика:

134

инвариантность цикла к исходному пункту коммивояжера (подраздел 3.4),

полученное решение может быть приведено к виду (1).

В наихудшем случае (рассчитывается

C вариантов с различными

начальными циклами) оценка требуемого объема элементарных операций

увеличится от полинома третьей степени до пятой (

C < 0,5n

). Однако

универсальность модифицированного МРЦ (возможность решения при

φ ≠ 1) в значительной мере компенсирует этот недостаток, не

представляющий, впрочем, серьезных трудностей для современных ЭВМ.

Таблица 1.

=cc , 1

j = 1 2 3 4 5 6 7 8 9 10

i = 1 0 921 56 977 34 11 45 56 101 157

2 259 0 416 675 91 766 857 622 479 101

3 580 680 0 260 940 200 141 341 482 822

4 303 125 428 0 554 982 536 518 54 572

5 625 197 822 19 0 842 861 702 563 265

6 829 94 923 17 940 0 957 896 853 749

7 601 350 952 302 253 555 0 808 363 172

8 535 707 242 948 190 139 329 0 468 797

9 264 61 325 386 711 96 807 903 0 710

10 614 324 938 263 201 464 665 129 794 0