Как сократить перебор с возвратом. Перечисление последовательностей переменной длины

Англия

Это пример неориентированного графа или симметричного отношения.

· Франция

· Италия "i,j Graph(i,j)=Graph(j,i)

В программировании стандартным способом задания графа является двуместные массивы, обычно булевские. Иной взгляд на диаграммы даёт их понимание как транспортные схемы. Автоматом назовём соответствие вида

Automaton: X´FàX

Automaton(x,f)=x^|, если ребро f ведёт из вершины х в вершину x^|. Или, в терминологии теории автоматов, событие f переводит из состояния х в состояние x^|.

Путём называется произвольная последовательность элементов из множества F. Функции Graph и Automaton очевидным образом продолжаются на множество всех путей F^*. Другая интерпретация (трактовка) элементов множества F – преобразование состояний (процедура). Функция Automaton(x,f)= x^| - аналог оператора аппликации – применения функции к аргументу.

Пусть задан некоторый автомат, а также предикаты Вход и Выход.

Вход: XàBoolean

Выход: XàBoolean

Состояния, на которых эти предикаты верны, называются входными и выходными.

Задача. Для данного автомата и предикатов Вход и Выход определить множество путей их каждого входного состояния некоторое выходное.

Это универсальная спецификация любой

задачи.

Пример: Сортировка массивов.

Множество состояний – множество всех состояний программы.

Вход: произвольное состояние, где Х – выделенная переменная, произвольный массив. Остальные переменные не определены.

Выход: любое состояние, в котором Х – перестановка начального состояния в упорядоченный массив.

Назовём задачу предыдущего вида (универсальный) конечной, если конечно множество состояний автомата (множество вершин графа). Полный перебор пути есть универсальный алгоритм решения любой конечной задачи.

Следствие: программисты не нужны! J

Но следствие неверно, поскольку

1) существуют бесконечные задачи;

2) универсальный алгоритм даёт реально невыполнимые решения.

Деревья

Назовём автомат инициальным, если выделено некоторое начальное состояние 0 такое, что любое другое состояние достижимо из него: " xÎX $ sÎF^* : (Automaton(0,s)=x).

Деревом называется инициальный автомат T, в котором разные пути приводят в разные состояния: "s,s^| ÎF^* (T(0,s)¹T(0,s^|)).

Обычно деревья связывают не только собственно с деревьями, но с генеалогическим древом, что подсказывает терминологию. Начальное состояние – корень, конечное – листья.

корень

t1 t1,t2,t3,…

0 1 Пример бинарного дерева F={0,1}

родители(предки)àдети(потомки)

Упражнение. 1) Дать определение дерева на языке теории графов (т.е. в терминах соединения вершин). 2) Дать формальное определение родственной терминологии (родители, дети, дядья, кузены, деды, внуки).

Фундаментальный пример дерева даёт класс всех последовательностей некоторого базового типа T, или класс всех функций NàT.

Дерево позиционное, если на входном алфавите, т.е. на множестве F, зафиксирован некоторый линейный порядок (сравнение). Например, F={0<1} или F={1<0}. Это позволяет нам говорить о старшинстве в одном поколении. Если же это сравнение определяет порядковый тип, то таким же (порядковым) будет и произвольный класс путей в лексикографическом (словарном) порядке.

Упражнение. Определить во введённых нами терминах какой-либо однозначный порядок наследования имущества.

Вернёмся к задаче о раскраске. Идея её проста – перебирать и проверять неполные, незаконченные раскраски, т.е. все последовательности c₁…c_k, k£n, n – число стран. Если неполная раскраска неправильна, то нет смысла перебирать раскраски большей длины, надо искать новый вариант – возврат.

Дата добавления: 2014-01-05