Логическое программирование на языке Visual Prolog. Солдатова О.П - 62 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

62
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 (L1, L2, L3):-select (X, L1, L11),
not (attack1 (X,L2)),
queens (L11, [X|L2], L3).
queens ([], L, L).
fqueens(N,L):-range (1, N, L1),
queens(L1,[],L).
goal
fqueens (4,L),write(L).
При таком задании цели, будет выдано второе решение,
представленное на рисунке, если задать внешнюю цель, то будут выданы
оба решения.
В данной программе реализован принцип «образоввать и проверить»,
так как сначала с помощью предиката range генерируется список,
содержащий числа от 1 до N. Предикат select
перебирает все элементы из
полученного списка для размещения очередного ферзя, при этом
корректность размещения проверяется при помощи предиката attack. Таким
образом, генератором является предикат select, а проверка реализуется при
помощи отрицания предиката attack. Чтобы проверить, в безопасном
положении находится новый ферзь, необходимо знать позиции ранее
размещенных ферзей. В данном случае для хранения промежуточных
результатов
используется второй параметр предиката queens, так как
решение задачи находится на прямом ходе рекурсии, для закрепления
результата при выходе из рекурсии используется третий параметр.
3 Основные стратегии решения задач. Поиск решения в
пространстве состояний
3.1 Понятие пространства состояния
Пространство состояний – это граф, вершины которого соответствуют
ситуациям, встречающимся в задаче («проблемные ситуации»), а
решение
задачи сводится к поиску путей на этом графе. На самом деле, задача поиска
пути на графе и задача о N ферзях - это задачи, использующие одну из
стратегий перебора альтернатив в пространстве состояний, а именно –
стратегию поиска в глубину.
Рассмотрим другие задачи, для решения которых можно использовать
в качестве общей
схемы решения пространство состояний.

Страницы