Алгоритм полного перебора раскрасок

function Правильная(r: tРаскраска): boolean;

begin

b: =true;

i: =ПерваяВершина;

while (i< =pred(ПоследняяВершина)) and not b do

begin j: =succ(i);

while (j< =ПоследняяВершина) and not b do

if Coседи(i, j) and (Цвет(r, i)=Цвет(r, j))

then b: =false else j: =succ(j);

i: =succ(i)

end;

procedure ПолныйПеребор (graph: tGraph; var found: boolean);

var r: tРаскраска; exists: boolean; {}

begin

r: =ПерваяРаскраска; found: =false; exists: =true;

while exists (= not КончилисьРаскраски} do

begin if Правильная(r) then begin found: =true; Печать(r) end

Следующая(r, exists) {r: =Следующая(r)}

end;

end;

Дальнейший анализ.

Тип tВершины должен быть порядковым. Тип tGraph хорошо бы реализовать так, чтобы было легко вычислять функцию Соседи - задать граф матрицей инциндентности. Тип tРаскраска хорошо бы реализовать так, чтобы было легко вычислять цвет каждой вершины r - реализовать раскраски как стек. Алгоритм прост, но малоэффективен. Перебор всех mⁿ раскрасок - функций/последовательностей [1..n]à [1..m] - дело долгое.

11. Инф Алгоритм перебора с возвратом на примере задачи о перечислении всех правильных раскрасок графа.

Идея сокращения области перебора проста - рассматривать неполные раскраски - динамические последовательности, т.е. функции [1..k]à [1..m], k£ n. Основание - если неполная раскраска r уже не правильна, нет никакого смысла терять время на перебор раскрасок большей длины.

Для этого доопределим лексикографический порядок на последовательностях Seq произвольной длины, Seq= È {Seq(L): LÎ N}. Пусть a, b Î Seq - разной длины LenA и LenB, a¹ b и N=N(a, b)=min {n: a(n) ¹ b(n)}- наименьший номер i, на котором они различаются. Тогда a< b, если

a) Либо NÎ Dom(a) (N £ LenA), NÎ Dom(b) (N £ LenB) и a(N)< _T b(N).

b) Либо NÎ Dom(a) (N £ LenA) и NÏ Dom(b) (N > LenB), т.е. a - начальный отрезок последовательности b

Алгоритм определения следующей последовательности - полностью повторяет полный перебор, за исключением пункта в) (теперь нам не зачем доопределять следующее значение до фиксированной длины). Операцию перехода к следующему значению в таком порядке принято называть возвратом.

procedure ПереборCВозвратом (graph: tGraph; var found: boolean);

var r: tРаскраска; exists: boolean;

begin

r: =ПерваяРаскраска; {заметь - теперь это пустая последовательность! }

found: =false; exists: =true;

while exists {= not КончилисьРаскраски длины менее n} do

begin if Правильная(r)

then if Полная(r) {т.е. длины n}

then begin found: =true; Печать(r) end

else {дополнить - добавить первое значение в T}

Push(r, Первый)

else {не правильная} Возврат(r, exists) {=Следующая(r, exists)}

end;

end;

 

12. Инф Обход дерева «в глубину» (с использованием стека) и «в ширину (с использованием очереди)».

Автомат Go - дерево, если существует корневая вершина (начальное состояние автомата) Æ,

a) в которую не ведет ни одно ребро, " aÎ Nodes (Go(r, a)=Æ à a=Æ ),

b) но из которой существует путь в любую вершину,

" aÎ Nodes $ rÎ Arrows (Go(r, Æ )=a),

причем этот путь - единственный, " r, r'Î Arrows (Go(r, Æ )=Go(r', Æ ) à r=r').

Go - бинарное дерево, если, к тому же, множество стрелок состоит из лишь из двух стрелок, далее обозначаемых как левая (left) и правая (right), Arrows={left, right}.

{реализация бинарного дерева ссылками}

pTree=pNode; {дерево задается ссылкой на корень}

pNode=^tNode;

tNode=record

Content: T; {содержимое вершины}

left, right: pNode;

end;

Задача обхода дерева заключается в переборе его вершин в некотором порядке, т.е. построении некоторой функции следования на Arrows*´ Nodes.

Самый простой класс таких порядков связан с лексикографическим порядком на множестве " слов" /путей Arrows*, связанных со всеми возможностями определения такого порядка на " алфавите" - множестве Arrows.

{пример обхода " в глубину" }

{» более короткие ветки идут в перечислении раньше более длинных}

procedure КЛП(root: pTree);

var

pt: pNode; {ссылка на текущую вершину}

stack: pStack;

begin

Create(stack);

if root< > nil then push(stack, root);

while not empty(stack) do

begin

pop(stack, pt); {подъем наверх}

with pt^ do

begin

{ какая-то обработка содержимого текущей вершины pt^.value}

if left< > nil {можешь идти налево? }

then {тогда иди, но сохрани правую ссылку}

begin pt: =left; if right< > nil then push(stack, right) end

else {налево нельзя}

if pt^.right< > nil {- можно ли направо? }

then pt: = pt^.right

end;

Destroy(Stack)

end;

{пример обхода в ширину - ветви одинаковой длины (" буквы" left, right) соседствуют в перечислении}

procedure (root: pTree);.

var

Queue: pQueue;

pt: pNode; {ссылка на текущую вершину}

begin

Create(Queue); {создать очередь}

if root< > nil then Put(Queue, root); {Поставить В Очередь }

while not Empty(Queue) {очередь не пуста} do

begin

Get(Queue, pt); {Вывести Из Очереди}

{обработать содержимое pt^.value вершины pt}

if pt!.left< > nil then Put(Queue, pt!.left);

if pt!.right< > nil then Put(Queue, pt!.right);

end;

Destroy(Queue)

end;

 

 

13. Инф Алгоритмы обработки арифметических выражений. А рифметическое выражение (в полноскобочной инфиксной записи) - последовательность символов, являющуюся

1) либо термом, т.е.

a) либо именем константы вида b₁… b_n.c₁… c_m, где

(n> 0) & (m> 0) & " iÎ [1, n](b_iÎ ['0', '9']) & " jÎ [1, m](c_jÎ ['0', '9'])

b) либо именем переменной вида d₁… d_k, где

(k> 0) & (d₁Î ['a', 'z']) & " iÎ [2, k](d_iÎ ['0', '9']È ['a', 'z'])

2) либо строкой вида (E₁)f(E₂), где E₁, E₂ - выражения, а f - один из знаков +, -, *, /

Определим также дерево выражения E как дерево над базовым типом string, состоящее из единственной вершины, содержащей Е, если Е - терм или же дерево вида

если Е - выражение вида (E₁)f(E₂).

Задача вычисления дерева выражения. Найти результат выражения при заданных значениях переменных, если выражение представлено деревом.

Для краткости и ясности алгоритма как сведения вычисления сложного выражения к вычислению элементарных выражений или атомов, предположим, что значения термов уже найдены и сохранены в самом дереве.

{вычисление элементарного выражения}

function AtomVal(root: pExpr): T;

begin

with root^ do

case Name of

'+': AtomVal: =left^.Val+right^.Val;

'-': AtomVal: =left^.Val-right^.Val;

'*': AtomVal: =left^.Val*right^.Val;

'/': AtomVal: =left^.Val/right^.Val;

{для простоты, опускаем обработку исключения - деления на 0}

end; end;

{выяснение типа вершины}

function NodeType(pt: pNode): char;

begin

with pt^ do

if (right=nil) and (left=nil)

then NodeType='t' {терм}

else NodeType='f' {выражение}

end;

{поиск атома, лежащего ниже данной вершины}

{идея: вычисление $-свойства found: =$ ptÎ pNode (pt¹ nil & pt^.left¹ nil & pt^.right¹ nil) }

procedure FindAtom(var pt: pNode; var stack: pStack);

Синтаксический анализ выражения, представленного деревом. Проверить, является ли произвольное бинарное символьное дерево деревом выражения. Задача синтаксического анализа очевидно распадается на анализ 1) термов и 2) сложных выражений. Анализ термов прост и напрямую сводиться к задаче поиска. Центральная идея: свести задачу анализа сложного выражения к задаче вычисления.

1) Анализ термов.

{Поиск позиции " исключения" - первого символа в подстроке s[start, finish], не принадлежащего множеству alphabet }

procedure FindException

{идея: проверка свойства found=$ positionÎ [start, end] (s[position] Ï alphabet)}

{проверка имени константы}

function ConstantName(s: string): boolean;

{проверка имени переменной }

function VariableName(s: string): boolean;

Анализ (сложных) выражений.

Определим понятие расширенного ( р- ) выражения как строки вида (E₁)F(E₂), где E₁, E₂ - произвольные, в том числе пустые строки, а F - произвольная непустая строка. Любому невырожденному дереву однозначно сопоставляется некоторое р-выражение.

Если р-выражение не имеет типа 'f' или 't', то оно имеет тип 'Æ '. Формальным вычислением р-выражения назовем операцию Reduce:

ì терм 'x', если Тип(E₁)=Тип(E₂)='t' и Тип(F)='f'

Reduce((E₁)F(E₂))= í

î 'Æ ', иначе

(смысл прост - результатом вычисления правильного выражения является терм, а результат вычисления неправильного выражения не определен)

Идея алгоритма: Выражение правильно » тип результата формального вычисления = терм.

{расширенный тип вершины}

function ExtentedNodeType(pt: pNode): char;

{теперь не уверены, что найдутся правильные атомы! }

{но, в таком случае, обязательно найдется не правильный }

procedure FindExtendedAtom(var pt: pNode; var stack: pStack);

{формальное вычисление расширенного элементарного выражения}

function ExtendedAtomVal(root: pExpr): string;

function ExpressionCorrect(root: pExpr): boolean;

 

⇐ Предыдущая123

Поделиться: