Оценка точности алгоритма. Определение оценок в лучшем и в худшем для алгоритма решения задачи коммивояжора по методу поиска в глубину

Цель оценки точности алгоритма – определение границ погрешности решения, обеспечиваемого им. Очевидно, что для различных входных данных приближенный алгоритм может давать решение ближе к оптимальному и дальше от него, т.е. имеет смысл говорить о поведении алгоритма «в лучшем» и «в худшем».

При определении границы погрешности «в худшем» надо иметь гарантию того, что ни при каком допустимом наборе входных данных решение не будет хуже, чем установлено границей, а для границы «в лучшем» – того, что не существует набора данных, при котором решение ближе к оптимальному. Анализируя вид и последовательность операций, выполняемых над графами в процессе решения задачи, можно сконструировать входные данные (или сформулировать требования к ним), на которых этот алгоритм приводит к наибольшей и наименьшей погрешности по функционалу. Гарантированность полученных оценок погрешности алгоритма обеспечивается доказательством того факта, что сконструированные наборы входных данных действительно приводят к наихудшему и наилучшему результату работы алгоритма соответственно.

Задача коммивояжера (поиск гамильтонова цикла минимального веса)

Идея алгоритма при решении методом поиска в глубину заключается в следующем:

• определяем ребра, инцидентные исходной вершине;

• затем выбираем и включаем в формируемый цикл ребро минимального веса (длины).

Далее действия повторяются для каждой, только что достигнутой вершины, причем в цепь включаются ребра, не образующие с ней цикла, до тех пор, пока количество вершин цепи < n -1, где n = | X |.

Ребро, соединяющее (n -1)-ю вершину с начальной и образующее гамильтонов цикл, определяется однозначно.

Отсюда вытекает следующее утверждение: приближенный алгоритм решения задачи коммивояжера по методу поиска в глубину обеспечивает получение точного решения, если каждый раз выбирается ребро u (xk, xr) такое, что

l (u (xk, xr)) = min { l (u (xk,xj)) /" u Î Г1 xk \ u (xi,xk)},

где xi – предыдущая вершина цепи, являющейся фрагментом гамильтонова цикла, Г1 – отношение (предикат) инцидентности между множествами вершин X и ребер U, таким образом, Г1 xk = Uk – ребра, инцидентные вершине xk.

Это слишком жесткое условие – граница «в лучшем» – есть наборы данных, которые ему не удовлетворяют, но решение при этом будет оптимальным.