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

Содержание.

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

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

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

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

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

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

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

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

9. Список литературы

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

Перечислить все способы расстановки 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;

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

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

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

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

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

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

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

Решение. Пусть 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) = n0 +n1 +n2 +n3 +…+nn.

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

1234567
Общее кол-во листьев2740341390655987960800
Кол-во вершин построенного дерева.2341754153552
Время построения(сек)<0.01<0.01<0.01<0.01<0.01<0.01<0.01
8910111213
Общее кол-во листьев
Кол-во вершин построенного дерева.20578394355391669268561894674890
Время построения(сек)<0.010.211.206.4837.12231.29

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

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

N=4

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

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

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

N =12345678910111213
R=1002104409235272426801420073712

Cписок литературы.

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

2) Евстигнеев В. А. Применение теории графов в программировании. – М.:Наука, 1984.

3) Основной алгоритм находился на BBS “Master of Univercity” в файле shen. rar в файловой области “Bardak” (тел. 43-27-03; время работы 21.00 – 7.00; FTN адрес – 2:5090/58).


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