beroal (beroal) wrote in ru_declarative,
beroal
beroal
ru_declarative

Category:

абстрактные методы решения задач

Сразу оговорюсь, что это не вопрос, а тема для обсуждения. Метод «разделяй и властвуй» все мы знаем. Есть ещё что-то на таком же абстрактном уровне? Примеры от меня.

Нужно найти неподвижную точку функции f. Пусть x — такая последовательность, что x(succ(n)) = f(x(n)). Находим такое наименьшее n, что x(succ(n)) = x(n). Говоря неформально, вычисляем последовательность, пока она не стабилизируется.

Частный случай предыдущей задачи, где f определена на векторах. (Вектор — это функция, определённая на некотором множестве V.) Здесь тоже вычисляем последовательность «недорешений» x. Параллельно вычисляем такую последовательность с, что ∀n ∀v v∈c(n) ↔ x(n)(v) = f(x(n))(v). с показывает, в каких точках x(n) «решён». Комплемент к этому множеству называется «agenda». x(succ(n)) вычисляем следующим образом. Выбираем «нерешённый» (принадлежащий agenda) u. Для всех v, если v=u, то x(succ(n))(v) = f(x(n))(v), иначе x(succ(n))(v) = x(n)(v). Другими словами, на одном шаге «решаем» один элемент вектора. c(succ(n)) вычисляется хитро, потому что изменение элемента вектора может сделать другие элементы «нерешёнными». Полное и формальное описание алгоритма могу привести, если кому-то надо.

Прикладные варианты этой задачи — алгоритмы на графах (V — множество вершин графа) (reachability, наиболее короткий путь), дедукция «снизу» (chart parser).
Tags: algorithm
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments