INTRODUCCIÓ A LA INTEL.LIGÈNCIA ARTIFICAL

TEMA 1: INTRODUCCIÓ A LA IA

TEMA 1: INTRODUCCIÓ A LA IA

Definició de la IA

# Segons en Robert Schank la IA te dos objectius:

• Construir una màquina intel-ligent

• Investigar la naturalesa de la intel-ligència.

En Schank dóna cinc característiques:

• Comunicació, es a dir, si no hi ha comunicació vol dir que no hi ha intel-ligència.

• Coneixement intern.

• Coneixement sobre el món.

• Objectius i plans.

• Creativitat.

# En Luc Steels la defineix com “el camp científic dedicat a comprendre el fenònem de la intel-ligència”, usant la definició d'Allen Newell que caracteritza la intel-ligència en els següents termes:

• Comportament flexible en funció de l'entorn.

• Exhibir comportament adaptatiu, racional, orientat a objectius.

• Operar en temps real.

• Operar en un entorn molt ric, complex i detallat. Percebre la gran quantitat de canvis de l'entorn, utilitzar grans quantitats de coneixement i controlar un sistema motor de molts graus de llibertat.

• Utilitzar símbols i abstraccions.

• Utilitzar llenguatge, naturals i artificials.

• Aprendre de l'entorn.

• Adquirir capacitats a través del desenvolupament.

• Viure autònament dins d'una comunitat.

• Mostrar consciència de sí mateix.

# En Patrick Winston diu que la IA és l'estudi dels càlculs que fan possible percebre, raonar i actuar.

# L'Elaine Rich la defineix com l'estudi de com fer que els orinadors facin coses que, per ara, les persones fan millor.

# En el llibre d'Edicions UPC es defineix la IA com l'intent de:

Com avaluar el comportament intel-ligent d'un programa?

Al 1950 Allan Turing va proposar un test que consistia en que una persona (observador) fa unes preguntes i li responen una altra persona i una màquina en habitacions diferents, i l'observador ha decidir en quina habitació es troba la persona. La màquina intenta fer-se passar per la persona i aquesta passa el test quan ha aconseguit enganyar un nombre considerable de vegades al/s observador/s. Aquest test només es basa en el comportament verbal, es a dir, només en la comunicació.

Arees d'aplicació de la IA

Tasques d'interació amb el món (nen).

• Percepció (Visió i Parla).

• Llenguatge natural (comprensió, Generació i Traducció).

• Raonament de sentit comú.

• Moviment (navigation, robots).

Tasques formals (a l'escola).

• Jocs (escacs, backgammon, go, trencaclosques).

• Matemàtiques (geometria, lògica, Integració simbòlica, derivació automàtica de programes).

Tasques d'expert (a la Facultat)

• Engnyeria (disseny, detecció de falles).

• Diagnòstic mèdic.

• Anàlisi financera.

• Anàlisi científica.

Historia de la IA

Gestació:

1820 Màquina de Babbage

1920 Màquina de Torres Quevedo

1945 Maquina de Von Neumann (ENIAC)

1948 Principios de Cibernètica (Vienner)

1950 Ideas de Shanon sobre automatització d'escacs.

Naixement i infancia (fins 1968):

· Cerca en espais d'estats.

· Generació i proba.

· Cerca heurística

• Programar per jugar a les dames.

1956 Conferencia de Dartmoth, euforia incial amb promeses exagerades (en 10 anys, campió mundial d'escacs), sobreestimació capacitat de cerca.

1957 Programar per jugar a escacs.

1958 General Problem Solver.

1960 Principi de resolució.

1963 Resolució d'integrals.

1965 Primers projectes de Robótica. Anys dificils: desacredit per les promese incumpleses. La conclusió es que la cerca sola és impracticable, i hi ha una necesitat de coneixement. S'abandonen les xarxes neuronals, tras Minsky i Papert.

Desenvolupament (fins 1977):

· Xarxes semàtiques.

· Regles

· Formalismes lògics.

· Sistemes de producció.

· Frames

· planificació.

1968 Dendral: síntesi d'estructures moleculars. Macsyma: càlcul simbólic.

1970 Scholar. J. Carbonell.

1972 Planner, Hewitt.

1973 Primers ptototipus de SE.

173 Mycin, Shortliffe, Buchanan, Clancey.

1974 Sophie, Brown, Burton

1975 Frames: Minsky.

1976 Teiresias, Davis.

Reconeixement extern (fins 1980):

1977 KRL, Bobrow, winograd

1978 Prospector, Duda

1980 Xsel, Xcon, McDermott. Papel del coneixement, multiplicitat de representacions,.

Representació del coneixement: tema estrella de la IA.

Popularització dels sistemes experts.

Necesitat de l'aprenentatge automàtic.

Xarxes neuronals: reanudació tras Hopfield.

Robótica i agents autónoms.

1981 Emycin, Van Melles, Shortliffe, Buchanan.

1982 Reactor, Nelson.

Tècniques d'IA

Ja hem vist la primera tècnica que va ser la de Turing, despres va apareixer ELIZA, que el va crear Weizembaum que vol simular el tipus de conversa que es te quan es parla amb un psicoanalista.

• Eliza és el mateix que el test de Turing? En Turing l'observador sap que una de les respostes és d'una màquina, enc anvi amb Eliza és la propia màquina.

• Tenim el problema de reconeixement del llenguatge natural: es a dir, que tenim un text i fem preguntes i obtenim unes respostes, si el sistema dona respostes despres de tenir el text, vol dir que ha comprés el text i per tant que te una certa intel-ligència.

• També tenim el Pattern matching: que conisteix en que tenim una frase i es fa una pregunta sobre aquesta frase.

Pere ha comprat un llibre vermell.

Que ha comprat Pere? un llibre vermell

Per cada patro tenim una resposta i si hi ha algun cas en que no te patro, llavors escogeix respostes a l''tzar. Aquest sistema és en el que es basa ELIZA.

• T.L.N: tractament del llenguatge natural, per solucionar el tractament de llenguatge natural tenim:

• Gramàtiques

• Lexicons (diccionaris)

Frase 1: acció: compra Individu 3: objecte 5:

Temps: passat instancia persona instancia llibre

Agent: individu 3 nom: Pere color: vermell

Objecte: objecte 5

Amb aquest metode s'afegeix un coneixement abstracte

Encara ens caldria afegir mes coneixement de sentit comú i això s'aconsegueix amb els scripts.

TEMA 2: REPRESENTACIÓ DEL CONEIXEMENT

Introducció

Per representar el coneixement necessitem dels esquemes de representació, els cuals estan compostos per:

• Estructures de dades.

• I procediments o funcions.

Normalment del coneixement parlarem de dos entitats:

• Mon o domini del problema.

• Representació del mon.

Aquestes dues entitats han d'estar molt relacionades, ja que volem la millor representació possible que puguem obtenr del món. La representació es pot fer per tant amb un o més esquemes. Aquesta representació sempre serà incompleta, ja que sino seriem en el mon del problema.

El coneixement te unes característiques que el fan irrepresentable totalment:

• En molts cassos la informció es voluminosa.

• Hi ha moltes modificacions.

• El coneixement es complex .

Per tant hem de buscar les parts rellevants del món.

Els sistemes basats en el coneixement són els sistemes que es basen en una representació del coneixement per resoldre els problemes que li poguin apareixer. Les característiques d'aquests sistemes, serien basicament:

• Adequació de la representació: l'esquema de representació ha de ser suficient per representar el problema i poder resoldre'l.

• Adequació de la inferència: a partir de coneixements es voldria obtenir altres coneixements (cas de la lògica, en concret les premises).

• Eficiència en la inferència: si la resposta triga molt en donar-se pot ser que en alguns sistemes ja sigui massa tard per aplicar-la, perque s'havia d'haver fet abans.

• Eficiència/comoditat en l'adquisició: que els mecanismes dels sistemes per representar el coneixement s'assemblin més als mecanismes que utitza l'expert per representar la informació.

Tipus de coneixement

Els diferents tipus de coneixement que podem represnetar són:

• Coneixement relacional simple: aquest es compon per les taules que contenen els registres d'una base de dades.

• Heretable/ taxonòmic: tenim una representació de conceptes a varis nivells.

Permeten repartir la informació als diferents nivells. I cambiant la informació d'un d'aquests nivells quedan actualitzats tots els nivells per sota sense haver de ser modificats aquests.

Com podem veure, aquest coneixement es compon de conjunts i d'elements, aquests últims són les entitats reals, i els conjunts conjunts d'aquestes entitats reals.

Existeixen dos tipus de crelacions:

· ES-UN (inclusió ").

· INSTANCIA DE (pertany ").

• Coneixement inferible: tipus particular del coneixement procedimental.

Home (Socrates)

"x: home (x) ! mortal (x)

• Coneixement procedimental: és el coneixement de com calcular els valors, es adir, te una funció de càlcul relacionada. Per exemple: l'edat va cambiant en funció de la data de naixement i per tant s'ha d'anar calculant. Per tant l'edat no es consideraría un atribut sino com una funció que pren la data actual i la data de naixement i dona l'edat.

Exemple: Relacions de familia.

Maria és cosina de l'Anna

Cosina s'ha de traduir als sis termes que tenim, unes possibles traduccions són:

Tenim quatre representacions i a partir de cada cas obtenim un resultat diferent. Una solució es agrupar els termes primitius i així obtenim una únca representació

Respas de lógica de predicats

• 1.-Formalització dels predicats.

• 2.-Manipulació, en concret posar els predicats en forma claussular.

• 3.-Resolució.

Problema 1

• A John, le gusta todo tipo de comida.

• 1.-"x: (comida (x) ! gusta (John, x))

• 2.-¬ comida (x) " gusta (John, x) _1

• Las manzanas son comida.

• 1.-comida (manzanas) ! "x: (manzana(x) ! comida(x))

• 2.-comida (manzanas)_2

• El pollo es comida.

• 1.-comida (pollo)

• 2.-comida (pollo)_3

• Cualquier cosa que alguien come y no muere es comida.

• 1.-"x: ("y: come (y, x) " ¬muere (y)) ! comida (x)

• 2.-"x: ("y: come (y, x) " ¬muere (y)) ! comida (x)

" "x: (¬("y: come (y, x) " ¬muere (y)) " comida (x))

" "x: ("y: ¬come (y, x) " muere (y)) " comida (x))

" "x "y: (¬come (y, x) " muere (y) " comida (x))

¬come (y, x) " muere (y) " comida (x)_4

• Bill come cacahuetes y no ha muerto.

• 1.-come (Bill, cacahuetes) " ¬muere (Bill)

• 2.-come (Bill, cacahuetes)_5

¬muere(Bill)_6

• Sue come todo lo que Bill come.

• 1.- "x: (come (Bill, x) ! come (sue, x))

• 2.- ¬come (Bill, x) " come (Sue, x)_7

Resolució: premisas U {¬C} " ð on C és la conclusió. La regla de la resolució és la següent:

Demostrar que:

C = gusta (John, cacahuetes)

¬gusta (John, cacahuetes) 1

x/cacahuetes

¬comida(cacahuetes) 4

x/cacahuetes

¬come (y, cacahuetes) " muere(y) 6

y/Bill

¬come (Bill, cachueste) 5

ð

Amb la resolució també es poden respondre les preguntes que demanen de donar algun nom, i no només a preguntes requereixen d'una resposta afirmativa o negativa.

Sistemes de regles de producció

Els sistemes de producció són semblants a les representacions lògiques, però no són iguals.

La representació lògica és el que s'anomena representació declarativa, que vol dir, que en el coneixement que representa estan definits els objecetes però en canvi no esta definit com es manipulen els objectes:

Els sistemes de regles són una representació procedimental, a més de definir els objectes, també explica el tipus d'execució que es pot fer sobre el coneixement. Es tracta la reprresentació lògica com un programa.

Exemple:

En els sistemes de produccions tenim dos components:

• Fets: els fets són afirmacions i en cap moment tindrem negacions.

• Implicacions

A ! B A	Modus ponens “cap endavant”
B

No podem utilitzar el modus ponens cap enrera, pero si podem fer una lectura cap enrera.

A ! B ; per obtenir unaB hem d'obtenir una A

A ! B Objectiu B	Modus ponens “cap enrera”
Objectiu A

Modus ponens cap endavant

Els tipus de coses que necessitem pel modus ponens cap endavant:

• Fets: s'agrupen en base de fets, tots afirmacions

• Regles: base de regles

• Mecanisme de control, s'aparellen en due parts:

· Mecanisme d'inferència: varia tot el conjunt del modus ponens possibles cap endavant que podria fer. Si no troba cap MP el sistema s'atura. Si hi ha diverses posibilitats necessitarem un mecanisme per escollir-ne alguna. Crea el conjut de conflictes (aplicacions que hi ha)

· Mecanisme de resolució de conflicte: escolleix el MP que farà servir entre tots els possibles.

Cap endavant les regles s'assemblen a l'estructura condicional

Les condicions i accions s'evaluen sobre les variables o contingut de la memoria.

En aquest sistema s'evaluen sobre la base de fets (BF) i es modifica l'anomenada base de fets.

A ! B A avalua cert segons la BF		A ! B " Base de regles (BR) A " BF
Executar B		Afegir B a la BF

A " B ! C i A " B ! C no passa res pero el següent cas te un tractament dierents:

¬ A ! B no pot passar i per tant no s'accepta

Però amb la hipotesi del mon tancat si s'acceptaria. La hipotesi del món tancat diu que durant el funcionament del sistema podem fer l'hipotesi de que tota afirmació estarà a la BF.

¬ A ! B A " BF	En cada moment A es cert o fals però no pot ser cert i fals en el mateix moment.
B

Tenim el criteri de refracció que diu que en el conjunt de conflictes no es consideren activacions que ja s'han fet.

Modus ponens cap enrera

En aquest tipus de sistema de producció també necessitem el descrit a l'apartat anterior (MP cap endavant) però amés necesitem la llista d'objectius a assolir.

• Fets: base de fets

• Regles: base de regles

• Llista d'objectius a assolir.

• Mecanismes de control

En aquest cas l'execució s'atura quan no tenim cap objectiu més que assolir.

A Objectiu A, B, C

Objectiu B, C

En aquest cas tenim unes restricions sintactiques:

• A ! B, on B només pot ser un “fet” afirmat.

• No podem tenir coses com: A ! B " C, però en canvi podem fer coses d'aquest estil:

A ! B A ! C

• No podem tenir coses com: A ! B " C, tenim com objectiu, però no podem afirmar que al tenir A tindrem B ja que podriem tenir C.

A " B " C ! D			A ! C B ! C
Objectiu D		A " B ! C
Objectiu A, B, C

¬ A ! B Objectiu B	Els objectius són de la bae de fets o a la part dreta i per tant es pot prohibir aquesta situació o tratar-lo de forma diferent. Aquesta forma és lasegüent:
Objectiu ¬ A

Negació per fallida:

Objectiu ¬ A pero plantegem Objectiu A, en aquest cas podem succeir dues coses:

• que aconseguim validar aquest predicat, i per tant voldrà dir que hem fracasat al obtenir ¬ A.

• O que no ho aconseguim demostrar, i per tant voldrà dir que hem aconseguit l'objectiu ¬A.

Ca enrera manifesten l'actiu canviant els objectius i no els fets com fa el sistema cap endavant. En cap enrera el mecanisme de resolució de conflictes pot fer backhacking, es a dir, que pot replantejar-se decissions no presses abans.

Representacions estructurades

Xarxes semantiques

Les xarxes semàntiques són sistemes de representació declaratiu encara que hi han xarxes amb coneixement procedimental.

La idea de les xarxes semàntiques es semblant a un diccionari. Quillian volia representar el significatde les paraules i es d'on surt l'idea de diccionari.

Una xarxa equival a un graf etiquetat amb els nodes i arcs. Els concpetes són als nodes i la definició són les diverses connexions amb els altres nodes.

Hi ha autors que a les xarxes semàntiques les anomenen xarxes associatives.

Els node represneten:

• Conceptes

• Individus: objectes concrets del nostre domini.

• Accions

• Valors de propietats dels individus.

Els arcs representen relacions (la relació que hi ha entre indivuds i conceptes) atributs, etc.

Exemple:

· Canari: ocell que canta i de color groc.

· Ocell: animal vertebrat, amb ales i que pot volar.

Les relacions poden ser de dos tipus: " es_un i " instcnia de.

En principi nomes es poden expresar relacions bnaries amb les xarxes semàtiques, però una relació de qualsevol cardinalitat es pot expressar en funció de relacions binaries.

Una relació binaria te l'esquema següent:

Exemple de transformació d'una relció qualevol a una relació binaria: resultat (equiplocal, equipVis, golsl, golsev)

El sou de Joan es de 100000 ptas

El sou de Joan es més gran que el de Pere.

En el primer exemple tenim n valor concret (100000) i a l'altre no (sou-j). El node de 10000 ptes pot existir sense la resta de la xarxa peque 100000 sempre seran 100000 els cobri o no, en Joan. En canvi el node sou-j depen de la xarxa. Per tant depenent de la epresentació tindrem nodes que els haurem de tenir sempre i noes objectius que poden existir en una altra xarxa.

Mecanismes d'inferencia de les xarxes semàntiques

Pàgina 6 de les transparencies.

A la figura 3 s'organitzen els concpetes de forma jerarquica (forma d'arbre) on cada nivel de l'arbre es caracteritza pel grau d'especificació. Hi ha dos tipus de relacions:

• Taxonòmiques: instancia_de. És una connexió entre els diferents conceptes.

• Particulars: defineixen els atributs dels conceptes.

Els concpetes inferiors hereten els atributs dels conceptes superiors a ells.

A la figura 5 tenim la represnetació d'un arc. Un arc te tres blocs:

A la figura 7 es vol simular una frase en una xarxa semàtica. El verb és el centre de la xarxa i està unit a tots els objectes de la frase. Seria com analitzar les frases (distingir subjecte, verb, objecte directe, objecte indirecte, etc.)

A la figura 8 tenim els grafs de dependencia concpetual. La frase es redueix a elements atomics, seria el llenguatge assembler de les frases.

A la figura 1 (pàgina 7) es vol intentar representar predicats en lògica. Les operacions (", ", ¬) necessitaran altres nodes que apuntin a les accions que afecten.

A la figua 7.7 (pàgina 8) es vol definir subparts de les xarxes. Això permet treballar amb quantificadors.

Sistemes de frames

Les etiquetes de les xarxes semàntiques són objectes no estructurats.

Els frames són xarxes semàtiques sobre objectes estructurats (tuples, registres...). És la definició d'un objecte estructurat on cada objecte estructurat es basa en una sèrire d'slots.

Un slot és un objecte estructurat en base a una serie de facets.

Un facet és un objecte amb “valor” que s'anomena fillers.

Les estructures no estan aïllades, estan relacionades. hi ha dos tipus de relacions:

• Taxonòmiques: relacions es_un (inclusió) i instancia_de (pertinença). Permeten el raonament per herencia.

• Usuari: s'han de definir i les definicions són estructurades.

Podem trobar un exemple a la pàgina 5 de les transparencies.

L'herencia no és copia sino consulta. EL frame consulta a un frame superir però la característica no és copia al frame consultor, sino que es manté al frame superior i només es pot consultar

La descripció de frames, slots i relacions es troba a les pagines següents:

Fotocopia 1

Descripció de les relacions, frames, i slots.

Fotocopia 2

Un demon es un una funció que s'activa sense cridar-les. Te condicions d'activacions sobre el valor associat a un slot. Sobre un valor podem preguntar, per un frame i slot concret, quin valor te. Si te definit el valor el retorna, si no el té definit i el demon esta en if_needed llavors s'executa una funció per calcular quin valor hauria de tenir. Si el demon està a if_added s'executaria aun assignem un valor a un slot concret. I si fos if_remove s'executaria la funció quan esborresim un valor.

L'herencia indica si l'slot es pot heretar o no. Les definicions d'herencia es defineixen en dos parts: per les taxonòmiques i per les relacions d'usuari.

Existeixen diferents tipus de slots en funció de l'herencia, aquests tipus de slots són:

• Slots membres: slots que s'apliquen a les instancies de les classes.

• Slots propis: són els que no interessa que s'heretin.

Les relacions definides per l'usuari sempre estan definides entre les instancies.

Herència

L'herència consisteix en trobar valors en d'altres frames quan el frame sobre el qual es fa la consulta no té cap valor (per l'slot). L'herència no es còpia sino que només es pot consultar.

Per trobar els valors a travès de l'herència tenim unes prioritats: primer es busca el facet valor i si no es troba es buscaria en el facet demon. Aquesta prioritat descrita és la prioritat dins del frame.

Les diferents formes de poder combinar les prioritats dintre la jeràrquia i les prioritats dintre del frame ens dona dos tipus d'herència:

Aquest dos ordres de cerca d'un valor en l'herència només es pot utilitzar en relacions d'usuaris si aquestes són transitives.

Que passa quan hi ha diferents camins per anar per l'herència? (herència multiple)

Eli.vola=NO

Ara hi ha dos possibles camins d'herència. Per solucionar el problema no hi ha criteris generals per solucionar l'herència multiple.

Un criteri podria ser escolir el camí de longitud més curta:

Aquest camí te longitud 1

Aquest camí te longitud 2

Però el primer camí podria tenir una lonmgitud més gran que el segon i el resultat seria incorrecte. I si els dos camins tinguessin la mateixa longitud encara no sabriem quin escollir.

El que no seria lògic seria triar el camí vermell ja que pel camí blau anem a un frame que està per sota del frame al que arribem pel camí vermell. No és lògic utilitzar els casos generals per definir casos excepcionals que defineix ja el valor que volem pel nostre frame.

Aquest és el criteri de la distancia inferencial:

• 1 pas: fer el conjunt dels frames des dels quals podem arribar a un valor *.

• 2 pas: filtre, el.liminar del conjunt els frames tals que en el conjunt hi ha un altre frame tal que podria heretar el valor deinit en el primer frame. Conjunt verd discontinu.

• 3 pas: Si la cardinalitat de l'slot és N llavors no hi ha cap problema. En canvi si la cardinalitat de l'slot es 1 tenim dos casos. Primer cas si la cardinalitat del conjunt es 1 llavors tot està correcte, però en canvi, el segon cas, si la cardinalitat del conjunt és més gran que 1 llavors el criteri no decideix.

Un altre criteri seria que si ens pot arribar un valor per un camí despreciem els altres camins.

Els scripts

Els scripts pretenn solucionar el problema del coneixement del sentit comú. Són un sistema de frames especialitzats per respondre al sentit comú.

A la pagina 12 de les transparencies trobem un exemple d'script

Anàlisi comparatiu de les representacions

Càlcul de predicats (CP)	Sintctics
Sistemes de producció (SP)
Xarxes semàntiques (XS)		Orientats a la semàntica
Frames (F)
Scripts (S)

	CP	SP	XS/F
Adequació expressiva	No hi ha valors per defecte.	Manca d'estructures Negociaó per fallada	Dificil representar lleis generals (negació?)
Adequació inferencial	Principi de resolució	Modus Ponens	Herència (taxonomica)
Eficiència inferencial	Pobre	Ús de meta-regles	Procediments
Eficiència en l'adquisició	Pobre	Regular	Bé
	Lleis generals	Coneixement heurístic	Coneixement taxonòmic

La inferència

TEMA 3: RESOLUCIÓ DE PROBLEMES

Introducció

La cerca sobre un espai d'estats es un bon metode per fer inferència sobre problemes (resolució de problemes).

La metodologia que seguirem serà:

• Formular el problema.

• Determnar la insrtancia de l'esquema de cerca òptim.

• Implementar.

La IA vol dissenyar engings informàtics amb un comportament intel-ligent en un entorn complexe. El disseny d'engings infomàtics equival a dissenyar un programa. I el comportament intel.ligent equival a:

• Fixar un objectiu

• Més assolir l'objectiu: aquest objectiu es pot assolir de forma reactica (sensors, reacció a cada configuració -estat- percebuda de l'entorn) o de amb una certa planificació.

Amb la planificació tenim un objectiu, la situació actual, el pla que seguirem (seqüències d'accions, precondcions, efectes ...) i una funció de cost (associada a cada acció).

Per exemple un robot podria anar directament provant fins a arribar al lloc desitjat o ve primer mirar per on podria anar i despres començar el viatge.

Exemple: tenim dues gerres una de 3 litres i una altre de 5 litres i volem obtenir 4 litres exactes.

Això es el que s'anomea Espai d'estats.

Els components d'un problema són:

• Estat. Configuració possible de l'entorn en el que em trobo resolent el problema.

En l'exemple: Estat = <xp, xg> on xp" {0,1,2,3} i xg"{0..5}

• Espai d'estats: conjunt de tots els estats per un problema

• Condició d'objectiu: xg=4

• Estat inicial : <0,0>

• Operadors: estat ! estat. Per cada operaxdor tindrem les precondicions i els efectes.

Per exemple: prec: xp<3 efecte: xp=3

• Funció de cost: estat * operador ! R

• Solució: que es compon d'un estat objectiu, una seqüència d'operadors de l'estat inicial a l'estat objectiu, de tots els estats objectius i totes les seqüències. En els dos primers casos poden obtenir la solució optima (per això haurem de disposar d'una mena de funció de cost).

Formulació

Exemple: problema de les 8 reines

Podem codificar el problema amb:

• Una taula de [8,8] de booleans.

• [<, >, <, >, ...., <, >]

x1 y1 x2 y2 x8 y8

Ens quedem amb la segona formulaci´:

Els elemnts bàsics que intervindran en el disseny d'esquemes algorísmics:

• Un estat és un conjunt de parells.

• Condició d'objectiu: "i, j: i"j: xi"xj " yi"yj " |yi-yj|"0 ""i: xi, yi " {1,...8}

• Estat inicial {<?,?>, <?,?>, ....}

• Operadors: col.locar reina (l, i, j)

Pre "k (xk,yk)" (?,?), xk"i yk"i; |xk-i|"|yk-j|

Efecte xl=i, yl=j.

• Solució: un estat objectiu

Cerca no informada

Els components d'un algorisme de cerca són:

• Comprovar l'objectiu. Funció es_estat_objectiu: estat ! booleà.

• Generar_successors: estat ! {estati} tal que són estats pels quals eisteix un operador tal que la precondició és satisfeta per l'estat anterior.

• Estrategia de cerca: selecciona_estat: {estat} x estratregia ! estat

• Solució: d'estat a un estat o a un camí (estat inicial, estat).

Esquema comú dels algorismes de cerca

• Associar a l'estat inicial un node incial.

• Aplicar al node inicial tots els operadors posibles (expandir elnode).

• Associar a tots els fills generats un punter al pare.

• Comprovar si algun dels fills és un nde terminal.

• Si no hem trobat un node terminal, un cop tractats els fills repetits, integrar els fills generats a la llista de pendents (ordre segons estratègia de cerca).

• Seleccionar un nou node a ser expandit i repetir 3, 4, 5, 6

• Si arribem a un node terminal final, s retorna al node inicial a través del punters i així obtenim el camí solució (seqüència d'operadors).

• Si es compleixen les condicions de control d'acabament i no hem arribat a un node terminal final, s'atura el procès sense solució. Les condicions d'acabament poden ser: la no generació de nodes nous al fer l'expansió de nodes i per tant s'arriba a tenir la llista de nodes pendents d'explorar buida, o l'arribada a una profunditat màxima, o l'ús del temps màxim de CPU inicialment previts, o...

Funció cerca_general (problema, estratègia) retorna solució o buit

Inicialitzar (problema, estat_inicial)

Bucle

Si generar_successors (problema, actual)=" llavors retorna buit

Sino estat_actual ! selecciona_estat (genera_successors (problema.actual, estrategia)

Si es_estat_objectiu (estat_actual) llavors retorna solució (estat_actual)

Fsi

Fsi

Fbucle

ffució

Una altra versió d'aquest algorisme de cerca general podria ser el següent:

Funció cerca_general (problema, estrategia) retorna solució o fallada

Espai ! inicialitació_espai (problema, estat inicial)

Mentre cert

Si no es pot expandir cap node (espai) llavors retorna fallada

Actual ! escollir_node_per_expandir (estrategia)

Si satisfa_condició_objectiu (actual) ! retorna actual

Fsi

Espai ! expandir_node (espai, actual)

Fmentre

Ffunció

Aquests dos algorisme implementen una cerca cega o desinformada i el que és util és la cerca informada.

Per poder fer una cerca informada necessitem declarar un tipus estructurat per indicar la informació a partir de la qual podem guiar la cerca.

Tipus

Problema es tupla estat_inicial: estat

Es_objectiu?:funció estat!bool

Operadors: cjt_de (operadors)

F_cost: funció estat x operador ! R

Ftipus

Ara la cerca general es pot fer de la següent forma:

Funció cercageneral (problema, fencuar) retorna solució o fallada

Var

Actual: estat

Oberts: supercua (estat)

Fvar

Oberts !encuar (supercua.crea, problema, estat_inicial)

Mentre cert

Si supercua.buida?(oberts) ! ret fallada

Actual ! desencuar(oberts);

Si problema.es_objectiu?(actual) ! ret atual

Fsi

Oberts ! fencuar(oberts, expandir(actual, problema.operadors));

Fmentre

Ffunció

Les estrategies que es poden seguir són el recorregut en amplada o en fondaria, i els algorismes es poden trobar a les trasparencies pagina 14.

Amplada

En amplada tenim una funció fencuar

fencuar: encuar_al_darrera

Aquesta funció garanteix que recorrem el nostre espai d'estats d'una forma sistemàtica. Ens garantirà completessa si existeix la solució (" solució ! segur que la trobem)

Amplada prioritària

OBERTS: llista de nodes als que s'ha arribat i encara no s'han expandit.

TANCATS: llista de nodes ja examinats.

INICIAL: descripció de l'estat inicial.

FINAL: descripció de l'estat final.

NODE_ACT: descripció de l'estat actual.

FILLS: llista que conté els nodes fills de l'estat actual.

OBERTS ! INICIAL

TANCATS ! NULL

NODE_ACT ! INICIAL

Associar un punter buit a INICIAL

mentre ¬buit(OBERTS) " (NODE_ACT<>FINAL) fer

OBERTS ! OBERTS - NODE_ACT

TANCATS ! NODE_ACT + TANCATS

FILLS ! expandir (NODE_ACT)

FILLS ! FILLS - TANCATS

FILLS ! FILLS - OBERTS

Associar a cada element de FILLS un apuntador a NODE_ACT

si algun_final (FILLS) llavors

NODE_ACT ! el_fil (FILLS)

sino OBERTS ! OBERTS + FILLS

NODE_ACT ! cap (OBERTS)

fsi

fmentrs

si NODE_ACT = FINAL llavors

proporcionar la seqüència solució.

sino

informar de que no existeix solució

fsi

A tots aquests algorismes, en lloc d'usar comparatius podriem usar un predicat del tipus:

final (NODE_ACT)

Fondaria

Fondaria Aquest algoritme no te completessa.

En aquest algorisme tenim dos variants:

• Fondaria limitada: fondaria on tindrà un màxim de node per baixar. (l = #_nodes -1). Si hi ha solució el camí que porta a la solució no pot tenir més de l passos.

• Fandaria iterativa (ID): aquesta fondaria es vàlida en arbres on no hi hagin moltes solucions.. qui anem provant per nivells de nodes. En aquest algorisme posem una fita per branca i quan arribem a aquesta fita (profunditat) continuem per la següent branca

	Fondaria Limitada	Fondaria Iterativa (ID)
fEncuar	si fondaria(n)<l llavors encuar_davant fsi	Fondaria_limitada(1) Fondaria_limitada(2) Fondaria_limitada(3) per i=1 fins " fer cerca_amb_fond_limitada(i) fper
Completesssa	Si si l és bona	Si
Temps	O(bl)	O(bd)
Espai	O(b·l)	O(b·d)

Fondaria Prioritària

OBERTS: llista de nodes als que s'ha arribat i encara no s'han expandit.

TANCATS: llista de nodes ja examinats.

INICIAL: descripció de l'estat inicial.

FINAL: descripció de l'estat final.

NODE_ACT: descripció de l'estat actual.

FILLS: llista que conté els nodes fills de l'estat actual.

OBERTS ! INICIAL

TANCATS ! NULL

NODE_ACT ! INICIAL

Associar un punter buit a INICIAL

mentre ¬buit(OBERTS) " (NODE_ACT<>FINAL) fer

OBERTS ! OBERTS - NODE_ACT

TANCATS ! NODE_ACT + TANCATS

si nivell(NODE_ACT) < PROF_MAX llevors

FILLS ! expandir (NODE_ACT)

FILLS ! FILLS - TANCATS

Associar a cada elements de FILLS un pnter a NODE_ACT

si algun_final (FILLS) llavors

NODE_ACT ! el_fill(FILLS)

sino OBERTS ! OBERTS - FILLS

OBERTS ! FILLS + OBERTS

NODE_ACT ! cap(OBERTS)

fsi

sino NODE_ACT ! cap (OBERTS)

fsi

fmentre

si NODE_ACT = FINAL llavors

proporcionar la seqüència solució

sino

informar de que no existeix soució

fsi

L'algorisme de cerca en amplada garanteix que recorrem l'espai de forma sistemàtica, en canvi l'algorisme en forndaria agafem una branca fins que aquesta acaba i aquesta pot ser infinita. A continuació veiem una taula resum de les característiques dels dos algorismes:

	Amplada	Fondaria		b= # maxim de fills (branching factor) d=fondaria
Fencuar	Encuar_al_darrera
Completessa	SI	NO
Cost temp	O(bd)
Cost espaial	O(bd)

El cost d'una operació és el cost que està associat a un arc de l'arbre. Si el cost és el mateix i positiu la optimalitat és bona en amplada.

Cerca bidireccional

Un altre esquema és el de cerca bidireccional: fem la cerca pels dos costats i amb els nodes que anem obtenint fem la intersecció. Si coincideixen en algun node, al´´o és un camí a la solució. Ara explorem un arbre de mida d/2 enlloc d'un arbre de mida d. L'ordre total serà 2·O(bd/d) per tant el cost en temps i espai és el següent:

Temps	O(bd/2)
Espai	O(bd/2)

Gestió dels estats repetits

Tenim tres possibilitats:

• Generar només els fills diferents del pare

• Anem guardant els nodes dels quals penja l'actual. Si no es pot expandir més, esborrem els pares (si no hi han més germans per probar).

• Gusrem tots els nodes (i punters).

Si estem en amplada

Cost Uniforme

Una variant del d'amplada és el de cost uniforme. En aquest algorisme els arcs quevan d'arc a arc tenen una etiqueta (prioirtat). El nostre algorisme posa primer a la cua el de prioritat menor (es a dir, el que l'etiqueta més petita. Així va buscant els nodes amb prioirtat més petita fins que troba la solució.

Troba la solució òptima si la funció de cost sobre els camins és creixent

Amb una altra versió de l'algorisme de cerca necessitem a més de la funció d'encuar, una funció d'evaluació.

Funció cerca_general (problema, fencuar, fevaluació)

...

mentre

....

estats ! cua_encuar (estats, expandir (actual), f evaluació)

fmentre

ffunció

El problema conté l'estat inicial, els operadors, la condició d'estat final, la funció de cost, etc.

La funció que tenim represnetada el que fa es encuar els estats nous amb ells vells en ordre decreixent segons fEvaluació.

Tipus de funció d'evaluació:

Algorisme	fEvaluació
Cost uniforme	G(n)		Cost mínim
Greedy Search (cerca avariciosa)	H(n)		Qualsevol estimació del cost del millor camí de n a l'estat objectiu més proper
A*	F(n)=g(n)+h(n)		Per un estat inicial i un estat objectiu. És l'estimació del millor camí cap a la solució que passa per n

Els millors algorisme són A* i el greedy search però aquest últim no es complet, en canvi A* es òptim amb les següents condicions:

• Si f és monotona

• Si h és admisible. h(n) és sempre més petit que el cost del millor camí de n al node objectiu.

Triarem la funció h “mes informada” i és més informada que h' si "n h'(n)<h(n) i h(n)<f(n).

Cerca Heuristica

Definicions prèvies:

• Cost d'un arc: c(mi, mj)

• Cost d'un camí:
  

• Cost del camí mínim K(mi,mj)= min Cl(l=1,...m)

• Cas on mj és un termnal final K(m, t)= h(m).

Si hi ha varis nodes termnals fials T={t1,.., tl}

h(m)= min K(m, ti)

• Cas on mi és un node inicial K(s, m)= g(m)

Si hi ha varis nodes inicials S= {s1, ...sl}

g(m) = min K(si, m)

Algorisme A*

En aquest algorisme necesitem una funció d'evaluació per intentar esbrinar quin és el millor camí. Per esbrinar quin pot sr el millor camí utilitzarem la funció heuristica (h(n), en concret utilitzarem l'estimador de l'heuristic h'(n))) i el cost propi del node (g(n)).

Les propietats dels heuristics són les següents:

• h' és admisible si "n: h'(n) " h(n)

• Si h' és admisible ! A*(h') serà òptim.

• La funció d'evaluació és monotona, es a dir, f va creixent cada vegada)

• Si h' és admisible ! h' és monotona.

• monotonia h ! consistencia h ! h(ni) - h(nj) " K(ni, nj)

K(ni, nj) ! camí optim de ni fins a nj.

En aquest algorisme tenim una cua d'oberts en la qual els elements s'ordenen de forma creixent segons la funció f. Sempre anem treient el node de cost minim i l'hem d'expandir.

Al agafar un node de la cua d'oberts i intentar exapandir-lo ens podem trobar dos casos:

• Orir un node ja obert, llavors actualitzem la nova f dins de la cua d'oberts, això si sempre agafant el valor petit de f

• Obrir un node ja tancat:

• Si h és consistent llavors no cal reobrir-lo

• Si h no és consistent llavors es torna a obrir (i encuar) i li asignem la f que li correspongui.

OBERTS ! INCIAL

TANCATS ! NULL

NODE_ACT ! INICIAL

Associar un pauntador buit a INICIAL

Associar valor de l'estimació a INICIAL

mentre ¬buit (OBERTS) " (NODE_ACT <> FINAL) fer

OBERTS ! OBERTS - NODE_ACT

TANCATS ! NODE_ACT + TANCATS

FILLS ! expandir (NODE_ACT)

FILLS1 ! FILLS - OBERTS

FILLS2 ! FILLS - FILLS1 /* FILLS2: duplicats que són OBERTS*/

FILLS ! FILLS1 - TANCATS

FILLS1 ! FILLS1 - FILLS /*FILLS1: duplcats que són a TANCATS*/

Tractar_FILLS

Tractar_FILLS1 /*Innecesari si l'heurístic usat és consistent*/

Tractar_FILLS2

OBERTS ! ordenar (OBERTS)

NODE_ACT ! cap(OBERTS

fmentre

si NODE_ACT = FINAL llavors

proporcionar la seqüència solució

sino

informar de que no existeix solució

fsi

Funció ordenar: ordena la llista d'oberts segons el valor de l'estimació (f)

Tractar_FILLS1 pot provocar “reobrir” nodes tancats i per tant, aquests nodes pooden ser novament expandits (re-exapnsió)

Tractar_Fills

Associar els valors de g' i f' a cada element de FILLS

Associar l'apuntador al pare (NODE_ACT) a cada element de FILLS

OBERTS ! FILLS + OBERTS

Tractar_Fills1 {duplicats que són a TANCATS}

Per a cada n de FILLS1 fer

si nva_g'(n) < antigag'(n) llavors

Associar a n un apuntador a NODE_ACT.

Associar a n la nova g' i la nova f'

TANCATS ! TANCATS - n

OBERTS ! n + OBERTS

fsi

fper

Tractar_Fills2 {duplicats que són a OBERTS}

Per a cada n de FILLS2 fer

si nova_g'(n) < antiga_g'(n) llavors

Associar a n un apuntador a NODE_ACT

Associar a n lanova g' i la nova f'

fsi

fper

Algorisme IDA*

Aquest algorisme és una combincació de l'algorisme A* juntament amb l'algorisme de fondaria iterativa o progressiva. En aquest algorisme necessitem el NVELLTALL, quest nivell és el valor màxim de la funció d'avaluació (f')

NIVELLTALL ! 1

NODE_ACT ! NULL

mentre (NODE_ACT <> FINAL) fer

OBERTS ! INICIAL

TANCATS ! NULL

NODE_ACT ! FINAL

Associar un apuntador buit a INCIAL

mentre ¬buit(OBERTS) " (NODE_ACT <> FINAL) fer

OBERTS ! OBERTS - NODE_ACT

TANCATS ! NODE_ACT + TANCATS

FILLS ! expandir (NODE_ACT, NIVELLTALL)

FILLS ! FILLS - TANCATS

Associar a cada element de FILLS un apuntador a NODE_ACT

si algun_final (FILLS) llavors

NODE_ACT ! el_fill (FILLS)

sino

OBERTS ! OBERTS - FILLS

OBERTS ! FILLS + OBERTS

NODE_ACT ! cap (OBERTS)

fsi

fmentre

NIVELLTALL ! NIVELLTALL +1

fmentre

Proporcionar la seqüència solució

La funció “expandir” només genera els nodes fills tals que el seu valor de f' sigui més petit o igual que NIVELLTALL.

Cal modificar-lo per tal de contemplar el cas de que no existeixi solució i fins i tot la possibilitat d'entrar en una branca infinita.

El grau d'informació entre dos heurístics és el sgüent:

• Donada h'1, h'2, llavors h'1 està més informada que h'2 si "n h'2(n) < h'1(n)

Esta més informada vol dir que esta més propera a l'estat al que volem arribar, es a dir, a l'estat solució.

Descomposició en subproblemes

La descomposició d'un problemes i altres més petits, és molt útil, ja que podem resoldre un problema bastant gran i difícil, resolent d'altres més petits i senzills. Per resoldre els problemes ens poden apareixer dos tipus d'unions entre els subproblemes:

• Conjució:per resoldre el problema principal hem de resoldre tots els seus subproblemes.

• Disjunció: per solucinar un problema només cal resoldre un dels seus subproblemes.

Els problemes que es troben en alguna fulla, són els anomenats problemes trivials o primitius

Les característiques de la descomposició en subproblemes són les següents:

• Dos tipus d'expansió de nodes: disjuntiva i conjuntiva.

• Els estats han de pertanyer al conjunt de subproblemes.

• Complexitat (subproblemes) < complexitat (problema)

• Solució: serà un graf degut a que existeix la conjunció i el su cost es calcula fent sumes en les expansions conjuntives

• Operadors: són de forma conjuntiva.

• Nodes resolts (R) són els:

• nodes terninals (problemes trivials o primitius)

• nodes de tipus o (disjunció) que tenen un fill resolt.

• nodes de tipus i (conjunció) que tenen tots els fills resolts.

• Nodes iressolubles:

• nodes terminals (sense fills) que no són problemes primitius (nodes queno surten a les capçaleres de les implicacions i nodes que oes troben a la base de fets).

• nodes de tipus o en que tots els fills són irresolubles.

• nodes de tipus i en que un dels fills és irresoluble.

• Condició d'acabament: que el node inicial es marqui com resolt o que es determini que és iresoluble.

• Solució: graf on l'arrel és el node incial, amb nodes i, nodes o, tots els nodes o tenen un sol fill. Cost: (node+arc) però en els node i, s suma el cost e tots els fills.

• funció heuristica: h': node ! R (estimació del cost òptim de resoldre aquell subproblemes)

• Nodes de tipus o: h'(n)= min [c(n,ni)+h'(ni)]

• nodes de tipus i : h'(n) = " [c(n,ni)+h'(ni)]

Algorisme AO*

OBERTS ! INICIAL

TANCATS ! NULL

GRAF ! INICIAL

Associar un apuntador buit a INICIAL

Associar valor de h' a INICIAL

mentre INICIAL_no_marcat fer

GE ! estimar_graf(GRAF)

NODE_ACT ! millor_node (GE " OBERTS)

OBERTS ! OBERTS - NODE_ACT

TANCATS ! NODE_ACT + TANCATS

si terminal_resluble(NODE_ACT) llavors

marcar_resolt_NODE_ACT

rutina_etiquetatge_nodes_resolts_a_GRAF

eliminar_d'OBERTS_nodes_si_avantpassats_resolts

sino

FILLS ! expandir (NODE_ACT)

si buit(FILLS) llavors

marcar_irresoluble_NODE_ACT

rutina_etiquetatge_nodes_irresolubles_a_GRAF

eliminar_d'OBERTS_nodes_si_avantpassats_irresolubles

actualitzar_h'_dels_avantpasats_de_NODE_ACT

sino

associar_apuntadors_entre_NODE_ACT_i_FILLS

associar_valor_h'_a_tots_FILLS

actualitzar_h'_de_NODE_ACT_i_dels_avantpassats

OBERTS ! FILLS + OBERTS

GRAF ! FILLS + GRAF

fsi

fsi

fmentre

si resolt (INICIAL) llavors

mostrar_graf_solució

sino

fracàs

fsi

Jocs

Nosaltres veurem un joc com a cerca en un espai d'estats.

• Estat: situació concreta (del joc) de la partida, i un booleà que indica a qui li toca jugar.

L'estructura de dades del joc seria la següent:

• Estat inicial

• Operadors. succesors: estat! {estat}

• Criteri d'acabament

• Funció d'utilitzat: serveix per evaluar cada un dels estats.

Funció=cond.favorables - cond desfavorables

• La solució serà l'estrategia o moviments que hem de fer per guanyar.

Tenim tres tipus d'algorismes sobre els jocs:

• MINMAX

• MINMAX heuristc

• Poda Alfa-Beta (-)

Algorisme MINMAX

L'idea d'aquest algorisme és etiquetar els estats des de les fulles amunt segons el torn del participant:

• Si hem d'escollir nosaltres agafem el node màxim

• Si li toca al contrincant agafem el mínim (que seria el millor resultat per ell)

Exemple:

funció MinMax (joc) retorna (operador, valor, utilitzat, final)

per cada op"joc.operadors fer

valor[op] ! MinMaxValor(aplicar(op, joc.estat_inicial), joc)

fper

retorna maxim (op, valor[op])

ffuncio

funció MinMaxValor(estat, joc) retorna valor

si jo.criteriFi (estat) llavors

retorna joc.fUtilitat (estat)

sino

si juga(estat)='jo' llavors

retorna


sino

retorna


fsi

fsi

ffunció

estat: tupla

r: representació d'un estat

juga: (jo, contrincant)

ftupla

Algorisme MINMAX Heuristic

Les diferencies que hi han entre l'algorisme anterior i aquest són les següents:

• Canviar la funció d'utilitat a funció d'evaluació (per aprofitar algun coneixement heuristic, per cada estat dona un valor que seria el cost estimat d'arribar al node solució).

• Canviar el criteri de Fi pel criteri de Poda que indica si hem de podar o no les branques que ens queden, es adir, si les hem de mirar o no.

Algorisme Alfa-Beta

En aquest algorisme anem mirant si podem ignorar alguna de les branques de l'arbre de la cerca, per fer això existeixen dos paràmetres alfa i beta. Es pot veure en el següent gràfic:

Els pares passen ,  als fills (un a un segons l'ordre d'exploració). Si estem en un fill MAX el valor d'aquest pasa al paràmetre beta del pare, i si estem en un fill MIN el valor d'aquest pasa al paràmetre alfa del pare. El criteri de poda serveix per treure els germans d'un node a partir del qual hem decidit podar.Es pot observar en el següent gràfic:

Mirar transparencias pàgina 34 en andavant.

funció MAXVALOR (estat, joc, , ) retorna el valor minmax de l'estat

si CriteriPoda (estat) llavors

retorna fEvaluació(estat)

sino

per cada s " suc (estat) fer

 ! MAX{, MINVALOR (s, joc, , )}

si  "  ! retorna 

fper

retorna 

fsi

ffunció

funció MINVALOR ( estat, joc, , ) retorna el valor minmax de l'estat

si CriteriPoda (estat) llavors

retorna fEvaluació(estat)

sino

per cada s " suc (estat) fer

 ! MIN{, MAXVALOR (s, joc, , )}

si  "  ! retorna 

fper

retorna 

fsi

ffunció

1

IIA-25

Què x y

-Buscar y x z

-retornar z

Persona

Alumnes

Alumnes

Telecos

Alumnes

informàtica

Maria

Pere

Joan

elements

Conjunts

Esquema d'un coneixement heretable

-fill

-filla

-mare

-pare

-germa

-germana

Si condició llavors accio1

Accio2

.

fsi

Base de coneixement

Base de coneixement

animal

vertebrat

volar

ales

groc

canta

ocell

canari

piolin

es_un

es_un

instancia_de

pot

capacitat de

habilitat

te_com_part

color

color de

NODES:

concpetes - ocell

individus - piolin

accions - volar

valors - groc

ARCS:

relacions - es_un

atributs -- color

resultat

e1

equiplocal

golsev

equipVis

golsl

inst_de

Joan

100000 pts

sou

Joan

sou-j

Pere

sou-p

50000

sou

sou

mes_gran

valor

sou_mes_gran

Pere

Joan

A

B

C

Frame slot

Facet valor

Facet demon if_needed

Prioritat dins del frame

frame

pare

avi

Inst_de

Es_un

Prioritat dintre de la jeràrquia

valor

If_needed

pare

avi

frame

1

2

4

3

6

5

N-Herència

Z-Herència

5

6

3

4

2

1

frame

avi

pare

If_needed

valor

Dintre del frame

Dintre de la taxonomia

OCELLS

ESTRUÇ

ELI

OCELLS DOMESTICS

-vola=si

-vola=no

Es_un

Es_un

Inst_de

Inst_de

*

*

MECANISME

GENERAL

· model declaratiu

· Demostració de

correctessa

MENYS

MENYS

MECANISME

ESPECÍFIC

· model procedimental

· correctessa?

MENYS

MENYS

Expressivitat

Eficiència

CP

SP

XS/F

Estat inicial

0

0

3

0

0

3

3

3

1

5

1

0

0

1

3

1

0

4

Gerra gran

Gerra petita

Omplir la petita

mj

mi

c(mi, mj)

C

mi

mj

K(ni, nj)

h(ni) - h( nj)

h(ni)

h( nj)

objectiu

ni

nj

f=0+h'(inicial)

c1

f=c10+h(node)

Objectiu

....

....

nostre torn

torn del contrincant

3

12

8

2

4

6

14

5

2

2

2

3

3

MAX

MIN

MAX

(MAX)





....

....

vi

Si vi >  ! modificar 

Si vi "  ! poda 

al final retorna 

vi

....

....





(MIN)

Si vi <  ! modificar 

Si vi "  ! poda 

al final retorna 

A

B

C

D

E

MAX

MAX

MIN

= i inf

= + inf

= i inf

= + inf /3

(3)

(3)

(3)

= i inf /3

= + inf

MIN

MAX

MAX

E

D

C

B

A