Prolog_facts.shtml
Сортировка фактов ПРОЛОГа
Ермолаев Д.С., Москва
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) %
Вообще, есть классическая сортировка с помощью бинарных деревьев.
Такая сортировка работает быстрее описанного выше метода. Но ее недостаток в том, что она выполняет полную сортировку до полного упорядочивания всех элементов списка. А предложенная мной сортировка делается не полностью, лишь увеличивая вероятность появления нужного факта в начале базы фактов ПРОЛОГа Мною была проведена тестовая оценка классической сортировки и предложенной: Так для количества записей 100 в базе, классическая сортировка делает 800 сравнений, а предложенная в статье (за два прохода): 378. Для 400 записей, соответственно: 11600 и 1500 (за два прохода). Однако если учесть, что время на выполнение одного сравнения в предложенном методе уходит больше и количество проходов при увеличении записей возрастает, выгодность классического метода увеличивается. Вот классический пример сортировки на ПРОЛОГе:
========================= % сортировка с использованием Reference Domains % То есть когда значение предает как ссылка
% файл пример находится в ch11e04.pro к VIP5.5 % и показывает как использовать ссылочные значения % в классической сортировке по методу бинарного дерева
/* Program ch11e05.pro */
DOMAINS
tree = reference t(val, tree, tree) val = integer list = integer*
PREDICATES
insert(integer,tree) instree(list,tree) nondeterm treemembers(integer,tree) sort(list,list)
CLAUSES
insert(Val,t(Val,_,_)):-!. insert(Val,t(Val1,Tree,_)):- Val>Val1, !, insert(Val,Tree).
insert(Val,t(_,_,Tree)):- insert(Val,Tree).
instree([],_). instree([H|T],Tree):- insert(H,Tree), instree(T,Tree).
treemembers(_,T):- free(T), !, fail.
treemembers(X,t(_,L,_)):- treemembers(X,L).
treemembers(X,t(Refstr,_,_)):- X = Refstr.
treemembers(X,t(_,_,R)):- treemembers(X,R).
sort(L,L1):- % рассортировывает элементы списка в бинарное дерево
instree(L,Tree), % преобразовывает бинарное дерево обратно в список
findall(X,treemembers(X,Tree),L1).
GOAL
sort([3,6,1,4,5],L), write("L=",L),nl.
% Здесь значения-ссылки используются только в домайне tree
