Razgradnja podatkovnih struktur

oseba(ime(Ime,Pri),datum_roj(Dan,Mes,Leto),naslov(Ul,St,Kr)).

Sekvenčni dostop (poudarjena sosednost, imamo vrstni red seznama, ki nam omogoča operaciji "včeraj" in "jutri"

teden([pon,tor,sre,cet,pet,sob,ned])

Razgrajeno na dneve

teden(pon,tor,sre,cet,pet,sob,ned)

Razgrajeno na začetek, sredino, konec

teden(zacetek(pon,tor),sredina(sre,cet),konec(pet,sob,ned))

daj_dan(Dan):-
  teden(T),
  element(Dan,T).

Reševanje s pomočjo razgradnje

Razgradnja nam lahko pomaga dobiti idejo o rešitvi problema.

Primer z damami

Postavi na šahovnico 8 dam tako, da nobena nobene ne napada.

  1 2 3 4 5 6 7 8
1|_|_|_|_|_|_|_|_|
2|_|_|_|_|_|_|_|_|
3|_|_|_|_|_|_|_|_|
4|_|_|_|_|_|_|_|_|
5|_|_|_|_|_|_|_|_|
6|_|_|_|_|_|_|_|_|
7|_|_|_|_|_|_|_|_|
8|_|_|_|_|_|_|_|_|

uporabimo pare indeksov za definicijo vsakega polja (kot koordinate)

[1/1, 3/2, 5/3,...

torej nam indeks lahko že takoj pove če se 2 dami napadata (npr 3/2 in 3/7)

rešitev dobimo z uporabo permutacij števil 1-8

dame([1,2,3,4,5,6,7,8]).

osem_dam_na_sah(Resitev):-
  dame(Dame),
  permutiraj(Dame,Resitev),
  preveri(Resitev).   %preverimo samo diagonalo

preveri([]).
preveri([D|Dame]):-
  preveri(Dame),
  ne_napada(D,Dame,1).

%ne_napada(Dama,Preostale_dame,Razlika_v_vrsticah)
ne_napada(_,[],_).
ne_napada(Stolpec,[Stolpec1|Dame],Razlika):-
  Stolpec1-Stolpec =\= Razlika,
  Stolpec-Stolpec1 =\= Razlika,
  Razlika1 is Razlika + 1,
  ne_napada(Stolpec,Dame,Razlika1).

Ena konfiguracija je:

-----------------
|Q| | | | | | | |
-----------------
| | | | |Q| | | |
-----------------
| | | | | | | |Q|
-----------------
| | | | | |Q| | |
-----------------
| | |Q| | | | | |
-----------------
| | | | | | |Q| |
-----------------
| |Q| | | | | | |
-----------------
| | | |Q| | | | |
-----------------

Primer z barvanjem zemljevida

Omejimo se na barvanje z minimalnim številom barv kjer nobeni sosednji državi nista pobarvani z isto barvo. Dokazano je bilo da so to 4 barve.

najprej predstavimo graf z množico dejstev

%soseda(Država1,Država2).
soseda(slo,h).
soseda(slo,i).
.
.

Rezultat naj vrne v obliki

[D1/B1,D2/B2, ... ,Dn/Bn]

[slo/B1,i/B2,h/B3,...]

Imamo barve

[rde,rum,zel,mod]

Uporabimo algoritem

dobi_seznam(Sez) :-
  setof(Dr/Barva,drzava(Dr),Sez).

drzava(Dr) :-
  soseda(Dr,_);
  soseda(_,Dr).

barvaj(Resitev):-
  dobi_seznam(Resitev),
  barvaj(Resitev,[]).

%drugi argument je seznam obdelanih
%parov sosednjih drzav do sedaj 
barvaj(Dr_barve,Ze) :-
  soseda(Dr1,Dr2),
  not(element(Dr1/Dr2,Ze)),
  element(Dr1/Br1, Dr_barve),
  element(Dr2/Br2, Dr_barve),
  dobi_par_barv(Br1,Br2),
  barvaj(Dr_barve,[Dr1/Dr2|Ze]).
barvaj(_,_). %ni več nepregledanega para

barva(rdeca).
barva(rumena).
barva(modra).
barva(zelena).

dobi_par_barv(Br1,Br2):-
  barva(Br1),
  barva(Br2),
  Br1 \== Br2.