цикла 2*СostFr.
цикла 2*СostFr. Неравенство треугольника обеспечивает результат: следующую оценку шага 4 - CostAp<2*CostFr, а значит, CostAp<2*CostBet.
Рассмотрим пример.
Для исходных данных, приведенных в п. 2.1.7, на рисунке жирными линиями выделен каркас минимального веса. Тонкие линии добавляются на шаге 2. Получаем эйлеров граф. Затем эйлеров цикл (маршрут) преобразуется в путь коммивояжера (шаг 4). Согласно неравенству треугольника мы получаем: d2,9+d9,8>d2,8; d2,8+d8,1>d2,1; d2,1+d1,7>d2,7. Суммируя левые и правые части неравенств, получаем: d2,9+d9,8+d8,1+d1,7>d2,7. Для рассмотренного примера CostAp равна 202. Это ~ 1.28*CostBet.
Структуры данных. Помимо названных ранее массивов А - матрица расстояний и массива Way - хранение искомого пути, требуется «что-то» для хранение описания каркаса. Пусть это будет массив B (B:array[1..Nmax,1..Nmax] of boolean). Элемент B[i,j], равный true, говорит о том, что ребро (i,j) графа принадлежит каркасу.
Общая логика.
Begin
init;{ввод
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
