Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11634
Последний выпуск: 19.06.2015

Сортировка фактов ПРОЛОГа

Ермолаев Д.С., Москва, www.icreator.ru
09.04.2002

Программа на ПРОЛОГе оперирует с базой знаний, состоящей из фактов. Как правило, поиск решения идет с помощью перебора всех возможных фактов. Это может привести к значительным потерям времени. Поэтому, иногда необходимо отсортировать факты так, что бы программа начинала просмотр знаний с наилучшего варианта для ускорения поиска решения. Здесь предложен алгоритм сортировки фактов языка ПРОЛОГ. Алгоритм и его реализация на Visual Prolog 5.2 была сделана мною за 3 часа. Я не знаю какой это метод, потому как сам его придумал. Я слышал что есть метод с какими-то пузырьками, возможно это его подобие :)

domains
ИмяЗаписи = string
НомерЗаписи, ЗначениеЗаписи = integer
МояЗапись=моя_запись(НомерЗаписи, ИмяЗаписи, ЗначениеЗаписи); пусто

database - мои_записи
мз(МояЗапись)

predicates
показать_мои_записи
значение_записи(МояЗапись,ЗначениеЗаписи)
запись_выбрать(МояЗапись З1, МояЗапись З2, МояЗапись Вставить, МояЗапись Наверх)
запись_вставить(МояЗапись)
сортировка(МояЗапись Вниз, МояЗапись Вверх) - (i,o)
сортировка
откат

clauses

откат:-!,fail.

% взять значение записи
значение_записи(моя_запись(_,_,Значение),Значение):-!.

% выбрать какую запись добавить, а какую передать наверх
запись_выбрать(Запись1,пусто,пусто,Запись1):-!.
запись_выбрать(Запись1,Запись2,Запись1,Запись2):-
	значение_записи(Запись1,Значение1),
	значение_записи(Запись2,Значение2),
	Значение1>Значение2,
	!.
запись_выбрать(Запись1,Запись2,Запись2,Запись1):-
	!.
% вставить факт обратно в базу знаний
запись_вставить(пусто):-!.
запись_вставить(Запись):-
	asserta(мз(Запись)),
	!.

% сама сортировка
сортировка(ЗаписьВниз,ЗаписьНаверх):-
% выбрать запись из базы знаний
	retract(мз(Запись1)),
% определить какую из записей передать вниз,
% а какую возможно вставить в этом предикате
	запись_выбрать(ЗаписьВниз,Запись1,ЗаписьВниз1,ЗаписьВставить1),
% рекурсия сортировки вниз
	сортировка(ЗаписьВниз1,Запись2),
% определить какую запись вставить обратно в знания
% а какую передать наверх
	запись_выбрать(ЗаписьВставить1,Запись2,ЗаписьВставить,ЗаписьНаверх),
% выбранную запись на вставление - вставляем
	запись_вставить(ЗаписьВставить),
	!.
% конец фактов - запомним последний
сортировка(Запись,пусто):-
	запись_вставить(Запись),
	!.

показать_мои_записи:-
	мз(Запись),
	nl,write(Запись),
	откат.
показать_мои_записи:-!.
	
сортировка:-
	сортировка(пусто,Запись),
	запись_вставить(Запись),
	показать_мои_записи,
	!.

В базе знаний "проба.txt" содержатся факты в следующем виде и порядке:

мз(моя_запись(1,"я",23)).
мз(моя_запись(2,"ты",3)).
мз(моя_запись(3,"он",2)).
мз(моя_запись(4,"она",123)).
мз(моя_запись(5,"они",223)).
мз(моя_запись(6,"вы",213)).
мз(моя_запись(7,"кто",23)).
мз(моя_запись(8,"что",20)).
мз(моя_запись(9,"где",13)).
мз(моя_запись(10,"когда",12)).
мз(моя_запись(1,"я",5)).
мз(моя_запись(2,"ты",55)).
мз(моя_запись(3,"он",24)).
мз(моя_запись(4,"она",1)).
мз(моя_запись(5,"они",223)).
мз(моя_запись(6,"вы",33)).
мз(моя_запись(7,"кто",44)).
мз(моя_запись(8,"что",20)).
мз(моя_запись(9,"где",113)).
мз(моя_запись(10,"когда",4)).

Сначала нужно загрузить факты в память с помощью команды:

Goal consult("проба.txt",мои_записи).

После этого можно запускать сортировку фактов:

Goal сортировка. % отсортировать один раз

Надо заметить что сортировка за один раз не расставляет все факты полностью по возрастанию Значения факта: здесь предикат "сортировка" - это лишь одна итерация сортировки. Однако за одну итерацию сразу несколько фактов перемещаются на довольно длинное расстояние в списке фактов. После нескольких выполнений предиката "сортировка" факты будут полностью отсортированы. Дело в том, что чтобы оценить окончание сортировки нужно сделать дополнительный предикат, который бы перезапускал сортировку в случае не полной сортировки фактов.

Вот результаты сортировки входных фактов из файла "проба":

Итерация 1.

моя_запись(4,"она",1)
моя_запись(2,"ты",3)
моя_запись(3,"он",2)
моя_запись(1,"я",23)
моя_запись(4,"она",123)
моя_запись(6,"вы",213)
моя_запись(7,"кто",23)
моя_запись(8,"что",20)
моя_запись(9,"где",13)
моя_запись(10,"когда",12)
моя_запись(1,"я",5)
моя_запись(2,"ты",55)
моя_запись(3,"он",24)
моя_запись(10,"когда",4)
моя_запись(5,"они",223)
моя_запись(6,"вы",33)
моя_запись(7,"кто",44)
моя_запись(8,"что",20)
моя_запись(9,"где",113)
моя_запись(5,"они",223)

Итерация 2.

моя_запись(4,"она",1)
моя_запись(3,"он",2)
моя_запись(2,"ты",3)
моя_запись(10,"когда",4)
моя_запись(1,"я",23)
моя_запись(4,"она",123)
моя_запись(7,"кто",23)
моя_запись(8,"что",20)
моя_запись(9,"где",13)
моя_запись(10,"когда",12)
моя_запись(1,"я",5)
моя_запись(2,"ты",55)
моя_запись(3,"он",24)
моя_запись(8,"что",20)
моя_запись(6,"вы",213)
моя_запись(6,"вы",33)
моя_запись(7,"кто",44)
моя_запись(9,"где",113)
моя_запись(5,"они",223)
моя_запись(5,"они",223)

Итерация 3

моя_запись(4,"она",1)
моя_запись(3,"он",2)
моя_запись(2,"ты",3)
моя_запись(10,"когда",4)
моя_запись(1,"я",5)
моя_запись(1,"я",23)
моя_запись(7,"кто",23)
моя_запись(8,"что",20)
моя_запись(9,"где",13)
моя_запись(10,"когда",12)
моя_запись(8,"что",20)
моя_запись(2,"ты",55)
моя_запись(3,"он",24)
моя_запись(6,"вы",33)
моя_запись(4,"она",123)
моя_запись(7,"кто",44)
моя_запись(9,"где",113)
моя_запись(6,"вы",213)
моя_запись(5,"они",223)
моя_запись(5,"они",223)

Итерация 4 моя_запись(4,"она",1) моя_запись(3,"он",2) моя_запись(2,"ты",3) моя_запись(10,"когда",4) моя_запись(1,"я",5) моя_запись(10,"когда",12) моя_запись(1,"я",23) моя_запись(8,"что",20) моя_запись(9,"где",13) моя_запись(8,"что",20) моя_запись(7,"кто",23) моя_запись(3,"он",24) моя_запись(6,"вы",33) моя_запись(7,"кто",44) моя_запись(2,"ты",55) моя_запись(9,"где",113) моя_запись(4,"она",123) моя_запись(6,"вы",213) моя_запись(5,"они",223) моя_запись(5,"они",223)

Итерация 5

моя_запись(4,"она",1)
моя_запись(3,"он",2)
моя_запись(2,"ты",3)
моя_запись(10,"когда",4)
моя_запись(1,"я",5)
моя_запись(10,"когда",12)
моя_запись(9,"где",13)
моя_запись(8,"что",20)
моя_запись(8,"что",20)
моя_запись(1,"я",23)
моя_запись(7,"кто",23)
моя_запись(3,"он",24)
моя_запись(6,"вы",33)
моя_запись(7,"кто",44)
моя_запись(2,"ты",55)
моя_запись(9,"где",113)
моя_запись(4,"она",123)
моя_запись(6,"вы",213)
моя_запись(5,"они",223)
моя_запись(5,"они",223)

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

А вот более сложный алгоритм. Здесь устранён недостаток, описанный выше. И теперь одинаковые записи сортируются как одна запись: если две записи равны, то они собираются в список и далее путешествуют по сортировке вместе. Если далее встретится еще равная запись, то и она присоединится к списку. Таким образом, сортировка производится за несколько итераций вне зависимости от количества одинаковых фактов.

% пузырьки легкие всплывают, а тяжелые тонут
% а пузырьки одинаковые - цепляются к друг дружке
domains
ИмяЗаписи = string
НомерЗаписи, ЗначениеЗаписи = integer
МояЗапись=моя_запись(НомерЗаписи, ИмяЗаписи, ЗначениеЗаписи);
  мои_записи(МоиЗаписи); пусто
МоиЗаписи = МояЗапись*

database - мои_записи
мз(МояЗапись)

predicates
показать_мои_записи
значение_записи(МояЗапись,ЗначениеЗаписи)
запись_выбрать(МояЗапись З1, МояЗапись З2, МояЗапись Вставить, МояЗапись Наверх)
запись_вставить(МояЗапись)
записи_вставить(МоиЗаписи)
сортировка(МояЗапись Вниз, МояЗапись Вверх) - (i,o)
сортировка
запись_выбрать_вниз(МояЗапись, МояЗапись, МояЗапись Вниз, МояЗапись)
запись_выбрать_вверх(МояЗапись, МояЗапись, МояЗапись, МояЗапись Вверх)
записи_сложить(МояЗапись,МояЗапись,МояЗапись) - (i,i,o)

clauses

% сложить две записи с одинаковым значением
записи_сложить(Запись1,Запись2,мои_записи([Запись1,Запись2])):-	!.
	
% взять значение записи
значение_записи(моя_запись(_,_,Значение),Значение):-!.
значение_записи(мои_записи([Запись|_]),Значение):-значение_записи(Запись,Значение),!.

% выбрать какую запись добавить, а какую передать далее
запись_выбрать(Запись1,Запись2,Запись1,Запись2):-
	значение_записи(Запись1,Значение1),
	значение_записи(Запись2,Значение2),
	Значение1Значение2,
	!.
запись_выбрать(Запись1,Запись2,Запись2,Запись1):-!.

% если записи равны, то их обоих нужно собрать в список и тащить вниз
запись_выбрать_вниз(Запись1,Запись2,ЗаписьВниз,пусто):-
	значение_записи(Запись1,Значение1),
	значение_записи(Запись2,Значение2),
	Значение1=Значение2,
	записи_сложить(Запись1,Запись2,ЗаписьВниз),
	!.
% если не равны, то обычное сравнение
запись_выбрать_вниз(пусто,Запись,Запись,пусто):-!.
запись_выбрать_вниз(Запись,пусто,Запись,пусто):-!.
запись_выбрать_вниз(Запись1,Запись2,ЗаписьВниз,ЗаписьВверх):-
	запись_выбрать(Запись1,Запись2,ЗаписьВниз,ЗаписьВверх),
	!.

% если записи равны, то их обоих нужно собрать в список и тащить вверх
запись_выбрать_вверх(Запись1,Запись2,пусто,ЗаписьВверх):-
	значение_записи(Запись1,Значение1),
	значение_записи(Запись2,Значение2),
	Значение1=Значение2,
	записи_сложить(Запись1,Запись2,ЗаписьВверх),
	!.
% если не равны, то обычное сравнение
запись_выбрать_вверх(Запись,пусто,пусто,Запись):-!.
запись_выбрать_вверх(пусто,Запись,пусто,Запись):-!.
запись_выбрать_вверх(Запись1,Запись2,ЗаписьВниз,ЗаписьВверх):-
	запись_выбрать(Запись1,Запись2,ЗаписьВниз,ЗаписьВверх),
	!.

% вставить список записей
записи_вставить([Запись|Записи]):-
	запись_вставить(Запись),
	записи_вставить(Записи),
	!.
записи_вставить([]):-!.

% вставить запись или список записей
запись_вставить(пусто):-!.
запись_вставить(мои_записи(Записи)):-
	записи_вставить(Записи),
	!.
запись_вставить(Запись):-
	asserta(мз(Запись)),
	!.

% сама сортировка фактов
сортировка(ЗаписьВниз,ЗаписьНаверх):-
% вытащить текущий факт из базы
	retract(мз(Запись1)),
% посмотреть, что далее вниз пойдет
	запись_выбрать_вниз(ЗаписьВниз,Запись1,ЗаписьВниз1,ЗаписьВставить1),
% вызвать рекурсию сортировки (продолжим далее)
	сортировка(ЗаписьВниз1,ЗаписьНаверх1),
% посмотреть, что вернуть наверх, а что положить в базу знаний
	запись_выбрать_вверх(ЗаписьВставить1,ЗаписьНаверх1,ЗаписьВставить,ЗаписьНаверх),
	запись_вставить(ЗаписьВставить),
	!.
% конец фактов - запомним последний
сортировка(Запись,пусто):-
	запись_вставить(Запись),
	!.
% для показа записей на экран
показать_мои_записи:-
	мз(Запись1),
	nl,write(Запись1),
	откат.
показать_мои_записи:-!.
	
% вызов сортировки
сортировка:-
	сортировка(пусто,Запись),
	запись_вставить(Запись),
	показать_мои_записи,
%	повторить,
	!.

вот результаты сортировки:

Итерация 1

Моя_запись(4,"она",1)
моя_запись(2,"ты",3)
моя_запись(3,"он",2)
моя_запись(1,"я",23)
моя_запись(4,"она",123)
моя_запись(6,"вы",213)
моя_запись(7,"кто",23)
моя_запись(8,"что",20)
моя_запись(9,"где",13)
моя_запись(10,"когда",12)
моя_запись(1,"я",5)
моя_запись(2,"ты",55)
моя_запись(3,"он",24)
моя_запись(10,"когда",4)
моя_запись(6,"вы",33)
моя_запись(7,"кто",44)
моя_запись(8,"что",20)
моя_запись(9,"где",113)
моя_запись(5,"они",223)
моя_запись(5,"они",223)

Итерация 2

моя_запись(4,"она",1)
моя_запись(3,"он",2)
моя_запись(2,"ты",3)
моя_запись(10,"когда",4)
моя_запись(1,"я",23)
моя_запись(4,"она",123)
моя_запись(7,"кто",23)
моя_запись(8,"что",20)
моя_запись(9,"где",13)
моя_запись(10,"когда",12)
моя_запись(1,"я",5)
моя_запись(2,"ты",55)
моя_запись(3,"он",24)
моя_запись(8,"что",20)
моя_запись(6,"вы",33)
моя_запись(7,"кто",44)
моя_запись(9,"где",113)
моя_запись(6,"вы",213)
моя_запись(5,"они",223)
моя_запись(5,"они",223)

Итерация 3

моя_запись(4,"она",1)
моя_запись(3,"он",2)
моя_запись(2,"ты",3)
моя_запись(10,"когда",4)
моя_запись(1,"я",5)
моя_запись(1,"я",23)
моя_запись(7,"кто",23)
моя_запись(8,"что",20)
моя_запись(9,"где",13)
моя_запись(10,"когда",12)
моя_запись(8,"что",20)
моя_запись(2,"ты",55)
моя_запись(3,"он",24)
моя_запись(6,"вы",33)
моя_запись(7,"кто",44)
моя_запись(9,"где",113)
моя_запись(4,"она",123)
моя_запись(6,"вы",213)
моя_запись(5,"они",223)
моя_запись(5,"они",223)

Итерация 4

моя_запись(4,"она",1)
моя_запись(3,"он",2)
моя_запись(2,"ты",3)
моя_запись(10,"когда",4)
моя_запись(1,"я",5)
моя_запись(10,"когда",12)
моя_запись(8,"что",20)
моя_запись(9,"где",13)
моя_запись(8,"что",20)
моя_запись(7,"кто",23)
моя_запись(1,"я",23)
моя_запись(3,"он",24)
моя_запись(6,"вы",33)
моя_запись(7,"кто",44)
моя_запись(2,"ты",55)
моя_запись(9,"где",113)
моя_запись(4,"она",123)
моя_запись(6,"вы",213)
моя_запись(5,"они",223)
моя_запись(5,"они",223)

Итерация 5

моя_запись(4,"она",1)
моя_запись(3,"он",2)
моя_запись(2,"ты",3)
моя_запись(10,"когда",4)
моя_запись(1,"я",5)
моя_запись(10,"когда",12)
моя_запись(9,"где",13)
моя_запись(8,"что",20)
моя_запись(8,"что",20)
моя_запись(1,"я",23)
моя_запись(7,"кто",23)
моя_запись(3,"он",24)
моя_запись(6,"вы",33)
моя_запись(7,"кто",44)
моя_запись(2,"ты",55)
моя_запись(9,"где",113)
моя_запись(4,"она",123)
моя_запись(6,"вы",213)
моя_запись(5,"они",223)
моя_запись(5,"они",223)
%

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
Аноним
Мне нравитсяМне не нравится
4 ноября 2005, 19:27:51
Круто!Мне понравилось.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог