На этом шаге мы рассмотрим решение обратной задачи и метод полного перебора.
Решение обратной задачи
Иногда обратная задача, т. е. задача, соответствующая функции f-1(Y)=X, решается значительно более просто, чем исходная задача. Тогда имеющийся алгоритм решения обратной задачи R иногда можно использовать для построения алгоритма решения прямой задачи Р.
Метод полного перебора
Когда говорили о решении задачи вычисления f(X) путем декомпозиции функции f или разбиения исходных данных X на части, то имелось в виду, что существуют математические результаты или иные основания для таких преобразований. Иначе говоря, задача аддитивна - ее решение может быть получено объединением решений частных задач.
В ряде случаев это не так. Рассмотрим, например, задачу о рюкзаке.
Даны целое неотрицательное число N и k чисел {n1, n2, n3, ..., nk}; найти подмножество в {n1, n2, n3, ..., nk}, сумма чисел которого равна N, если такое подмножество существует.
Нет никаких оснований для того, чтобы разделить исходные данные на части и решать задачи для упрощенных исходных данных. Сама формулировка задачи также не подсказывает никакой возможности декомпозиции.
Выход оказывается одновременно и простым и сложным. Можно взять некоторое подмножество и непосредственной проверкой (суммированием чисел из этого подмножества и сравнением суммы с N) узнать, удовлетворяет ли это подмножество поставленному условию. Поскольку различных подмножеств имеется конечное количество 2k, то потенциально можно перебрать все подмножества и найти решение.
Сложность заключается в том, что с увеличением количества исходных данных (переходе от k к k+1) быстро увеличивается необходимое число проверок. При k = 10 их будет 1024, а при k = 40 уже более 1012.
Метод полного перебора применим в тех случаях, когда искомое решение Y =f(Х) принадлежит некоторой конечной области и может быть найдена простая функция quality(Y) для проверки правильности (или качества) выбранного решения. Тогда задача P вычисления функции f заменяется на многократное решение задачи R вычисления функции quality (столько раз, сколько элементов имеется в области решений). Причем, в общем случае, просмотреть нужно всю область и порядок, в котором просматриваются элементы, не важен.
На следующем шаге мы рассмотрим эвристические методы.
