Главная arrow Робототехника arrow Сортировка фактов
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Сортировка фактов Печать
Программа на ПРОЛОГе оперирует с базой знаний, состоящей из фактов. Как правило, поиск решения идет с помощью перебора всех возможных фактов. Это может привести к значительным потерям времени. Поэтому, иногда необходимо отсортировать факты так, что бы программа начинала просмотр знаний с наилучшего варианта для ускорения поиска решения. Здесь предложен алгоритм сортировки фактов языка ПРОЛОГ. Алгоритм и его реализация на 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&gtVal1,
               !,
               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