47940 (608412), страница 2
Текст из файла (страница 2)
. (7)
Рассмотрим теперь множество I
, и матрицу С
. Так как все пути, принадлежащие этому множеству, содержат переход ij, то для его исследования нам достаточно рассмотреть задачу коммивояжера, в которой города номеров i и j совпадают. Размерность этой задачи будет уже равна N - 1, а ее матрица получится из матрицы С вычеркиванием столбца номера j и строки номера i.
Поскольку переход ij невозможен, то элемент 
принимаем равным бесконечности.
Рассмотрим случай N=3 (рис. 4, а) и предположим, что мы рассматриваем тот вариант, который содержит переход 32. Тогда задача коммивояжера после вычеркивания третьей строки и второго столбца вырождается в тривиальную. Ее матрица изображена на рис. 4, б). В этом случае мы имеем единственный путь, и его длина будет, очевидно, равна сумме
| 1 | 2 | 3 | |
| 1 | С1 | С1 | |
| 2 | С2 | С2 | |
| 3 | С3 | С3 |
Рис. 4а.
| 1 | 3 | |
| 1 | C1 | |
| 2 | C2 |
Рис. 4б.
Итак, если в результате вычеркивания строки номера i и столбца номера j мы получим матрицу второго порядка, то задачу можно считать решенной.
Пусть теперь N > 3. После вычеркивания мы получим матрицу порядка N-1 >2. С этой матрицей (N-1)-го порядка совершим процедуру приведения. Матрицу, которую таким образом получим, обозначим через 
, а через 
- сумму ее констант приведения. Тогда для 
, мы будем иметь оценку
. (8)
На этом первый шаг алгоритма закончен. В результате одного шага мы разбили множество всех возможных вариантов на два множества , и для путей, принадлежащих этим множеством, мы получили оценки (8) и (7) (рис. 5).
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3 EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
