Вештачка интелигенција - K28/11/2007 - Задача 1

Задачата која ќе ја разгледаме денеска е следнава. Треба да се напише предикат во PROLOG, transform(L1, L2), кој дадена листа L1 составена од подлисти ќе ја трансформира во листа L2 во која подлистите од влезната листа се подредени според бројот на елементи во опаѓачки редослед. Може да се претпостави дека листата L1 не е празна. Доколку има две подлисти со ист број на елементи, за „поголема“ се смета онаа која има поголем прв елемент. Доколку и првите елементи им се еднакви, се споредуваат вторите елементи, и.т.н., додека не се најде барем еден елемент во една од подлистите кој е поголем од елементот на соодветната позиција во втората подлиста. Доколку двeте подлисти се идентични, тогаш едната се отстранува од резултатот. Може да се претпостави дека нема повеќе од две подлисти со ист број елементи. 

Пример

---

transform([[3,10], [2,4,6,33,1,8], [4,1,6,3], [3], [2,4,6,33,1,8], [7,12], [4,1,2,7], [6,7,9]], L).

L= [[2,4,6,33,1,8],[4,1,3,6],[4,1,2,7],[6,7,9],[7,12],[3,10],[3]].

Решение

---

 

Најпрво ќе разгледаме предикат за сортирање на обична листа со цели броеви во растечки редослед, а потоа ќе го прилагодиме истиот тој предикат да го решава нашиот проблем. Станува збор за PROLOG - варијанта на quicksort алгоритмот кој поради својата рекурзивна природа се изразува на многу едноставен начин во PROLOG. 

Пред quicksort предикатот, ќе разгледаме еден помошен предикат partition.

partition(_, [], [], []) :- !.
partition(X, [Y|L], [Y|A], B) :- Y=<X, partition(X, L, A, B).
partition(X, [Y|L], A, [Y|B]) :- Y>X, partition(X, L, A, B).

partition(X, L, A, B) предикатот прима четири аргументи и неговата цел е елементите од листата L да ги подели во две дисјунктни листи (А и В) во однос на елементот X. Во листата А треба да се стават сите елементи од L кои се помали или еднакви на X, а во листата В сите елементи од L кои се поголеми од Х. 

?- partition(3, [1,5,4,3,7], A, B).

A = [1,3],

B = [5,4,7].

Влезните аргументи на partition предикатот се првите два: елементот X во однос на кој ќе се врши поделбата и листата L која треба да се подели. Излезните аргументи се последните два - листите А и В.
Кога ќе дојдеме до празна листа, враќаме како резултат празни листи. Ако тековниот елемент кој го разгледуваме, Y, е помал или еднаков на елементот Х, тогаш го додаваме во листата А. Во спротивно, ако е поголем од Х, го додаваме во листата В.

Бидејќи горново решение за поделба на листата L можеби не е најинтуитивното, предлагам уште еден начин на кој може да се изврши поделбата. Имено, со следниве два искази целосно се одредени А и В:

1. z е елемент на А ако z е елемент на L и z =< X.

2. z е елемент на B ако z е елемент на L и z > X .

кои преточени во  PROLOG наредби изгледаат:

 partition(X, L, A, B) :-
    findall(Z, (member(Z,L), Z=<X), A),
    findall(Z, (member(Z,L), Z>X), B).

"Најди ги сите елементи Z кои се во L и се помали или еднакви на Х и смести ги во А. Потоа, најди ги сите елементи Z кои се во L и се поголеми од Х и смести ги во В."

Да забележам дека елементите во листите A и B не се сортирани. partition не сортира, туку само врши поделба.

Сега да го разгледаме предикатот quicksort.

quicksort([], []) :- !.
quicksort([X|Xs], R) :-
    partition(X, Xs, Left, Right),
    quicksort(Left, LeftSorted),
    quicksort(Right, RightSorted),
    append(LeftSorted, [X|RightSorted], R).

quicksort прима два аргумента. Првиот е влезен аргумент и е листа која треба да се сортира (L=[X|Xs]), а вториот е излезен и е всушност истата листа, но сортирана (R). Од влезната листа [X|Xs] се зема првиот елемент Х и во однос на него се врши поделба на остатокот од листата, Xs, на две листи: Left и Right користејќи го предикатот partition. 

Во Left се наоѓаат сите елементи на Xs кои се помали или еднакви на Х, а во Right сите елементи на Xs кои се поголеми од Х. Бидејќи сите елемети од Xs ги реорганизиравме во две нови листи, самата листа Xs нема повеќе да ни е потребна.

Следно што правиме е повикуваме сортирање на Left и Right при што се добиваат сортираните LeftSorted и RightSorted. Резултатот, сортираната листа R, e конкатенација од обликот [LeftSorted | X | RightSorted]. 

Граничниот случај е кога ќе се дојде до празна листа. Тогаш едноставно се враќа празна листа и се отсекува повикувањето на второто quicksort правило.

Да се навратиме сега на нашиот проблем. Потребно е да сортираме листа од листи, а не листа од цели броеви. Она што ќе треба да го промениме е начинот на кој се одредува дали еден елемент е помал од друг. Погоре, тоа го правевме во partition предикатот со наредбите Y=<X, Y>X. Сега, овие две наредби ќе ги замениме со нов предикат pomala(Y,X) кој ќе враќа true доколку листата Y е "помала" од листата Х, или false во спротивно, слично како што "Y=<X" враќа true доколку Y е помал или еднаков на X, односно false во спротивно.
Имено,

pomala(Y,X) :- length(Y, Yn), length(X, Xn), Yn < Xn.

pomala(Y,X) :- length(Y, Yn), length(X, Xn), Yn = Xn, sporedi(Y,X).

sporedi([], []) :- !.
sporedi([A|_], [B|_]) :- A<B.
sporedi([A|Y], [B|X]) :- A=B, sporedi(Y,X).

Листата Y e "помала" од листата Х ако должината на Y (Yn) e помала од должината на Х (Xn). Дополнително, листата Y е помала од листата Х ако должините им се еднакви (Yn=Xn), но првиот елемент по кој Y и Х се разликуваат е помал кај Y.

Последниов случај го решава предикатот sporedi коj споредува две листи со еднаква должина. sporedi ќе се повика само во случај ако X и Y листите имаат иста должина за да ја реши дилемата која од нив две е помала. Со sporedi, елементите на листите се разгледуваат еден по еден. Ако се наиде на елемент во Y што е помал од елементот во X на иста позиција, тогаш Y e навистина "помала". sporedi предикатот ќе врати true, а со тоа и pomala ќе врати true. 

Да забележам дека sporedi ќе успее (ќе врати true) дури и ако листите X и Y се идентични по состав, односно ако се дојде до случајот sporedi([], []) што значи дека сме ги изминале сите елементи од Х и Y и сите биле еднакви меѓу себе. 

Тоа значи дека доколку листите Y и X се идентични, pomala(Y,X) ќе успее. Идентичните листи ќе ги отстраниме на крајот, по сортирањето.

Дополнително, се бара сортирањето да е во опаѓачки редослед, што значи дека треба да ја смениме логиката при partition. Во "левата" листа да одат поголемите, а во "десната" помалите. Модифицираниот partition предикат ќе изгледа вака:

 partition(X, L, A, B) :-
    findall(Z, (member(Z,L), not(pomala(Z,X))), A),
    findall(Z, (member(Z,L), pomala(Z,X)), B).

Со овој partition предикат, листите во листата L се распоредуваат во листите A и B, во зависност од тоа дали се помали или поголеми од листата X, со тоа што поголемите се сместуваат во А, а помалите во В. 

На крајот само ќе треба да ги отстраниме дупликат листите. Тоа може да го направиме со otstrani_duplikati предикатот. 

Конечната програма изгледа вака:

transform(L1, L2) :- quicksort(L1, Lp), otstrani_duplikati(Lp, L2).

quicksort([], []) :- !.
quicksort([X|Xs], R) :-
    partition(X, Xs, Left, Right),
    quicksort(Left, LeftSorted),
    quicksort(Right, RightSorted),
    append(LeftSorted, [X|RightSorted], R).

partition(X, L, A, B) :-
    findall(Z, (member(Z,L), not(pomala(Z,X))), A),
    findall(Z, (member(Z,L), pomala(Z,X)), B).

pomala(Y,X) :- length(Y, Yn), length(X, Xn), Yn < Xn.

pomala(Y,X) :- length(Y, Yn), length(X, Xn), Yn = Xn, sporedi(Y,X).

sporedi([], []) :- !.
sporedi([A|_], [B|_]) :- A<B.
sporedi([A|Y], [B|X]) :- A=B, sporedi(Y,X).

otstrani_duplikati([], []).

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

otstrani_duplikati([X|A], [X|B]) :- 
    not(member(X,A)),
    otstrani_duplikati(A,B).


PL  http://www.mediafire.com/?0s5kwbsl8aykxs7



VeIn PROLOG пролог veshtachka inteligencija вештачка интелигенција листи сортирање quicksort quick sort