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

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. Отношение соседства из задачи по раскраске – пример именно такого определения графа.

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