Var I:tСтраны; c:tЦвет;

Begin

кончились:=false;

i:=последняя страна;

c:=раскраска[i];

while not Кончились and (раскраска[i]последний цвет) do

begin

раскраска[i]:=первый цвет;

i:=i-1;

кончились:=i=0;

end;

if not Кончились then раскраска[i]:=succ(раскраска[i]);

end;

{Поддерживается быстрое вычисление конъюнкции}

Упражнение. Завершить первый вариант решения задачи.

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

Вопрос: нужно ли было писать такой алгоритм???

Ответ: несомненно, ДА!!!

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

Два взгляда на диаграммы – графы и автоматы.

Нахождение решений как поиск пути в графе. Полный перебор как универсальный алгоритм.

Графом называется некоторое множество вершин Х, соединённых рёбрами F.

GraphXXV

С каждым графом можно связать функцию, ставящую в соответствие каждой паре вершин некоторое ребро (либо его отсутствие). Для этого нужно ввести некоторое неопределённое значение. В самом простом случае интересно лишь наличие, либо отсутствие ребра, т.е. функция вида Graph(i,j)=trueboolean. Это в классической дискретной математике определение графа как отношения или двуместного предиката.

Graph(i,j)=true – существует стрелка из вершины i в вершину j. Отношение соседства из задачи по раскраске – пример именно такого определения графа.

Англия

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

 Франция

 Италия 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

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

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

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

задачи.

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

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

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

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

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

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

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

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

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