birmaga.ru
добавить свой файл

1


Ю.Ю. Горюнов (к.ф.-м.н., доцент), Т.Ю. Горюнова (к.п.н., доцент)

ПОИСК МАРШРУТОВ В ГРАФАХ В СИСТЕМЕ VISUAL PROLOG

г. Пенза, РГУИТП Пензенский филиал
Достаточно большое количество практических задач можно сформулировать в терминах поиска маршрута из заданной начальной вершины в заданную конечную вершину в некотором графе. В некоторых таких задачах требуется просто найти такой маршрут, в других задачах этот маршрут должен удовлетворять определённым условиям, например, требуется найти наикратчайший маршрут, либо этот маршрут должен содержать все вершины графа.

Как правило, задачи поиска маршрутов в графах решаются только методом полного перебора. Поэтому при программном решении таких задач наиболее подходящим языком программирования является Пролог, так как перебор вариантов является частью его алгоритма унификации. Говоря иначе, в программах на Прологе не надо задавать сам поиск маршрута, достаточно указать какие вершины в графе являются соседними.

В настоящее время кроме программного решения задачи требуется его визуализация и создание современного интерфейса. Всем этим требованиям удовлетворяют приложения, создаваемые в системе Visual Prolog.

В данной статье демонстрируется возможности системы Visual Prolog на примере решения следующей известной задачи. Найти наикратчайший маршрут шахматного коня от поля (a, b) до поля (c, d) при движении по доске размером m×n. Числовые значения горизонталей и вертикалей начального и конечного полей, а также размеры доски вводятся интерактивно.

Задача об обходе шахматной доски конём сводится к задаче обхода графа следующим образом.

Пронумеруем горизонтали и вертикали шахматной доски, тогда множество полей m×n доски будет находиться во взаимно однозначном соответствии с множеством пар 

Определим на множестве  бинарное отношение , положив , если с поля  за один ход коня можно попасть на поле .


Очевидно, что  является нерефлексивным и симметричным бинарным отношением. Поэтому пара  является графом.

Следовательно, обход шахматной m×n доски конём равносилен обходу графа .

Для нахождения наикратчайшего маршрута следует найти все маршруты из начального поля в конечное. Найдя очередной маршрут, запоминаем его, если его длина меньше длины маршрута, хранящегося в памяти.

Состав проекта. Окно “Step_Horse”, в которое вставлены три элемента управления (ЭУ) «группировка», шесть ЭУ «статический текст», шесть ЭУ «поле редактирования», один ЭУ «кнопка».

Результат работы приложения для поиска наикратчайшего маршрута от поля (1. 1) до поля (2, 2) на шахматной доске 4×4 показан на следующем рисунке.



Для контроля работы приложения в окно Messages можно вывести все маршруты из начального до конечного поля.

Следует отметить, что на 4×4 доске из поля (1, 1) до поля (2, 2) ведут 136 маршрутов.

Программу, создаваемую в Visual Prolog, условно можно разделить на две части: объявление доменов, предикатов и объявление обработчиков событий. Все эти объявления можно поместить в «свой» модуль, либо использовать модуль, создаваемый системой Visual Prolog.

Ниже приводятся все необходимые объявления.

Объявление доменов.

domains

field = f(integer Y, integer X) % поле доски,

list = field* % список полей.

Объявление динамического предиката.

facts-dbd

paths(list Path, integer Length) % для запоминания маршрутов.

Объявление предикатов.


predicates

nondeterm % в клетку Next можно попасть из клетки Cur:

step(field Cur, field Next, integer MaxX, integer MaxY)

nondeterm % начало поиска маршрута из поля Cur:

begin(field Cur, field Finish, integer MaxX, integer MaxY)

nondeterm % ищем все маршруты из Start в Finish:

allPaths(field Start, field Finish, integer MaxX, integer MaxY)

nondeterm % маршрут от текущей клетки доски до конечной:

path(field Current, list, field Finish, integer MaxX, integer MaxY)

nondeterm % поле принадлежит списку?

member(field, list)

out_list(list) % вывод элементов списка в окно Messages,

number_el(list, integer) % количество элементов в списке,

remember_path(list, integer) % запомнить список и его длину,

nondeterm % рисуем вертикальные линии шахматной доски:

draw_vert_lines(window, integer Xstart, integer Xend)

nondeterm % рисуем горизонтальные линии шахматной доски:

draw_hori_lines(window, integer Ystart, integer Yend)

nondeterm % нумеруем клетки доски по горизонтали:

draw_num_hori(window, integer Ystart, integer Yend)

nondeterm % нумеруем клетки по вертикали:

draw_num_vert(window, integer Ystart, integer Yend)

nondeterm % рисуем маршрут.

draw_path(window, list)

clauses

allPaths(v(X, Y), v(EndX, EndY), MaxX, MaxY) :-

begin(v(X, Y), v(EndX, EndY), MaxX, MaxY),

fail. % fail заставит Пролог найти все маршруты.

allPaths(_, _, _, _).

begin(v(X, Y), v(EndX, EndY), MaxX, MaxY) :-

% помещаем начальную вершину в список:

path(v(X, Y), [v(X, Y)], v(EndX, EndY), MaxX, MaxY).

begin(_, _, _, _).

path(v(EndX, EndY), Was, v(EndX, EndY), _, _) :-

% требуемый маршрут найден, запоминаем его:

nl, out_list(Was), number_el(Was, N), remember_path(Was, N).


path(v(X, Y), Was, v(EndX, EndY), MaxX, MaxY) :-

% продолжаем искать маршрут:

step(v(X, Y), v(Z, T), MaxX, MaxY), % соседняя вершина,

not(member(v(Z, T), Was)), % там уже были? – нет,

% помещаем её в список и продолжаем поиск:

path(v(Z, T), [v(Z, T)|Was], v(EndX, EndY), MaxX, MaxY).

member(H, [H|_]).

member(H, [_|T]) :- member(H, T).

% Две вершины являются соседними, если из первой можно попасть

% во вторую за один ход коня, то есть их координаты удовлетворяют

% одной из восьми перечисленным ниже зависимости:

step(v(X, Y), v(X1, Y1), _, MaxY) :- X>1, Y
step(v(X, Y), v(X1, Y1), _, MaxY) :- X>2, Y
step(v(X, Y), v(X1, Y1), MaxX, MaxY) :-

X
step(v(X, Y), v(X1, Y1), MaxX, MaxY) :-

X
step(v(X, Y), v(X1, Y1), _, _) :-X>1, Y>2, X1=X-1, Y1=Y-2.

step(v(X, Y), v(X1, Y1), _, _) :- X>2, Y>1, X1=X-2, Y1=Y-1.

step(v(X, Y), v(X1, Y1), MaxX, _) :- X2, X1=X+1, Y1=Y-2.

step(v(X, Y), v(X1, Y1), MaxX, _) :- X1, X1=X+2, Y1=Y-1.

out_list([]):-!.

out_list([v(X,Y)|T]):- out_list(T), write("(", X, ",", Y, ") ").

number_el([ ], 0).

number_el([_|T], N) :- number_el(T, N1), N=N1+1.

remember_path(Path, Length):-

% найденный маршрут запоминается, если его длина меньше длины

% маршрута хранящегося в памяти; старый маршрут забывается:

paths(_, N), Length
asserta(paths(Path, Length)),!.

remember_path(_,_):- !.

% Предикаты для рисования доски и нумерации её горизонталей

% и вертикалей. Все эти предикаты первым аргументом имеют

% дескриптор окна из домена window.

draw_vert_lines(_, X, Xend) :- X>Xend.


draw_vert_lines(Win, X, Xend) :- draw_Line(Win, pnt(X, 15), pnt(X, 135)),

X1=X+30, draw_vert_lines(Win, X1, Xend).

draw_hori_lines(_, Y, Yend) :- Y>Yend.

draw_hori_lines(Win, Y, Yend) :- draw_Line(Win, pnt(15, Y), pnt(135, Y)),

Y1=Y+30, draw_hori_lines(Win, Y1, Yend).

draw_num_hori(_, X, Xend) :- X>Xend.

draw_num_hori(Win, X, Xend) :- X1=X*30-4, str_int(SX, X),

draw_Text(Win, X1, 149, SX), X2= X+1,

draw_num_hori(Win, X2, Xend).

draw_num_vert(_, Y, Yend) :- Y>Yend.

draw_num_vert(Win, Y, Yend) :- Y1=120-(Y-1)*30+6, str_int(SY, Y),

draw_Text(Win, 3, Y1, SY), Y2= Y+1,

draw_num_vert(Win, Y2, Yend).

draw_path(_, [v(_,_)]).

draw_path(Win, [v(X1,Y1),v(X2,Y2)|T]) :-

X11=30*X1, Y11=120-(Y1-1)*30, X21=30*X2, Y21=120-(Y2-1)*30,

draw_Line(Win, pnt(X11,Y11),pnt(X21,Y21)),

draw_path(Win,[v(X2,Y2)|T]).

Объявление обработчика событий.

%BEGIN Delete_Odd, idc_обход _CtlInfo

% событие «нажали кнопку «обход»»:

win_delete_odd_eh(_Win, e_Control(idc_обход, _CtrlType, _CtrlWin, _CtlInfo), 0) :-

% дескриптор ЭУ «поле редактирования», в котором хранится

% размер доски по горизонтали:

W1=win_GetCtlHandle(_Win, idc_horizontx),

% получаем строку из ЭУ «поле редактирования»:

S1=win_GetText(W1),

% преобразуем строку в число:

str_int(S1, MaxX),

% Следующими предикатами получаем числовые значения

% в оставшихся пяти ЭУ «поле редактирования»:

W2=win_GetCtlHandle(_Win, idc_verticaly),

S2=win_GetText(W2), str_int(S2, MaxY),

W3=win_GetCtlHandle(_Win, idc_xstart),

S3=win_GetText(W3), str_int(S3, XStart),

W4=win_GetCtlHandle(_Win, idc_ystart),

S4=win_GetText(W4), str_int(S4, YStart),

W5=win_GetCtlHandle(_Win, idc_xend),


S5=win_GetText(W5), str_int(S5, EndX),

W6=win_GetCtlHandle(_Win, idc_yend),

S6=win_GetText(W6), str_int(S6, EndY),

Size=MaxX*MaxY, asserta(paths([], Size)),

% Перебираем все маршруты и запоминаем наикратчайший:

allPaths(v(XStart, YStart), v(EndX, EndY), MaxX, MaxY),

% Берём из памяти наикратчайший маршрут и выводим его в окно

% Messages:

paths(L, N), nl, write("Наикратчайший маршрут: "),

out_list(L),nl, write("Длина: ",N),

% Рисуем доску:

draw_vert_lines(_Win, 15,135), draw_hori_lines(_Win, 15,135),

% Отмечаем начальное и конечное поля:

X1=30*Xstart-9, Y1=120-(Ystart-1)*30+9, draw_Text(_Win, X1, Y1, "b"),

X2=30*EndX-9, Y2=120-(EndY-1)*30+9, draw_Text(_Win, X2, Y2, "e"),

% Нумеруем горизонтали и вертикали:

draw_num_hori(_Win, 1, 4), draw_num_vert(_Win, 1, 4),

% Рисуем маршрут:

draw_path(_Win, L),

!.

%END Delete_Odd, idc_обход _CtlInfo
Список литературы.

1. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003.

2. Горюнов Ю.Ю., Горюнова Т.Ю. Использование языка Visual Prolog для представления знаний. – Пенза: Изд-во Пенз. ин-та экономического развития и антикризисного управления, 2008.