Год сдачи: 2009 Информация о файлах в архиве: .doc Краткое описание оценка отлично Введение
Поставленная перед нами задача относится к так называемым задачам оптимизации – задачам, в которых необходимо выбрать вариант, обладающий наилучшими свойствами из всех представленных.
Задача поиска контура оптимальной длины называется «Задачей коммивояжера» Общая ее формулировка такова. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Найдем решение этой задачи для нашего графа в виде гамильтонова контура. Вывод
Решение задач оптимизации с использованием методов теории графов существенно облегчают процесс вычисления. Используя алгоритм Литтла можно получить несколько различных контуров одинаковой длины. В этом варианте мы получили два различных контура, длиной 18, и один контур, длиной 17. Последний контур и является оптимальным. Последовательность действий алгоритма такова
Шаг 1. В каждой строке матрицы стоимости найти минимальный элемент и вычесть его из всех элементов этой строки. Затем сделать это и для столбцов, не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.
Шаг 2. Для каждого нулевого элемента матрицы рассчитаем коэффициент γi,j, равный сумме наименьшего элемента i-й (исключая элемент Ci,j равный 0) и наименьшего элемента j-го столбца. Из всех коэффициентов γi,j выбираем такой, который является максимальным. В гамильтонов контур вносится соответствующая дуга.
Шаг 3. Удаляем k-ю строку и столбец l, заменяем на бесконечность значение элемента Cl,k так как дуга (k,l) включена в контур, а обратный путь не допустим.
Шаг 4. Повторяем алгоритм с пункта 1 пока порядок матрицы не станет равным двум. После этого остается внести в граф две дуги (они добавляются однозначно, так как других вариантов получения контура не остается) и получается гамильтонов контур.
|