Шаг 5.
Методы разработки алгоритмов.
Решение обратной задачи и метод полного перебора

    На этом шаге мы рассмотрим решение обратной задачи и метод полного перебора.

Решение обратной задачи

    Иногда обратная задача, т. е. задача, соответствующая функции 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 (столько раз, сколько элементов имеется в области решений). Причем, в общем случае, просмотреть нужно всю область и порядок, в котором просматриваются элементы, не важен.

    На следующем шаге мы рассмотрим эвристические методы.




Предыдущий шаг Содержание Следующий шаг