|
быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута). Все эффективные, т.е. сокращающими полный перебор, методы решения задачи коммивояжёра являются эвристическими. При этом большинство эвристических методов находит не самый эффективный маршрут, а приближённое решение. На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а также алгоритм муравьиной колонии. Рассмотрим более подробно сущность метода ветвей и границ ("поиска с возвратом", "backtracking"). Данный метод является одной из первых эффективных схем неявного (улучшенного) перебора, идея которого состоит в том, что при решении экстремальной задачи можно избежать полного перебора путем отбрасывания заведомо неоптимальных решений. Общая идея метода состоит в следующем: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу в задаче минимизации, сверху — в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной [39, с. 114]. На каждом шаге метода элементы разбиения множества допустимых решений на подмножества подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу (сверху) для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы. 82 |
удовлетворять неравенству треугольника, т.е. для всех [,'}, к: С,+С^.>С,. (42) В математической постановке говорится о произвольной матрице, так как достаточно часто нарушается условие (41). В связи с этим различают два варианта задачи: симметричную задачу, когда условие (41) выполнятся, и несимметричную в противном.случае. Второе замечание касается числа всех возможных туров. В несимметричной задаче коммивояжера все туры 1=(}\,}2,-,}п,и) и t ' = ( j . , j 2 , j О имеют разную длину и должны учитываться оба. Число разных туров определяется как (п-1)!. Симметричных туров будет в два раза меньше, т.к. каждый засчитан два раза: как 1 и как 1'. Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (1,}) проведено, если Су^О и не проведено, если Су=1. Тогда, если существует тур длины О, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом.Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём) [65, с. 31Г. В терминах теории графов симметричную задачу коммивояжера можно сформулировать следующим образом: дана полная сеть с п вершинами, длина ребра (1, ]) = Су. Найти гамильтонов цикл минимальной длины. В несимметричной задаче вместо термина «цикл» необходимо употреблять «контур», а вместо «ребра» «дуги». Среди простейших методов решения задачи коммивояжера лежат методы сплошного типа перебора, случайного ближайшего перебора, соседа а также жадные алгоритмы алгоритма (каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута). Все эффективные, т.е. сокращающими полный перебор, методы решения задачи 97 коммивояжёра эвристических являются методов эвристическими. находит не самый При этом большинство маршрут, а эффективный приближённое решение. На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а также алгоритм муравьиной колонии. Рассмотрим более подробно сущность метода ветвей и границ ("поиска с возвратом", "backtracking"). Данный метод является одной из первых эффективных схем неявного (улучшенного) перебора, идея которого состоит в том, что при решении экстремальной задачи можно избежать полного перебора путем отбрасывания заведомо неоптимальных решений. Общая идея метода состоит в следующем: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу в задаче минимизации, сверху в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной [130, с. 114]. На каждом шаге метода элементы разбиения множества допустимых решений на подмножества подвергаются проверке для выяснения, содержит данное подмножество • оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу (сверху) для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы. Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из неотброшенных 98 |