Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Поиск пути на графе




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

Пример 59:

Определить путь между вершинами графа, представленного на рисунке:

A- переменная обозначающая начало пути

B- вершина в которую нужно попасть

P -ациклический путь на графе (ациклический путь- это путь не имеющий повторяющих вершин).

 

 


domains

top=symbol

listtop=top*

predicates

edge (top, top)

/* аргументы обозначают имена вершин */

path (top, top, listtop)

/*Предикат path(top, top, listtop) создает список из вершин, составляющих путь.*/

clauses

edge (a, b).

edge (c, b).

edge (a, c).

edge (b, d).

edge (d, e).

path (A, A, [A]).

path (A, B, [A\P]):-edge(A, N), path(N, B, P).

С помощью поиска в глубину осуществляется корректный обход любого конечного дерева или ориентированного ациклического графа. Однако, встречаются задачи, где требуется производить обход графа с циклами. В процессе вычислений может образоваться бесконечный программный цикл по одному из циклов графа.

Неприятностей с зацикливанием можно избежать модификацией отношения connected. К аргументам отношения добавляется дополнительный аргумент, используемый для накопления уже пройденных при обходе вершин, для исключения повторного использования одного и того же состояния применяется проверка.

Пример 60: написать программу обхода конечного ориентированного графа, представленного на рисунке.


domains

top=symbol

listtop=top*

predicates

edge(top,top)

connected(top,top,listtop,listtop)

connect(top,top)

member(top,listtop)

clauses

edge(a,b).

edge(b,c).

edge(c,a).

edge(b,d).

edge(d,e).

member(A,[A|T]):-!.

member(A,[B|T]):-member(A,T).

connected(A,B,V,[B|V]):-edge(A,B).

connected(A,B,V,V2):-edge(A,N),not(member(N,V)),

V1=[N|V],connected(N,B,V1,V2).

connect(A,B):-connected(A,B,[A],V),write(V).

goal

connect(a,b).

Метод “образовать и проверить”

Метод “образовать и проверить” – общий прием, используемый при проектировании алгоритмов и программ. Суть его состоит в том, что один процесс или программа генерирует множество предполагаемых решений задачи, а другой процесс или программа проверяет эти предполагаемые решения, пытаясь найти те из них, которые действительно являются решением задачи.

Используя вычислительную модель Пролога, легко создавать логические программы, реализующие метод “образовать и проверить”. Обычно такие программы содержат конъюнкцию двух целей, одна из которых действует как генератор предполагаемых решений, а вторая проверяет, являются ли эти решения премлимыми. В Прологе метод “образовать и проверить” рассматривается как метод недетерминированного программирования. В такой недетерминированной программе генератор вносит предположение о некотором элементе из области возможных решений, а затем просто проверяется, корректно ли данное предположение генератора.

Для написания программ недетерминированного выбора корретного элемента из некоторого списка в качестве генератора обычно используют предикат member из примера 36, порождающий множество решений. При задании цели member (X, [1,2,3,4]) будут даны в требуемой последовательности решения X=1, X=2, X=3, X=4.

Пример 61: проверить существование в двух списках одного и того же элемента.

domains

list=integer*

predicates

member (integer, list)

clauses

member (Head, [Head |_ ]).

member (Head, [_ | Tail ]):- member (Head, Tail).

intersect (L1, L2):- member(X, L1), member(X, L2).

goal

intersect ([1, 4, 3, 2], [2, 5,6]).

Первая подцель member в предикате intersect генерирует элементы из первого списка, а с помощью второй подцели member проверяется, входят ли эти элементы во второй список. Описывая данную программу как недетерминированную, можно говорить, что первая цель делает предположение о том, что X содержится в списке L1, а вторая цель проверяет, является ли X элементом списка L2.

Следующее определение предиката member с использованием предиката append:

member(X, L):- append(L1, [X|L2], L) само по существу является программой, в которой реализован принцип «образовать и проверить». Однако, в данном случае, два шага метода сливаются в один в процессе унификации. С помощью предиката append производится расщепление списка и тут же выполняется проверка, является ли X первым элементом второго списка.

Еще один пример преимущества соединения генерации и проверки дает программа для решения задачи об N ферзях: требуется разместить N ферзей на квадратной доске размером NxN так, чтобы на каждой горизонтальной, вертикальной или диагональной линии было не больше одной фигуры. В первоначальной формулировке речь шла о размещении 8 ферзей на шахматной доске таким образом, чтобы они не угрожали друг другу. Отсюда пошло название задачи о ферзях.

Эта задача хорошо изучена в математике. Для N=2 и N=3 решения не существует; два симметричных решения при N=4 показаны на рисунке. Для N=8 существует 88 (а с учетом симметричных – 92) решений этой задачи.

    Q  
Q      
      Q
  Q    

 

  Q    
      Q
Q      
    Q  

Приведенная в примере 62 программа представляет решение задачи об N ферзях. Решение задачи представляется в виде некоторой перестановки списка от 1 до N. Порядковый номер элемента этого списка определяет номер вертикали, а сам элемент – номер горизонтали, на пересечении которых стоит ферзь. Так решение [2, 4, 1, 3] задачи о четырех ферзях соответствует первому решению, представленному на рисунке, а решение [3, 1, 4, 2] - второму решению. Подобное описание решений и программа их генерации неявно предполагают, что в любом решении задачи о ферзях на каждой горизонтали и на каждой вертикали будет находиться по одному ферзю.

Пример 62: программа решения задачи об N ферзях.

domains

list=integer*

predicates

range (integer, integer, list)

/* предикат порождает список, содержащий числа в заданном интервале*/

queens (integer, list, list, list)

/* предикат формирует решение задачи о N ферзях в виде списка решений, при этом первый список – текущий вапиант списка размещения ферзей, второй список промежуточное решение, третий список - рузультат*/

select (integer, list, list)

/*предикат удаляет из списка одно вхождение элемента*/

attack1 (integer, list)

/*предикат преобразует attack, чтобы ввести начальное присваивание разности в номерах горизонталей, делается это из-за ограничений языка Турбо-Пролог*/

attack (integer, integer, list)

/*предикат проверяет условие атаки ферзя других ферзей из списка, два ферзя находятся на одной и той же диагонали, на расстоянии M вертикалей друг от друга, если номер горизонтали одного ферзя на M больше или на M меньше номера горизонтали другого ферзя*/

fqueens (integer, list)

clauses

range (M, N, [M|T]):- M<N, M1=M+1, range (M1, N, T).

range (N, N, [N]):-!.

select(X,[X|T1],T1).

select (X, [Y|T1], [Y|T2]):-select (X, T1, T2).

attack1 (X, L):- attack(X, 1, L).

attack(X, N, [Y|T2]):-N=X-Y; N=Y-X.

attack(X, N, [Y|T2]):-N1=N+1, attack (X, N1, T2).

queens (N, L1, L2, L3):-select (X, L1, L11),

not (attack1 (X,L2)),

queens (N,L11, [X|L2], L3).

queens (N,[], L, L).

fqueens(N,L):-range (1, N, L1),

queens(N,L1,[],L).

goal

fqueens (4,L),write(L).

При таком задании цели, будет выдано второе решение, представленное на рисунке, если задать внешнюю цель, то будут выданы оба решения.

В данной программе реализован принцип «образоввать и проверить», так как сначала с помощью предиката range генерируется список, содержащий числа от 1 до N. Предикат select перебирает все элементы из полученного списка для размещения очередного ферзя, при этом корректность размещения проверяется при помощи предиката attack. Таким образом, генератором является предикат select, а проверка реализуется при помощи отрицания предиката attack. Чтобы проверить, в безопасном положении находится новый ферзь, необходимо знать позиции ранее размещенных ферзей. В данном случае для хранения промежуточных результатов используется третий параметр предиката queens, так как решение задачи находится на прямом ходе рекурсии, для закрепления результата при выходе из рекурсии используется четвертый параметр.




Поделиться с друзьями:


Дата добавления: 2015-06-27; Просмотров: 402; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.025 сек.