Исследование методов решения линейных уравнений
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
СОДЕРЖАНИЕ
Метод ветвей и границ
Метод первого порядка
Метод второго порядка
Оптимальный поиск
Пассивный поиск
метод дихотомии
Метод золотого сечения
Динамическое программирование
Линейное программирование. Метод Жордана-Гаусса.
Список литературы
Метод ветвей и границ
В качестве примера метода ветвей и границ рассмотрим задачу коммивояжера.
Постановка задачи.
Имеется N пунктов, расстояние между которыми известны. Необходимо, начав движения из п.1. последовательно обойти все остальные по самому короткому пути и вернуться в п.1. Условие a заключается в следующем: в каждый пункт надо войти только один раз и один раз из него выйти. На рис.1. приведен пример задачи для N = 5. На ребрах, соединяющих вершины графа (пункты), указаны расстояния.
Рис. 1.
Условие a делает невозможным выбор на некотором шаге вычислений оптимального из путей, приводящих в некоторую точку. Решение задачи методом прямого перебора всех возможных (N-1)! возможно лишь для малых N, Необходим метод, который позволяет уменьшать число рассматриваемых вариантов. Таким методом является метод ветвей и границ (МВТ).
Основное содержание метода заключается в том, что строятся нижние оценки функции цели (ФЦ), позволяющие отбраковать множество вариантов, для которых значение ФЦ заведомо хуже. По мере рассмотрения новых вариантов граница перемещается вниз (в задаче минимизации) до тех пор, пока число различных вариантов не уменьшается настолько, что выбор лучшего из них будет сделан непосредственным сравнением.
Решение задачи.
Запишем исходные данные в виде таблицы C0 = (Cij). В ней i и j - номера пунктов, движение на каждом шаге совершается из i в j, длина этого шага пути Cij, крестиками отмечены запрещенные переходы. Пусть Сi = min Cij. Найдем Сi для каждого i (в таблице эти значения подчеркнуты), после чего совершим приведение матрицы С0 к C01 по строкам, где Cij1 вычисляются по формулам Cij1 = Cij - Ci. Обозначим d01 = Ci. и Cj1 = min Cij. Найдем Cj для всех j и выполним приведение C01 по столбцам. В приведенном примере все Сj = 0, поэтому C02 = C01, константа приведения по столбцам d02 = 0, d0 = d01 + d02 = 23.
Можно утверждать, что задачам с матрицами C0 и C01 соответствует один и тот же оптимальный маршрут. Длина любого пути LS(C0) и LS(C02) связаны формулой LS(C0) = LS(C02) + d0. что следует из условия a. Тогда любой путь по матрице представляет движение по клеткам таблицы, причем в каждой строке и каждом столбце можно побывать только один раз.
Величину d0 можно использовать в качестве нижней границы при оценке всех возможных путей.
Рассмотрим путь, который включает переход из i в j. Для него LS gij = d0 + Cij. Такой переход всегда есть, так как в приведенной матрице хотя бы один элемент в строке - нулевой. Выбирая один из них, мы выбираем оптимизацию одного шага пути (самый короткий первый шаг). При этом, конечно, мы не знаем, как это отразится на длине последующего пути. Обозначим (ij) множество путей, не содержащих непосредственный переход из i в j. Поскольку из i надо куда-то выйти, а в j откуда-то прийти, то этому множеству соответствует оценка:
LS g(ij) = d0 + qij, где qij =
Тогда нижней оценкой для множества путей будет g2 = d0 + qij. Мы заинтересованы в выборе такого перехода ij, для которого эта оценка является самой высокой. Этот выбор можно сделать, отыскав среди нулевых элементов i строки такой, которому соответствует q2 = max qij. Выбором пары (ij) все множество возможных путей разбивается на два подмножества. Одно из них содержит переход (ij) (ему соответствует оценка g1 = d0 + q1), другое (ij) (ему соответствует оценка g2 = d0 + q2).
В нашем примере первым шагом пути должен быть переход из п.1. Сij= 0 для i,j = 1,2. Множество всех возможных путей W разбиваем на два: содержащих переход (12) и не содержащих переход (12). Строим для них нижние оценки. g1 = d0 = 23. Для перехода, не содержащего (12), соответствует путь, содержащий переходы (14) и (32). На этом первая итерация вычислительного процесса заканчивается. При дальнейшем движении за поиском оптимального пути будем наблюдать с помощью дерева вариантов (рис.2).
Рис. 2.
Рассмотрим теперь первое подмножество. В нем уже реализован переход (12), поэтому в таблице С02 строку 1 и столбец 2 удаляем (вычеркиваем) из дальнейшего рассмотрения. С02 преобразуется в С1, а после приведения - в С12. В верхнем левом углу таблицы С1 ставим крестик, так как переход (21) в рассматриваемом подмножестве (12) становиться невозможным.
Теперь над новой таблицей проделываем те же действия, что и над С2. Для С12 константа приведения a1 = 2. Далее в качестве возможных рассмотрим подмножества, содержащие пути (23) и (), и произведем их оценку:
(23) g23 = g1 = (d0 + d1) + с23 = 23 + 2 + 0 = 25.
() = g2 = (d0 + d1) + W23 = 25 + 5 = 30,
где W23 = = C24 + C 43 = 3+2 = 5.
После вычеркивания из таблицы C12 строки i = 2 и столбца j = 3 получается матрица С2 размером 3х3. Очередное разбиение возможных вариантов перемещения на подмножестве (34) и () дает оценки g34 = 26 и =27.
После очередного сокращения матрицы таблица принимает размер 2х2 и однозначно определяет путь: начальная точка 4, конечная - 1, путь (451). Он имеет длину 6. По дереву вариантов мы прошли путь до вершины. Длинный путь (123451) имеет длину 32. Аналогично множество () содержит единственный путь (3541) длиной 2. Путь (123541) имеет длину 27, его длина меньше, чем у пути, содержащего переход (34). В качестве нижней границы теперь следует выбирать 27. Любое множество, имеющее оценку больше 27, следует отбросить. Если же оценка меньше 27, то такой пу?/p>