Математическая логика и теория алгоритмов

Скачать реферат: Математическая логика и теория алгоритмов

Постановка задачи

Перечислить все способы расстановки n ферзей на шахматной доске n на n, при которых они не бьют друг друга.

Построение модели

Очевидно, на каждой из n горизонталей должно стоять по ферзю. Будем называть k-позицией (для k = 0, 1,..., n) произвольную расстановку k ферзей на k нижних горизонталях (ферзи могут бить друг друга). Нарисуем "дерево позиций": его корнем будет единственная 0-позиция, а из каждой k-позиции выходит n стрелок вверх в (k + 1)-позиции. Эти n позиций отличаются положением ферзя на (k + 1)-ой горизонтали. Будем считать, что расположение их на рисунке соответствует положению этого ферзя: левее та позиция, в которой ферзь расположен левее.

Дерево позиций для n = 2.

Данное дерево представлено только для наглядности и простоты представления для n = 2.

Среди позиций этого дерева нам надо отобрать те n-позиции, в которых ферзи не бьют друг друга. Программа будет "обходить дерево" и искать их. Чтобы не делать лишней работы, заметим вот что: если в какой-то k-позиции ферзи бьют друг друга, то ставить дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении.

Точнее, назовем k-позицию допустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга. Наша программа будет рассматривать только допустимые позиции.

Описание алгоритма

Разобьем задачу на две части: (1) обход произвольного дерева и (2) реализацию дерева допустимых позиций.

Сформулируем задачу обхода произвольного дерева. Будем считать, что у нас имеется Робот, который в каждый момент находится в одной из вершин дерева. Он умеет выполнять команды:

  • вверх_налево (идти по самой левой из выходящих вверх стрелок);
  • вправо (перейти в соседнюю справа вершину);
  • вниз (спуститься вниз на один уровень);
  • вверх_налево;
  • вправо;
  • вниз.

Также осуществляет проверки, соответствующие возможности выполнить каждую из команд, называемые "есть_сверху", "есть_справа", "есть_снизу" (последняя истинна всюду, кроме корня). Обратите внимание, что команда "вправо" позволяет перейти лишь к "родному брату", но не к "двоюродному".

Будем считать, что у Робота есть команда "обработать" и что его задача — обработать все листья (вершины, из которых нет стрелок вверх, то есть где условие "есть_сверху" ложно). Для нашей шахматной задачи команде обработать будет соответствовать проверка и печать позиции ферзей.

Доказательство правильности приводимой далее программы использует такие определения. Пусть фиксировано положение Робота в одной из вершин дерева. Тогда все листья дерева разбиваются на три категории: над Роботом, левее Робота и правее Робота (Путь из корня в лист может проходить через вершину с Роботом, сворачивать влево, не доходя до нее, и сворачивать вправо, не доходя до нее). Через (ОЛ) обозначим условие "обработаны все листья левее Робота", а через (ОЛН) — условие "обработаны все листья левее и над Роботом"

Нам понадобится такая процедура:

procedure вверх_до_упора_и_обработать

{дано: (ОЛ), надо: (ОЛН)}

begin

{инвариант: ОЛ}

while есть_сверху do begin

вверх_налево

end

{ОЛ, Робот в листе}

обработать;

{ОЛН}

end;

Основной алгоритм:

дано: Робот в корне, листья не обработаны

надо: Робот в корне, листья обработаны

{ОЛ}

вверх_до_упора_и_обработать

{инвариант: ОЛН}

while есть_снизу do begin

if есть_справа then begin {ОЛН, есть справа}

вправо;

{ОЛ}

вверх_до_упора_и_обработать;

end else begin

{ОЛН, не есть_справа, есть_снизу}

вниз;

end;

end;

{ОЛН, Робот в корне => все листья обработаны}.

Осталось воспользоваться следующими свойствами команд Робота (сверху записаны условия, в которых выполняется команда, снизу — утверждения о результате ее выполнения):

{ОЛ, не есть_сверху} обработать {ОЛН}

{ОЛ} вверх_налево {ОЛ}

{есть_справа, ОЛН} вправо {ОЛ}

{не есть_справа, ОЛН} вниз {ОЛН}

Теперь решим задачу об обходе дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья).

Решение. Пусть x — некоторая вершина. Тогда любая вершина y относится к одной из четырех категорий. Рассмотрим путь из корня в y. Он может:

  • быть частью пути из корня в x (y ниже x);
  • свернуть налево с пути в x (y левее x);
  • пройти через x (y над x);
  • свернуть направо с пути в x (y правее x).

В частности, сама вершина x относится к последней категории. Условия теперь будут такими:

(ОНЛ) обработаны все вершины ниже и левее;

(ОНЛН) обработаны все вершины ниже, левее и над.

Вот как будет выглядеть программа:

procedure вверх_до_упора_и_обработать

{дано: (ОНЛ), надо: (ОНЛН)}

begin

{инвариант: ОНЛ}

while есть_сверху do begin

обработать

вверх_налево

end

{ОНЛ, Робот в листе}

обработать;

{ОНЛН}

end.

Основной алгоритм:

дано: Робот в корне, ничего не обработано

надо: Робот в корне, все вершины обработаны

{ОНЛ}

вверх_до_упора_и_обработать

{инвариант: ОНЛН}

while есть_снизу do begin

if есть_справа then begin {ОНЛН, есть справа}

вправо;

{ОНЛ}

вверх_до_упора_и_обработать;

end else begin

{ОЛН, не есть_справа, есть_снизу}

вниз;

end;

end;

{ОНЛН, Робот в корне => все вершины обработаны}.

Приведенная только что программа обрабатывает вершину до того, как обработан любой из ее потомков. Теперь изменим ее, чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз после всех своих потомков. Листья по-прежнему обрабатываются по разу.

Под "обработано ниже и левее" будем понимать "ниже обработано по разу, слева обработано полностью (листья по разу, остальные по два)". Под "обработано ниже, левее и над" будем понимать "ниже обработано по разу, левее и над — полностью".

Программа будет такой:

procedure вверх_до_упора_и_обработать

{дано: (ОНЛ), надо: (ОНЛН)}

begin

{инвариант: ОНЛ}

while есть_сверху do begin

обработать

вверх_налево

end

{ОНЛ, Робот в листе}

обработать;

{ОНЛН}

end.

Основной алгоритм:

дано: Робот в корне, ничего не обработано

надо: Робот в корне, все вершины обработаны

{ОНЛ}

вверх_до_упора_и_обработать

{инвариант: ОНЛН}

while есть_снизу do begin

if есть_справа then begin {ОНЛН, есть справа}

вправо;

{ОНЛ}

вверх_до_упора_и_обработать;

end else begin

{ОЛН, не есть_справа, есть_снизу}

вниз;

обработать;

end;

end;

{ОНЛН, Робот в корне => все вершины обработаны полностью}.

Доказательство правильности алгоритма

Докажем, что приведенная программа завершает работу (на любом конечном дереве).

Доказательство. Процедура вверх_налево завершает работу (высота Робота не может увеличиваться бесконечно). Если программа работает бесконечно, то, поскольку листья не обрабатываются повторно, начиная с некоторого момента, ни один лист не обрабатывается. А это возможно, только если Робот все время спускается вниз. Противоречие.

Блок-схема алгоритма

Описание переменных и программа

Теперь реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной k: 0..n (число ферзей) и массива c: array [1..n] of 1..n (c [i] — координаты ферзя на i-ой горизонтали; при i > k значение c [i] роли не играет). Предполагается, что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг друга).

program queens;

const n = ...;

var k: 0..n;

c: array [1..n] of 1..n;

procedure begin_work; {начать работу}

begin

k:= 0;

end;

function danger: boolean; {верхний ферзь под боем}

var b: boolean;

i: integer;

begin

if k <= 1 then begin

danger:= false;

end else begin

b:= false; i:= 1;

{b <=> верхний ферзь под боем ферзей с номерами < i}

while i <> k do begin

b:= b or (c[i] = c[k]) {вертикаль}

or (abs(c[i]-c[k]) = abs(i-k)); {диагональ}

i:= i+ 1;

end;

danger:= b;

end;

end;

function is_up: boolean {есть_сверху}

begin

is_up:= (k < n) and not danger;

end;

function is_right: boolean {есть_справа}

begin

is_right:= (k > 0) and (c[k] < n);

end;

{возможна ошибка: при k=0 не определено c[k]}

function is_down: boolean {есть_снизу}

begin

is_up:= (k > 0);

end;

procedure up; {вверх_налево}

begin {k < n}

k:= k + 1;

c [k]:= 1;

end;

procedure right; {вправо}

begin {k > 0, c[k] < n}

c [k]:= c [k] + 1;

end;

procedure down; {вниз}

begin {k > 0}

k:= k - 1;

end;

procedure work; {обработать}

var i: integer;

begin

if (k = n) and not danger then begin

for i:= 1 to n do begin

write ('<', i, ',' , c[i], '> ');

end;

writeln;

end;

end;

procedure UW; {вверх_до_упора_и_обработать}

begin

while is_up do begin

up;

end

work;

end;

begin

begin_work;

UW;

while is_down do begin

if is_right then begin

right;

UW;

end else begin

down;

end;

end;

end.

Расчёт вычислительной сложности

Емкостная сложность

В программе используется одномерный массив размерности n, поэтому объём входа и объём выхода совпадают и равны n. Количество переменных равно 3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.

С(n) = n + 4

Временная сложность

Если рассматривать обработку каждого листа, без проверки на пути к нему, то временная сложность T(n) = n 0 + n 1 + n 2 + n 3 +…+ n n

Но в случае, когда каждая вершина проверяется, временная сложность T(n) = o (n 0 + n 1 + n 2 + n 3 +…+ n n ). И это тем вернее, чем больше n. Данный вывод получен на основе приведённых ниже статистических данных:

1

2

3

4

5

6

7

Общее кол-во листьев

2

7

40

341

3906

55987

960800

Кол-во

вершин построенного дерева

2

3

4

17

54

153

552

Время построения

(с)

<0.01

<0.01

<0.01

<0.01

<0.01

<0.01

<0.01

8

9

10

11

12

13

Общее кол-во листьев

 

 

 

 

 

 

Кол-во вершин построенного дерева

2057

8394

35539

166926

856189

4674890

Время построения

(с)

<0.01

0.21

1.20

6.48

37.12

231.29

Тестирование

Построенная по описанному алгоритму программа при различных n выдаёт следующие данные:

N = 4

<1,2><2,4><3,1><4,3>

<1,3><2,1><3,4><4,2>

Т.е. количество расстановок равно 2. Ниже приведена таблица зависимости от n количества решений (R).

n =

1

2

3

4

5

6

7

8

9

10

11

12

13

R =

1

0

0

2

10

4

40

92

352

724

2680

14200

73712

Библиографический список

  1. Кузнецов О. П. Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988 г.
  2. Евстигнеев В.А. Применение теории графов в программировании. — М.:Наука, 1984 г.