Процесс работы алгоритма

Шаг	X0	X1	X2	X3	X4	X5	Xt
0	0
1		7	2
2		5		7
3				6	10		15
4					9	13	15
5						12	11

Квадратами выделены окончательные метки. Путь перемещения от  к  отмечен в таблице ломаной кривой через вершины  и его длина равна 11 (рис.3).

Рис.3. Представление найденного пути на графе примера

Далее приводится алгоритм для создания компьютерной программы поиска пути на графе.

For  do

Begin

Mark[x] = FALSE;

Dist[x] = ;

End;

y = x0;

Mark[x0] = TRUE;

Dist[x0] = 0;

While not Mark[xt] do

Begin

For  do

    If not Mark[x] and Dist[x]>Dist[y]+W[y,xt] then

    Begin

        Dist[x]=Dist[y]+w[y,x];

        Prev[x]=y;

     End;

{Поиск новой вершины  с минимальной временной меткой}

Dist[y] = min(Dist[x]); {  and Mark[x]=FALSE}

Mark[y] = TRUE;

End.

В приведенном алгоритме граф представляется матрицей весов W. Вектор Mark[x] меток вершин устанавливает принадлежность вершины  постоянной (TRUE) или временной (FALSE) метке. Вектор Dist в алгоритме фиксирует текущие значения вершин. Вектор Prev позволяет восстановить в обратной последовательности вершины найденного пути. Prev[x] указывает на вершину с окончательной меткой, ближайшую к вершине x. Последовательность вершин найденного пути будет иметь следующий вид: xt, Prev[xt], Prev[Prev[xt]], Prev[Prev[Prev[xt]]], …, x0, а значение Dist[xt] составит длину пути из x0 d xt. Очередная новая вершина, претендующая на постоянную метку, обозначается через y.

ВАРИАНТЫ ЗАДАНИЙ

Задания к лабораторной работе состоят из двух частей.

1. Определение оптимального плана действий для игры в восемь - задача №1.

2. Нахождение пути в графе пространства состояний - задача №2.

Данные к выполнению заданий сгруппированы в таблицах (табл. 3, 4).

Таблица 3

Исходные данные для решения задачи №1

№ варианта	Начальная  ситуация	№ варианта	Начальная  ситуация
1	1 3 4   6 2 8 7 5	6	8 1 3 7 4   6 2 5
2	2 6 3 1 4   8 7 5	7	2   3 1 8 6 7 5 4
3	8 1 3   2 5 7 4 6	8	1 3 4 7 2   6 8 5
4	2 3 4 1 6   8 7 5	9	8 1 2 7 4 3   6 5
5	1 4 2 8 6   7 5 3	10	8 1 3   2 6 7 5 4

 

 

Таблица 4