introducciÓ als esquemes algoritmicsima.udg.es/docencia/3105ig0003/5.backtracking.pdf ·...

INTRODUCCIÓ ALS ESQUEMES ALGORITMICS:

5. RECORREGUT DE GRAFS

JOAN SURRELL i SAURÍ

DEPARTAMENT D’INFORMÀTICA I MATEMÀTICA APLICADA

Introducció als Esquemes Algorítmics

- 2 -

INDEX

INDEX ...................................................................................................................................... 2

BIBLIOGRAFIA ...................................................................................................................... 3

1. INTRODUCCIÓ................................................................................................................. 4

2. BACKTRACKING ............................................................................................................... 5

2.1. Introducció ................................................................................................................... 5 2.2. Esquemes recursius....................................................................................................... 6 2.3. Esquemes iteratius ........................................................................................................ 8 2.4. Exemples.................................................................................................................... 10

2.4.1. El problema de les vuit reines........................................................................................................... 10 2.4.2. El salt del cavall ................................................................................................................................. 12 2.4.3. Optimització d’una motxilla ............................................................................................................. 15 2.4.4. Cifras y letras..................................................................................................................................... 20 2.4.5. El convit ............................................................................................................................................. 25

3. ALTRES RECORREGUTS ............................................................................................. 28

3.1. Introducció ................................................................................................................. 28 3.1.1. Recorregut en amplada o per nivells ................................................................................................ 28 3.1.2. Recorregut de cost mínim ................................................................................................................. 30 3.1.3. Poda d’una cerca................................................................................................................................ 32

3.2. Branch and bound ...................................................................................................... 33 3.2.1. Esquema ............................................................................................................................................. 33 3.2.2. Optimització de terminis ................................................................................................................... 35 3.2.3. El problema de la motxilla ................................................................................................................ 39

4. EXERCICIS...................................................................................................................... 51

5. Backtracking

- 3 -

BIBLIOGRAFIA

• Brassard, G.; Bratley, P. ALGORITMIQUE. CONCEPTION ET ANALYSE Masson, 1987 (Versió castellana de Novembre de 1990).

• Brassard, G.; Bratley, P. FUNDAMENTALS OF ALGORITHMICS Prentice-Hall, 1996 (Versió castellana de Novembre de 1997 amb errors).

• Gonzalo, J.; Rodríguez, M. ESQUEMAS ALGORÍTMICOS ENFOQUE METODOLÓGICO Y PROBLEMAS RESUELTOS UNED, 1997.

• Horowitz, E.; Sahni, S. FUNDAMENTALS OF COMPUTER ALGORITHMS Computer Science Press, 1978.

• Wirth, N. ALGORITMOS Y ESTRUCTURAS DE DATOS Prentice Hall Iberoamericana, 1986.


- 4 -

1. INTRODUCCIÓ

El grafs són les estructures de dades mé genèriques que hi ha. Amb el seu ajut es poden representar gran quantitat de problemes. Per la resolució dels problemes que es poden modelitzar amb grafs sol ser molt freqüent aplicar algoritmes qeu examinin tots els nodes o totes les arestes d’un graf. Altres problemes requereixen només visitar un cert nombre de nodes o arestes o bé fer una cerca fins a trobar un node o una aresta que compleixi una determinada condició.

En alguns problemes el graf es crea o és l’estructura de dades d’entrada i a partir d’ella es realitza la resolució del problema. No sempre succeeix així, ja que en algunna classe de problemes, com ara els jocs, el graf no es crea explícitament, sino que només es té una representació abstracta basada moltes vegades en el node actual (posició del joc), alguns elements adjacents i el camí seguit fins a la posició actual. En aquests tipus de problema el graf és infinit i extraordinariament gran. Cal substituir la representació explícita per tècniques algoritmiques que permetin fer-ne un recorregut o, més habitualment, una cerca. Traduit a la pràctica, això vol dir que cal no tractar nodes ja visitats (marcar el nodes) i poder generar els nodes adjacents a un de donat.

En aquest tema es tractaran diverses tècniques de recorregut de grafs, orientades a trobar la solució de certs problemes que es poden representar amb l’ajuda d’arbres o de grafs. Els esquemes presentats són molt generals i potents i poden ser aplicats a gran quantitat de situacions. El seu defecte, per anomenar-ho d’alguna manera, és el cost que presenten els algoritmes que s’obtenen a partir d’ells: generalment es tracta d’algortmes exponencials i superiors.

5. Backtracking

- 5 -

2. BACKTRACKING

2.1. INTRODUCCIÓ

El backtracking consisteix a resoldre problemes utilitzant algorismes que troben solucions sense seguir regles prefixades, sinó que apliquen un mètode sistemàtic de tempteig. El nom de backtracking es pot traduir com “seguir la pista cap enrera”.

El procediment bàsic utilitzat pel backtracking consisteix a descompondre el procés de tempteig en feines parcials. En cada feina es prova un camí cap a una possible solució, considerant-la com la solució correcta. Si es descobreix que aquest camí (solució) que s’ha prefixat no arriba a la solució desitjada, llavors es torna enrera i, seguint el tempteig sistemàtic, es prefixa una altra solució parcial que, novament, pot portar a la solució global o no. Aquest esquema algunes vegades també s’anomena assaig i error o tornada enrera.

Aquest mètode, basat en la realització de proves sistemàtiques, porta implícita una possibilitat d’error. Aquesta possibilitat d’error comporta la necessitat de retrocedir cada vegada que es descobreix que s’ha seguit un camí erroni cap a la solució final.

Cadascun dels camins a possibles solucions està ple de ramificacions que, al seu torn, es ramifiquen novament, formant un arbre. Aquest arbre s’anomena arbre de possibilitats. Si s’arriba a un punt en el camí que cap branca de les possibles no porta a una solució, llavors cal retrocedir. Aquest retrocés no es fa fins a la posició inicial del camí, sinó que només cal retrocedir fins a l’anterior ramificació i, a partir d’ella, fer una nova elecció (esperant tenir més sort).

Els problemes que es poden solucionar utilitzant aquest esquema són aquells on no es coneix cap forma per trobar la solució i el problema es pot descompondre en una sèrie de decisions o passos que poden conduir (si es té la sort d’encertar-los) cap a la solució completa. Com que no existeix cap manera de determinar la decisió o el pas correcte que segueix a un de determinat, cal fer un tempteig sistemàtic de tots els passos possibles.


- 6 -

Els esquemes de backtracking són molt costosos per qualsevol tipus d’ordinadors, ja que solen ser algorismes exponencials, O(an). Per fer més eficient l’algorisme resultant, cal anar molt amb compte a l’hora d’escollir la manera i l’ordre de realitzar l’elecció dins el ventall de possibilitats que hi ha a cada pas de l’arbre de possibilitats. També cal pensar detingudament l’estructura de dades que cal utilitzar de manera que simplifiqui l’algorisme.

2.2. ESQUEMES RECURSIUS

Els esquemes de backtracking s’expressen de manera més natural de forma recursiva. Així, l’esquema general per trobar una solució a un problema on es pot aplicar backtracking serà el següent:

ESQUEMA Backtracking Recursiu Una Solucio

Inicialitzar Conjunt De Candidats MENTRE QuedenCandidats AND NO Encertat FER Seleccionar I Esborrar Candidat SI Acceptable LLAVORS Anotar Candidat SI NO Solucio Completa LLAVORS Backtracking Pas Seguent {Crida Recursiva} SI NO Encertat LLAVORS Desanotar Candidat FSI ALTRAMENT Encertat:= Cert FSI FSI FMENTRE FESQUEMA

La variable Encertat seria global i s’inicialitzaria a Fals en el programa principal, ja que en començar no s’ha trobat encara la solució.

En alguns casos no es vol trobar només una solució al problema, sinó que interessa trobar totes les solucions. En aquest cas, l’esquema que cal utilitzar és el següent:

ESQUEMA Backtracking Recursiu Totes Les Solucions

Inicialitzar Conjunt De Candidats MENTRE Queden Candidats FER

5. Backtracking

- 7 -

Seleccionar I Esborrar Candidat SI Acceptable LLAVORS Anotar Candidat SI NO Solucio Completa LLAVORS Backtracking Pas Seguent ALTRAMENT Tractar Solucio FSI Desanotar Candidat FSI FMENTRE FESQUEMA

En altres casos el que interessa no és trobar una solució, ni trobar-les totes, sinó trobar la millor solució. En aquest cas es podria pensar a trobar totes les solucions i després agafar la millor. Tanmateix, cal veure que quan es disposa d’una solució, encara que no sigui la millor, és possible estalviar procés, ja que no cal mirar moltes branques de l’arbre de possibilitats. Es poden excloure totes aquelles que, d’alguna manera, no conduiran cap a una solució millor que la disponible fins al moment. El guany que aquesta exclusió comporta pot arribar a ser molt gran. L’esquema, adaptat a aquestes condicions, seria el següent:

ESQUEMA Backtracking Recursiu Solucio Optima

Inicialitzar Conjunt De Candidats MENTRE Queden Candidats FER Seleccionar I Esborrar Candidat SI Acceptable AND Es Pot Trobar Solucio Millor LLAVORS Anotar Candidat SI NO Solucio Completa LLAVORS Backtracking Pas Seguent ALTRAMENT SI Solucio Actual Millor Que Optima LLAVORS Optima Es Solucio Actual FSI FSI Desanotar Candidat FSI FMENTRE FESQUEMA


- 8 -

La inicialització de la solució òptima es realitzaria en el programa principal, ja que abans de començar no hi ha cap solució.

En aquest esquema és bo començar la recerca sistemàtica de tal manera que ràpidament es trobi una solució tal que, encara que no sigui la millor, s’hi acosti força. Així es fa una poda molt gran de l’arbre de possibilitats.

2.3. ESQUEMES ITERATIUS

Els esquemes recursius poden passar-se a iteratius seguint les regles donades anteriorment. Els esquemes resultants, un cop fetes les simplificacions i adaptacions oportunes, són els següents:

ESQUEMA Backtracking Iteratiu Una Solucio

Nivell:= 1 Inicialitzar Conjunt De Candidats MENTRE NO Encertat AND (Nivell ≥ 1) FER SI Queden Candidats en el Nivell LLAVORS Seleccionar I Esborrar Candidat SI Aceptable LLAVORS Anotar Candidat SI NO Solucio Completa LLAVORS Guardar Candidats Nivell Nivell:= Nivell+1 Inicialitzar Conjunt De Candidats ALTRAMENT Encertat:= Cert FSI FSI ALTRAMENT Nivell:= Nivell-1 SI (Nivell ≠ 0) LLAVORS Recuperar Candidats Nivell Anterior Desanotar Candidat FSI FSI FMENTRE FESQUEMA

ESQUEMA Backtracking Iteratiu Totes Les Solucions

Nivell:= 1 Inicialitzar Conjunt De Candidats

5. Backtracking

- 9 -

MENTRE (Nivell ≥ 1) FER SI Queden Candidats Nivell LLAVORS Seleccionar I Esborrar Candidat SI Acceptable LLAVORS Anotar Candidat SI NO Solucio Completa LLAVORS Guardar Candidats Nivell Nivell:= Nivell + 1 Inicialitzar Conjunt De Candidats ALTRAMENT Tractar Solucio Desanotar Candidat FSI FSI ALTRAMENT Nivell:= Nivell - 1 SI (Nivell ≠ 0) LLAVORS Recuperar Candidats Nivell Anterior Desanotar Candidat FSI FSI FMENTRE FESQUEMA

ESQUEMA Backtracking Iteratiu Solucio Optima

Nivell:= 1 Inicialitzar Conjunt De Candidats MENTRE (Nivell ≥ 1) FER SI Queden Candidats en el Nivell) LLAVORS Seleccionar I Esborrar Candidat SI Acceptable AND Es Pot Trobar Solucio Millor LLAVORS Anotar Candidat SI NO Solucio Completa LLAVORS Guardar Candidats Nivell Nivell:= Nivell + 1 Inicialitzar Conjunt De Candidats ALTRAMENT SI Solucio Actual Millor LLAVORS Optima Igual Solucio Actual FSI Desanotar Candidat FSI FSI ALTRAMENT Nivell:= Nivell - 1


- 10 -

SI (Nivell ≠ 0) LLAVORS Recuperar Candidats Nivell Anterior Desanotar Candidat FSI FSI FMENTRE FESQUEMA

2.4. EXEMPLES

2.4.1. EL PROBLEMA DE LES VUIT REINES

Enunciat: Col·locar 8 reines en un tauler d’escacs sense que es matin (Tant d’aquest problema, com de la resta que hi ha en aquest capítol, es pot trobar un enunciat complet al final del capítol).

A primer cop d’ull no es veu cap mètode per trobar la solució d’aquest problema. El millor que es pot fer és intentar una solució mitjançant assaig i error utilitzant backtracking.

Una vegada s’ha decidit que s’utilitzarà l’esquema de backtracking, caldrà escollir l’estructura de dades millor i més eficient per representar el tauler i les reines segons les necessitats del problema. Ni a cap fila, ni a cap columna no es poden tenir dues reines. Ni a cap diagonal, ja sigui ascendent o descendent tampoc no es poden tenir dues reines. Amb aquestes consideracions senzilles, però que moltes vegades no són gaire evidents, és possible determinar una estrucura de dades que pot fer baixar en gran mesura el temps de procés de l’algorisme. L’algorisme per resoldre aquest problema és el següent:

ALGORITME PosarReines VAR i: Enter Encertat: Boolea Fila: TAULA [1..8] DE Boolea Columna:TAULA [1..8] DE Enter Diagonal: TAULA [2..16] DE Boolea Contradiagonal: TAULA [-7..7] DE Boolea FVAR

ACCIO Reina(i: Enter; ENT SORT Encertat:Boolea) VAR j:Enter FVAR

5. Backtracking

- 11 -

ACCIO InicialitzarConjuntDeCandidats

j:= 0 FACCIO

ACCIO SeleccionarIEsborrarCandidat

j:= j+1 FACCIO

FUNCIO Acceptable RETORNA Boolea

RETORNA (Fila[j] AND Diagonal[i+j] AND Contradiagonal[i-j]) FFUNCIO

ACCIO AnotarCandidat

Columna[i]:= j Fila[j]:= Fals Diagonal[i+j]:= Fals Contradiagonal[i-j]:= Fals FACCIO

FUNCIO SolucioCompleta RETORNA Boolea

RETORNA(i = 8) FFUNCIO

ACCIO DesanotarCandidat

Fila[j]:= Cert Diagonal[i+j]:= Cert Contradiagonal[i-j]:= Cert FACCIO

FUNCIO QuedenCandidats RETORNA Boolea

RETORNA(j < 8) FFUNCIO

{inici de Reina} InicialitzarConjuntDeCandidats


- 12 -

MENTRE QuedenCandidats AND NO Encertat FER SeleccionarIEsborrarCandidat SI Acceptable LLAVORS AnotarCandidat SI NO SolucioCompleta LLAVORS Reina(i+1, Encertat) SI NO Encertat LLAVORS Desanotar ALTRAMENT Encertat:= Cert FSI FSI FMENTRE FACCIO

{ Programa Principal } PER i DE 1 FINS 8 FER Fila[i]:= Cert FPER PER i DE 2 FINS 16 FER Diagonal[i]:= Cert FPER PER i DE -7 FINS 7 FER Contradiagonal[i]:= Cert FPER Encertat:= Fals Reina(1,Encertat) SI Encertat LLAVORS PER i DE 1 FINS 8 FER Escriu(Columna[i]) FPER ALTRAMENT Escriu('No hi ha solució') FSI FPROGRAMA

2.4.2. EL SALT DEL CAVALL

Enunciat: Recórrer un tauler d’escacs de n x n caselles, a partir de la casella (1,1) seguint els moviments del cavall en el joc d’escacs i passant per totes les caselles una única vegada.

Per representar el tauler pot utilitzar-se una taula de dues dimensions. Aquesta taula pot ser de booleans per indicar si ja s’ha passat o no per la casella. Tanmateix, com que cal guardar el

5. Backtracking

- 13 -

recorregut fet, es pot fer la taula de sencers i guardar-hi el pas en què s’ha visitat la casella, de manera que un valor 0 indicarà que la casella encara no ha estat visitada.

Pel que fa als candidats (caselles noves on pot anar el cavall), cal recordar que en el seu moviment el cavall pot anar a vuit possibles caselles, sempre i quan estiguin buides i siguin interiors al tauler. El conjunt potencial de candidats és sempre el mateix, mentre que la funció Acceptable haurà de determinar si alguna de les condicions anteriors no es compleix abans de rebutjar un candidat. Com que els candidats són sempre els mateixos, es guardaran en una taula global de totes les etapes de la solució i, utilitzant un índex particular de l’etapa, es farà un recorregut per les vuit posicions de la taula en cada pas de la solució.

ALGORITME PosarCavalls CONST N = 6 FCONST

VAR i,j: Enter Encertat: Boolea Tauler: TAULA [1..N,1..N] DE Enter A,B: TAULA [1..8] DE Enter FVAR

ACCIO SaltCavall(i:Enter;ENT SORT Encertat:Boolea; X,Y:Enter) VAR j,u,v:Enter FVAR


j:= 0 FACCIO


j:= j + 1 u:= X + A[j] v:= Y + B[j] FACCIO



- 14 -

SI (u<1) OR (u>N) OR (v<1) OR (v>N) LLAVORS RETORNA(Fals) ALTRAMENT RETORNA(Tauler[u,v]=0) FSI FFUNCIO

ACCIO Anotar

Tauler[u,v]:= i FACCIO


RETORNA(i = N*N) FFUNCIO

ACCIO Desanotar

Tauler[u,v]:= 0 FACCIO


RETORNA(j < 8) FFUNCIO

{ inici del backtraking en si } InicialitzarConjuntDeCandidats MENTRE QuedenCandidats AND NO Encertat SeleccionarIEsborrarCandidat SI Acceptable LLAVORS Anotar SI NOT SolucioCompleta LLAVORS SaltCavall(i+1, Encertat,u,v) SI NO Encertat LLAVORS Desanotar ALTRAMENT Encertat:= Cert END FMENTRE FACCIO

{ programa principal } A[1]:= 2; B[1]:= 1 A[2]:= 1; B[2]:= 2

5. Backtracking

- 15 -

A[3]:= -1; B[3]:= 2 A[4]:= -2; B[4]:= 1 A[5]:= -2; B[5]:= -1 A[6]:= -1; B[6]:= -2 A[7]:= 1; B[7]:= -2 A[8]:= 2; B[8]:= -1 PER i DE 1 FINS N FER PER j DE 1 FINS N FER Tauler[i,j]:= 0 FPER FPER

Tauler[1,1]:= 1 Encertat:= Fals SaltCavall(2,Encertat,1,1)

SI Encertat LLAVORS PER i DE 1 FINS N FER PER j DE 1 FINS N FER Escriu(Tauler[i,j],' ') Escriu FPER ALTRAMENT Escriu('No hi ha solució') FSI FALGORITME

2.4.3. OPTIMITZACIÓ D’UNA MOTXILLA

Enunciat: Omplir una motxilla que pot suportar un pes màxim P amb un conjunt d’objectes cadascun dels quals té un pes i una utilitat determinada. El problema ha d’omplir la motxilla de manera que es maximitzi la suma d’utilitats dels objectes i no se superi, en cap cas, el pes màxim.

Aquest cas no és el cas típic de trobar una solució sinó que cal trobar la millor solució que satisfà les condicions del problema.

ALGORITME OptimitzarMotxilla CONST N = 30 FCONST


- 16 -

TIPUS Objecte = TUPLA Nom: Cadena Pes: Real Utilitat: 0..10 FTUPLA

ConjObjectes = TUPLA Obj: TAULA [0..N] DE Objecte Elements: Enter FTUPLA

Motxilla = TUPLA ObjPorta: TAULA [1..N] DE Enter Utilitat: Enter Pes: Real Elements:Enter PesSupor:Real FTUPLA FTIPUS

VAR MotxillaOptima: Motxilla MotxillaActual: Motxilla ConjuntObjectes: ConjObjectes PesMaxim: Real FVAR

ACCIO OmplirMotxilla(ENT SORT Obj:ConjObjectes, ENT SORT Optima,Actual:Motxilla) VAR j:Enter FVAR


SI (Actual.Elements = 0) LLAVORS j:= 0 ALTRAMENT j:= Actual.ObjPorta[Actual.Elements] FSI FACCIO


5. Backtracking

- 17 -

j:= j+1 FACCIO


RETORNA((Actual.Pes+Obj.Obj[j].Pes) ≤ Actual.PesSupor) FFUNCIO

ACCIO Anotar

Actual.Elements:= Actual.Elements + 1 Actual.Pes:= Actual.Pes + Obj.Obj[j].Pes Actual.Utilitat:= Actual.Utilitat+Obj.Obj[j].Utilitat Actual.ObjPorta[Actual.Elements]:= j FACCIO

ACCIO Desanotar VAR j:Enter FVAR

j:= Actual.ObjPorta[Actual.Elements] Actual.Pes:= Actual.Pes - Obj.Obj[j].Pes Actual.Utilitat:= Actual.Utilitat-Obj.Obj[j].Utilitat Actual.Elements:= Actual.Elements - 1 FACCIO


RETORNA(j < Obj.Elements) FFUNCIO

FUNCIO EsPotTrobarSolucioMillor RETORNA Boolea VAR Auxiliar: Real i: Enter FVAR

Auxiliar:= 0 PER i DE j+1 FINS Obj.Elements FER Auxiliar:= Auxiliar + Obj.Obj[i].Utilitat


- 18 -

RETORNA(Actual.Utilitat + Auxiliar > Optima.Utilitat) FFUNCIO

FUNCIO SolucioActualMillorOptima RETORNA Boolea

RETORNA(Actual.Utilitat > Optima.Utilitat) FFUNCIO

ACCIO OptimaIgualSolucioActual VAR i:Enter FVAR

PER i DE 1 FINS Actual.Elements FER Optima.ObjPorta[i]:= Actual.ObjPorta[i] FPER Optima.Utilitat:= Actual.Utilitat Optima.Pes:= Actual.Pes Optima.Elements:= Actual.Elements FACCIO

{inici de la recerca de la solució} InicialitzarConjuntDeCandidats MENTRE QuedinCandidats FER SeleccionarIEsborrarCandidat SI Acceptable AND EsPotTrobarSolucioMillor LLAVORS Anotar SI QuedenCandidats LLAVORS OmplirMotxilla(Obj, Optima, Actual) FSI SI SolucioActualMillorOptima LLAVORS OptimaIgualSolucioActual FSI Desanotar FSI FMENTRE FACCIO

ACCIO EntrarObjectes(ENT SORT A: ConjObjectes) VAR i:Enter FVAR

i:= 0 REPETIR i:= i+1

5. Backtracking

- 19 -

Escriu('Nom del objecte :') Llegir(A.Obj[i].Nom) Escriu('Pes : ') Llegir(A.Obj[i].Pes) Escriu('Utilitat: ') Llegir(A.Obj[i].Utilitat) FINS (i = 30) OR (A.Obj[i].Pes = 0) SI (i = 30) LLAVORS A.Elements:= 30 ALTRAMENT A.Elements:= i-1 FSI FACCIO

ACCIO InicialitzarMotxilla(ENT SORT A:Motxilla)

A.Elements:= 0 A.Pes:= 0 A.Utilitat:= 0 A.PesSupor:= PesMaxim FACCIO

ACCIO EntrarPesMaximMotxilla(ENT SORT A: Real)

Escriu('Quin es el pes suportable per la motxilla :') Llegir(A) FACCIO

ACCIO OrdenarObjectes(ENT SORT A: ConjObjectes) VAR i,j: Enter x: Objecte FVAR

PER i DE 2 FINS A.Elements FER x.Nom:= A.Obj[i].Nom x.Pes:= A.Obj[i].Pes x.Utilitat:= A.Obj[i].Utilitat A.Obj[0].Nom:= x.Nom A.Obj[0].Pes:= x.Pes A.Obj[0].Utilitat:= x.Utilitat j:= i-1 MENTRE (x.Utilitat/x.pes) > (A.Obj[j].Utilitat/A.Obj[j].Pes) FER A.Obj[j+1].Nom:= A.Obj[j].Nom A.Obj[j+1].Pes:= A.Obj[j].Pes


- 20 -

A.Obj[j+1].Utilitat:= A.Obj[j].Utilitat j:= j-1 FMENTRE A.Obj[j+1].Nom:= x.Nom A.Obj[j+1].Pes:= x.Pes A.Obj[j+1].Utilitat:= x.Utilitat FPER FACCIO

ACCIO EscriureSolucio(ENT SOR A:Motxilla;ENT SOR B:ConjObjectes) VAR i:Enter FVAR

Escriu('La solucio optima te els objectes :') PER i DE 1 FINS A.Elements FER Escriu(' De pes : ',B.Obj[A.ObjPorta[i]].Pes) Escriu(' i utilitat :') Escriu(B.Obj[A.ObjPorta[i]].Utilitat) FPER Escriu('El pes total es: ',A.Pes) Escriu('La utilitat es: ',A.Utilitat) FACCIO

{ programa principal } EntrarPesMaximMotxilla(PesMaxim) EntrarObjectes(ConjuntObjectes) OrdenarObjectes(ConjuntObjectes) InicialitzarMotxilla(MotxillaOptima) InicialitzarMotxilla(MotxillaActual) OmplirMotxilla(ConjuntObjectes,MotxillaOptima,MotxillaActual) EscriureSolucio(MotxillaOptima,ConjuntObjectes) FALGORITME

2.4.4. CIFRAS Y LETRAS

Enunciat: Cada dia de dilluns a divendres La 2 (TV-2) emet de 15 a 15:30 un programa concurs anomenat “CIFRAS Y LETRAS”. La part de xifres del concurs consisteix a fer el següent:

• Els concursants elegeixen sis valors numèrics d’entre quatre files. Les tres primeres files corresponen a valors entre 1 y 9 mentre que la darrera disposa dels valors 10, 25, 50, 75 i 100.

• A continuació la presentadora selecciona un número entre 100 i 999.

5. Backtracking

- 21 -

• A partir d’aquest moment els concursants disposen de 45 segundos per trobar una combinació que doni com a resultat el nombre seleccionat. Es poden utilitzar els sis valors i posar-hi entre ells les operacions +, -, *, /, amb els parèntesis que es vulgui i en els llocs que es vulgui.

Exemple: Si els valors escollits pels concursants són 10, 50, 7, 8, 1, 3 i el seleccionat per la presentadora és el 557 es poden obtenir les següents combinacions:

10 10 + 50 10 + 50 + 7 (10 + 50) + 7 10 + (50 + 7) ... 10 * 50 10 * 7 10 * (50 + 7) (10 * 50) + 7 ... (10 + 50) * 7 - (3 + 1) (10 + 50) * (7 - 3 + 1) ...

fins a trobar una combinació que doni el resultat seleccionat que, en aquest cas correspont a:

50 * (8+3) + 7

50 * (10 + 1) + 7

En cas de no trobar el valor exacte es dona com a bona la millor aproximació, ja sigui per excés com per defecte.

Es demana: Fer un programa que utilizant un esquema de tempteig sistemàtic (backtraking) no recursiu simuli un concursant.

• Se suposa que els valors escollits pels concursants estaran en un vector Operants: TAULA [1..6] DE Enter (els dos primers corresponen a la quarta fila i les restants a xifres de la restants files) i el valor seleccionat per la presentadora estarà en una variable Resultat: Enter.

• Per a que el programa no sigui molt complex se dispone de la sigüent acció:


- 22 -

ACCIO Evalua (OpEnt: TAULA [1..6] DE Enter; OperaEnt: TAULA [1..5] DE '*', '/', '+', '-'; NumOpent: Enter; Resultat: Enter; VAR Millor: Real; VAR Combinacio: Cadena[100])

que a partir d’una combinació de xifras y operadors, a més del resultat que es vol obtenir, retorna la millor aproximació i la cadena amb la fórmula de la millor aproximació. Així, en el exemple anterior, si s’entra amb:

OpEnt = [10, 50, 7, 3, ?, ?] OperaEnt = [+, *, +, ?, ?] NumOperant = 4 Resultado = 557

evaluarà:

10 + 50 * 7 + 3 (10 + 50) * 7 + 3 10 + (50 * 7) + 3 10 + 50 * (7 + 3) (10 + 50) * (7 + 3) (10 + 50 * 7) + 3 10 + (50 * 7 + 3)

donant com a resultat:

Millor = 560 Combinacio = '10 + 50 * (7 + 3)'

Nota: no cal optimitzar el procés.

Solució:

TIPUS TaulaEnters: TAULA [1..6] DE Enter TaulaBooleans: TAULA [1..6] DE Boolea TaulaOperacionsPossibles: TAULA [1..4] DE Caracter TaulaOperacionsExpressio: TAULA [1..5] DE Caracter TuplaCandidats: TUPLA Valors: TaulaEnters Usats: TaulaBooleans Operacions: TaultaOperacionsPossibles FTUPLA TuplaSolucio: TUPLA

5. Backtracking

- 23 -

Valors: TaulaEnters Operacions: TaulaOperacionsExpressio Resultat: Enter Expressio: Cadena NElements: Enter FTUPLA FTIPUS

VAR Candidats: TuplaCandidats SActual, SOptima: TuplaSolucio Resultat: Enter FVAR

ACCIO CalcularExpressio(i: Enter) VAR jOperacio, jValor: Enter FVAR

ACCIO InicialitzarConjuntDeCandidats jOperacio:= 0 jValor:= 1 {veure seleccionar} FACCIO

FUNCIO QuedenCandidats RETORNA Boolea RETORNA(NO ((jOperacio = 4) AND (jValor = 6))) FFUNCIO

FUNCIO EsPotTrobarSolucioMillor RETORNA Boolea RETORNA(SOptima.Resultat ≠ Resultat) FFUNCIO

ACCIO SeleccionarCandidatIEsborrar SI (jOperacio = 4) LLAVORS jOperacio:= 1 jValor:= jValor + 1 ALTRAMENT jOperacio:= jOperacio + 1 FSI FACCIO

FUNCIO Acceptable RETORNA Boolea RETORNA(NO Candidats.Utilitzats[jValor]) FFUNCIO


- 24 -

ACCIO AnotarCandidat Candidats.Utilitzats[j.Valor]:= Cert SActual.Valors[i+1]:= Candidats.Valors[jValor] SActual.Operacions[i]:= Candidats.Operacions[jOperacio] SActual.NElements:= i+1 Avalua(SActual.Valors, SActual.Operacions, SActual.NElements, SActual.Resultat, SActual.Expressio) FACCIO

FUNCIO SolucioMillor RETORNA Boolea VAR DiferenciaActual, DiferenciaOptima: Enter FVAR

DiferenciaActual:= Abs(Actual.Resultat - Resultat) DiferenciaOptima:= Abs(Optima.Resultat - Resultat) RETORNA(DiferenciaActual < DiferenciaOptima) FFUNCIO

ACCIO DesanotarCandidat Candidats.Utilitzats[j.Valor]:= Fals SActual.NElements:= i { realment, no cal } FACCIO

InicialitzarConjuntDeCandidats MENTRE QuedenCandidats AND EsPotTrobarSolucioMillor FER SeleccionarCandidatIEsborrar SI Acceptable {AND EsPotTrobarSolucioMillor} LLAVORS AnotarCandidat SI SolucioMillor LLAVORS SOptima:= SActual FSI SI (i < 5) LLAVORS CalcularExpressio(i+1) FSI DesanotarCandidat FSI FMENTRE FACCIO

En el programa principal caldria posar el següent codi:

{programa principal} Resultat:= ?

5. Backtracking

- 25 -

Candidats.Valors[]:= <?, ?, ?, ?, ?, ?> Candidats.Usats[]:= <Fals, Fals, Fals, Fals, Fals, Fals> Candidats.Operacions[]:= <'+','-','*','/'> SOptima.NElements:= 1 SOptima.Expressio:= "" SOptima.Resultat:= 0 PER i DE 1 FINS 6 FER SActual.Valors[1]:= Candidats.Valors[i] SActual.NElements:= 1 SActual.Expressio:= "?" SActual.Resultat:= Candidats.Valors[i] Candidats.Usats[i]:= Cert CalcularExpressio(1) Candidats.Usats[i]:= Fals FPER

2.4.5. EL CONVIT

Enunciat: S’han de distribuir n convidats en una taula on hi ha lloc per n comensals. Es disposa d’una Afinitat(k,l) que retorna un valor comprès entre 0 i 10 segons el grau d’afinitat que els convidats k i l tinguin entre si (0 indica aversió profunda i 10 simpatia desbordant). Els comensals es disposen en una taula circular, per la qual cosa dos comensals són adjacents si ocupen posicions veines.

Dissenyeu, segons el mètode d’assaig i error, un algorisme que calculi la distribució de convidats a la taula que optimitza el seu benestar. Aquest benestar es calcularà sumant les afinitats dels comensals asseguts en posicions adjacents.

TIPUS Candidat = TUPLA Codi: Enter ... FTUPLA TaulaCandidats = TAULA [1..NCandidats] DE Candidat TuplaSolucio = TUPLA Candidats: TaulaCandidats Benestar: Enter FTUPLA FTIPUS


- 26 -

VAR SActual, SOptima: TuplaSolucio FVAR

ACCIO Seure(i: Enter, Candidats: TaulaCandidats) VAR CActual, CAnterior: Candidat Benestar: Enter FVAR

InicialitzarConjuntDeCandidats MENTRE QuedenCandidats FER SeleccionarIEsborrarCandidat SI Acceptable AND EsPotTrobarSolucioMillor LLAVORS AnotarCandidat SI SolucioCompleta LLAVORS Benestar:= Afinitat(1, CActual.Codi) SActual.Benestar:= SActual.Benestar+Benestar SI SolucioMillor LLAVORS SOptima:= SActual FSI Benestar:= Afinitat(1, CActual.Codi) SActual.Benestar:= SActual.Benestar-Benestar ALTRAMENT Candidats[j]:= Candidats[NCandidats-i] Seure(i+1, Candidats) Candidats[j]:= CActual FSI DesanotarCandidat FSI FMENTRE FACCIO


Ordenar(Candidats, NCandidats - i + 1) {natural o avancat} j:= 0 CAnterior:= SActual.Candidats[i-1] FACCIO


RETORNA(j < NCandidats - i) FFUNCIO


5. Backtracking

- 27 -

j:= j + 1 CActual:= Candidats[j] FACCIO


RETORNA(Cert) FFUNCIO

FUNCIO EsPotTrobarSolucioMillor RETORNA Boolea

RETORNA(SActual.Benestar+(NCandidats-i+1)*10)>SOptima.Benestar) FFUNCIO

ACCIO AnotarCandidat VAR Benestar: Enter FVAR

SActual.Candidats[i]:= CActual Benestar:= Afinitat(CActual.Codi, CAnterior.Codi) SActual.Benestar:= SActual.Benestar + Benestar FACCIO


RETORNA(i = NCandidats) FFUNCIO

FUNCIO SolucioMillor RETORNA Boolea

RETORNA(SActual.Benestar > SOptima.Benestar) FFUNCIO

ACCIO DesanotarCandidat

Benestar:= Afinitat(CActual.Codi, CAnterior.Codi) SActual.Benestar:= SActual.Benestar - Benestar FACCIO


- 28 -

3. ALTRES RECORREGUTS

3.1. INTRODUCCIÓ

3.1.1. RECORREGUT EN AMPLADA O PER NIVELLS

L’esquema de backtraking serveix per resoldre problemes en els que la solució es pot expressar com un conjunt finit de parts, cadescuna de les quals pot tenir un cert nombre de valors coneguts. La tècnica de resolució del problema consisteix en anar provant solucions construides element a element fins a trobar-ne una que compleixi les condicions imposades pel problema a resoldre. Aquesta tècnica de treball rep el nom de assaig i error a causa de la seva forma de procedir. Amb ella és possible determinar una solució a un cert problema, trobar-les totes o trobar la que optimitza una certa funció.

1

2

3

4

5

6

7

8

9

10

11 12

13

14

15

Figura 1: exemple d’arbre n-ari d’un esquema de backtraking

Com ja s’ha vist anteriorment l’algoritme que s’obté amb aquest esquema realitza un recorregut en preordre d’un arbre n-ari de candidats. Un arbre n-ari pot tenir altres recorreguts: postordre, inordre (no gaire usual) o per nivells. Els recorreguts en postordre o en inordre no aporten cap variació respecte al recorregut en preordre. No succeeix el mateix amb el recorregut per nivells. Un exemple ajudarà a il·lustrar-ho:

5. Backtracking

- 29 -

Enunciat: Donats dos valors enters, r i s, i dues funcions, f1(n) = 3*n i f2(n) = n div 2, determinar la seqüència mínima de manipulacions que cal fer en r per transformar-lo en s utilitzant les funcions donades.

Exemple: r = 3

s = 13f2 f1 f1 3 = 13

Aquest problema és un bon candidat a ser resolt utilitzant backtraking. Tanmateix, apareix un problema que es pot veure fàcilment si es dibuixa l’arbre de candidats:

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3

9 1

27 4 3 0

81 13 12 2

Figura 2: Part de l’arbre generat en el problema de les funcions

Com es pot veure l’arbre resultant és d’alçada infinita i no és possible podar-lo de cap manera visible. Si es realitza un recorregut en preordre, no hi ha cap condició que pugui fer retornar des de la primera branca. Una estratègia alternativa seria fer un recorregut per nivells de l’arbre: 3, 9, 1, 27, 4, 3, 0, 81, 13. Aquest mètode de treball permet solventar alguns problemes difícilment resolubles utilitzant altres tècniques.

FUNCIO Manipulacions (r, s: Enter) RETORN Llista(Enter) VAR l: Llista(Enter) q: Cua(<Enter, Llista(Enter)>) c: Conjunt(Enter) i, j: Enter Trobat: Boolea FVAR


- 30 -

CrearLl(l) CrearQ(q) CrearConjunt(c) Encua(c, <r, l>) Trobat:= Fals {caldria assegurar que el bucle sempre acaba} MENTRE NO Trobat AND NO CuaBuida(q) FER k:= 1 MENTRE (k<=NFuncions) FER <i, l>:= Primer(q) j:= fk(i) Inserir(l, k) SI (j = s) LLAVORS Acabar:= Cert ALTRASI NO Existeix(c, j) LLAVORS Afegeix(c, j) Encua(c, <j, l>) FSI FPER Desencua(q) FMENTRE Primer(l) RETORNA(l) FFUNCIO

3.1.2. RECORREGUT DE COST MÍNIM

Si s’aplica el recorregut per nivells a altres problemes els resultats que dóna no són millors als obtinguts per backtraking. Així, pel problema de les reines amb n=4 s’obtenen els següents arbres de candidats si el recorregut es realitza en preordre o per nivells:

5. Backtracking

- 31 -

1

2

3 4 5

6 7 8 9

10

11 12

13 14 15 16

17 18

19

20 21 22 23

24

25 26 27 28

29 30 31

32

33

34 35 36 37

38 39 40 41

42 43 44

45

46

47 48 49

50 51 52 53

54

55

56 57 58 59

60 61

Figura 3: resolució del problema de les reines (n=4) per backtracking

1

2 3 4 5

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

Figura 4: resolució del problema de les reines (n=4) fent el recorregut per nivells

Com es pot veure després de generar 27 nodes s’obté la primera solució amb backtraking, mentre que cal generar-ne 52 per obtenir la solució amb el recorregut per nivells.


- 32 -

Tanmateix el recorregut per nivells es pot millorar utilitzant la següent idea: els diferents nodes no tenen la mateixa probabilitat de generar una solució. Si a cada node (solució parcial) se li assigna un valor que quantifiqui l’esperança que té d’esdevenir solució, la cua de nodes es pot transformar en una cua de prioritat de manera que no s’esculli aquell element que faci més temps que s’hagi generat, si no aquell que sembli que ha de donar lloc a solució més ràpidament. Evidentment la generació de la funció que determina l’esperança d’esdevenir una solució no és en absolut trivial. Existeixen tècniques d’optimització com les vistes a algoritmes voraços o en la cerca de solucions òptimes en backtraking que podem servir com a base de determinació d’aquestes funcions per un problema donat.

La tècnica de recorregut d’un arbre de candidats amb priorització dels nodes a tractar rep el nom de recorregut de cost òptim, ja que intenta optimitzar el recorregut que es realitza en l’arbre. Si la funció de cost s’agafa com l’ordre amb que són generats els nodes s’obté un recorregut per nivells, mentre que si la funció de cost equival al nombre de nivells que manquen per arribar a la solució completa (per simplificar el raonament es pot suposar que totes les solucions tenen el mateix nombre d’elements), s’obté un recorregut en profunditat o en preordre de l’arbre, semblant al que es realitza en l’algoritme de backtraking. Es pot afirmar que el recorregut amb cua de prioritat inclou als dos anteriors.

3.1.3. PODA D’UNA CERCA

Els diferents mètodes mostrats en aquesta introducció ofereixen diferents tècniques per obtenir la solució d’un problema donat. Tots ells comparteixen una característica comú: fan una cerca de la solució dins un arbre de candidats utilizant una estructura auxiliar (pila, cua o cua de prioritat) per guardar els nodes generats. En tots ells s’obtenen algoritmes amb ordres d’execució exponencials o pitjors, per la qual cosa qualsevol mètode que permeti reduir el nombre de nodes de l’arbre acostuma a ser d’una gran ajuda.

Si qualsevol mètode de recorregut s’aplica a un problema d’optimització existeix una funció que es vol optimitzar. El valor d’aquesta funció es pot utilitzar per deixar de recòrrer algunes branques de l’arbre de candidats que es pugui assegurar que donaran lloc a solucions pitjors a la millor que s’ha obtingut fins el moment o, en cas que no se’n disposi de cap, a la millor estimació que es pugui fer d’ella. Aquest mètode de podar l’arbre és una generalització del mètode utilitzat en l’esquema de backtraking quan s’utilitzava per trobar la solució òptima.

5. Backtracking

- 33 -

3.2. BRANCH AND BOUND

3.2.1. ESQUEMA

L’esquema de branch and bound (ramificació i poda) es pot aplicar a problemes dels quals no es coneix cap mètode eficient per determinar la solució i la seva obtenció comporta el recorregut d’un arbre de candidats. La base d’aquest esquema és molt simple i es pot resumir en els següents punts:

• Els nodes generats es guardaran en una estructura de dades auxiliar (generalment una cua de prioritat), que es començarà a omplir amb l’arrel de l’arbre de candidats.

• Cada pas (iteració) de l’esquema s’agafarà un element de l’estructura de dades auxiliar, s’eliminarà d’ella i es convertirà amb el node actiu.

• Es generaran tots els fills del node actiu. Aquesta operació rep el nom de ramificació (branch).

• Es comprobarà si aquests fills generats poden esdevenir solució i si poden fer-ho amb un valor millor que la millor optimització obinguda fins el moment. Es descartaran aquells elments que no compleixin alguna de les dues condicions. Aquesta operació rep el nom de poda (bound).

• Si algun dels fills és solució completa i la seva funció d’optimització és millor que la millor obtinguda fins el moment, aquesta solució esdevindrà la nova solució òptima.

• Els fills restants s’afegiran a l’estructura de dades.

• Aquest procés es finalitzarà quan l’estrutura de dades estigui buida.

Un esquema molt general del procés anterior el tenim a continuació:

ESQUEMA Branch and Bound

Crear Estructura Posar Arrel Arbre Determinar Valor Limit Inicial MENTRE NO Estructura Buida FER Seleccionar i Esborrar Primer Element Estructura Obtenir Fills {ramificar} Calcular Intervals Valor Limit Podar Fills No Acceptables o Solucions No Millors Guardar Fills No Podats


- 34 -

FMENTRE FESQUEMA

Aquests esquema és de més alt nivell que el de backtraking i, per tant, comportarà més feina cara a l’obtenció de l’algoritme corresponent. Una versió del mateix esquema més detallada podria ser la següent:

ESQUEMA Branch and Bound

Crear Estructura Posar Arrel Arbre Determinar Valor Limit Inicial MENTRE NO Estructura Buida FER Seleccionar i Esborrar Primer Element Estructura PER tots els fills FER Obtenir Fill {ramificar} Calcular Intervals Valor Limit SI Acceptable AND Es Pot Trobar Solucio Millor LLAVORS SI Solucio Completa LLAVORS SI Solucio Millor LLAVORS Optima:= Actual FSI ALTRAMENT Guardar Fill FSI SI Llindar Millor LLAVORS Actualitzar Llindar FSI FSI FPER FMENTRE FESQUEMA

Cal recordar aquí novament que un esquema és una manera d’enfocar una resolució d’un problema i, com a tal, no es pot pendre con un formulari fix aplicable a qualsevol problema de la mateixa manera, si no que cal adaptar-lo a la concepció de l’algoritme segons els requisits particulars del problema. És per això que algunes vegades l’algoritme resultant en aplicar el mètode de branch and bound no tindrà molt a veure amb la darrera versió de l’esquema presentat.

A primera vista, l’esquema de branch and bound pot semblar apte per resoldre només problemes d’optimització. Tanmateix pot utilitzar-se per obtenir la solució d’altres problemes sempre que es

5. Backtracking

- 35 -

pugui obtenir una funció de cost que quantifiqui la possibilitat de que un node esdevingui solució. Així quan més probable sigui que un node esdevingui solució més aviat serà tractat.

Cal destacar un aspecte que en la formulació dels esquemes anteriors potser no ha quedat massa clar. Per cada node visitat es determinen dos valors del llindar d’optimització, un per excés i l’altre per defecte. Així, per exemple, en un problema de minimització interesa determinar l’interval de valors entre els que es mourà la funció a minimitzar per a cada node generat. Si el valor mínim de l’interval és més gran que el millor valor òptim obtingut fins al moment, aquest node no pot donar lloc a una solució millor i, per tant, cal descartar-lo. Si, pel contrari, el valor màxim de l’interval és inferior al millor valor òptim és pot és pot posar-lo com a nou valor òptim. En un node solució els dos extrems de l’interval coincidiran, ja que no es tracta d’un valor estimat, si no del valor real.

A la vista de l’esquema anterior un es pot preguntar si realment aquest esquema dona lloc a un algoritme eficient, ja que cal realitzar un gran nombre de càlculs per cadescun dels nodes de l’arbre. Aquests dubtes s’accentuen si es desenvolupa un algoritme utilitzant aquest esquema ja que, a diferència del cas del backtraking, els algoritmes resultants acostumen a ser força grans i complexos i és difícil de copsar a primer cop de vista si l’algoritme obtingut és millor que el que s’obtindria usant altres mètodes. Respondre a aquesta questió no és senzill ja que no sempre s’obtenen els mateixos resultats. Cal recordar aquí que les tècniques per dissenyar algoritmes no asseguren en cap cas que l’algoritme obtingut sigui eficient si no que només donen unes pautes per obtenir un nou algoritme que resolgui un cert problema. Un cop obtingut l’algoritme caldrà analitzar la seva eficiència i veure en quins casos és aplicable.

3.2.2. OPTIMITZACIÓ DE TERMINIS

Enunciat: Es disposa d’un conjunt de n tasques que necessiten una certa quantitat de temps per ser processades, que pot ser diferent entre elles. Cal realitzar-les de manera seqüencial. Cada tasca té associat un cert benefici que només s’obtè si es pot realitzar abans del termini que té fixat per ser acabada. Determinar la seqüencia de tasques que produeix un major benefici.

TIPUS Tasca = TUPLA Temps: Enter Benefici: Enter Termini: Enter FTUPLA TaulaTasques = TAULA [1..NTasques] DE Tasca


- 36 -

Solucio = TUPLA Tasques: TaulaTasques NElements: Enter Benefici: Enter BeneficiMaxim: Enter Durada: Enter DarreraTasca: Enter FTUPLA CuaSolucions = Cua(Solucio) FTIPUS

FUNCIO OrdreTasques(Candidats:TaulaTasques) RETORNA Solucio VAR i, j: Enter q: CuaSolucions Resultat, Actual, Nova: Solucio TasquesFetes: TaulaBooleans BeneficiMinim: Enter FVAR

CrearCua(q) BeneficiMinim:= 0 Encua(q, Actual) Inicialitza(Actual) Resultat:= Actual MENTRE NO CuaBuida(q) FER Actual:= Primer(q) Desenqua(q) PER i DE Actual.DarreraTasca + 1 FINS NTasques FER Nova:= Actual SI TascaAfegible(Nova, Candidats[i]) LLAVORS AfegirTasca(Nova, Candidats, i) SI (Nova.BeneficiMaxim > BeneficiMinim) LLAVORS Encuar(q, Nova) SI (Nova.Benefici > BeneficiMinim) LLAVORS BeneficiMinim:= Nova.Benefici Resultat:= Nova FSI FSI FSI FPER FMENTRE RETORNA(Resultat) FACCIO

ACCIO Inicialitza(SORT s:Solucio)

5. Backtracking

- 37 -

s.NElements:= 0 s.Benefici:= 0 s.BeneficiMaxim:= SumarBeneficis(Candidats, 1) s.Termini:= 0 s.DarreraTasca:= 0 FACCIO

FUNCIO SumarBeneficis(Candidats:TaulaTasques, i:Enter) RETORNA Enter VAR j, Resultat: Enter FVAR

Resultat:= 0 PER j DE i FINS NTasques FER Resultat:= Resultat+Candidats[j].Benefici FPER RETORNA(Resultat) FFUNCIO

FUNCIO TascaAfegible(s: Solucio, t: Tasca) RET Boolea VAR i, j: Enter Acceptable, Trobat: Boolea Termini: Enter FVAR

Acceptable:= Cert Trobat:= Fals j:= s.NElements Termini:= s.Durada + t.Temps MENTRE (j > 0) AND Acceptable AND NO Trobat FER SI (Termini < s.Tasques[j].Termini) LLAVORS Acceptable:= Fals ALTRASI (s.Tasques[j].Termini < t.Termini) LLAVORS Trobat:= Cert ALTRAMENT Termini:= Termini - s.Tasques[j].Durada j:= j-1 FSI FMENTRE RETORNA(Acceptable AND Trobat) FFUNCIO

ACCIO AfegirTasca(SORT s: Solucio; Candidats: TaulaTasques; i: Enter)


- 38 -

VAR j: Enter Acabar: Boolea FVAR

j:= s.NElements Acabar:= Fals MENTRE (j > 0) AND NO Acabar FER SI (s.Tasques[j].Termini < Candidats[i].Termini) LLAVORS Acabar:= Cert ALTRAMENT s.Tasques[j+1]:= s.Tasques[j] j:= j - 1 FSI FMENTRE

s.Tasques[j+1]:= Candidats[i] s.NElements:= s.NElements+1 s.Benefici:= s.Benefici + Candidats[i].Benefici s.BeneficiMaxim:= SumarBeneficis(Candidats, i+1) s.Durada:= s.Durada + Candidats[i].Temps s.DarreraTasca:= i FACCIO

Si s’aplica aquest esquema a un conjunt de dades tal com el següent

Element Guany Temps Termini 1 5 1 1 2 10 2 3 3 6 1 2 4 3 1 1

s’obté un resultat que queda reflexat a la següent taula:

Node Tasques Durades Terminis Guany Llindar Valors Vàlids Mínim Màxim Valor Vàlid 1 √ 0 24 0 √ 2 1 1 1 √ 5 24 5 √ 3 2 2 3 √ 10 19 10 √ 4 3 1 2 √ 6 9 10 √ 5 4 1 1 √ 3 3 10 √ 6 1, 2 1, 3 1, 3 √ 15 24 15 √ 7 1, 3 1, 2 1, 2 √ 11 14 15 √

5. Backtracking

- 39 -

8 1, 4 1, 2 1, 1 x 8 8 15 x 9 3, 2 1, 3 2, 3 √ 16 19 16 √ 10 4, 2 1, 3 1, 3 √ 13 13 16 x 11 4, 3 1, 2 1, 2 √ 9 9 16 x 12 1, 3, 2 1, 2, 4 1, 2, 3 x 21 24 16 √ 13 1, 4, 2 1, 2, 4 1, 1, 3 x 18 18 16 √ 14 1, 4, 3 1, 2, 3 1, 1, 2 x 14 14 16 x 15 4, 3, 2 1, 2, 4 1, 2, 3 x 19 19 16 √ 16 1, 4, 3, 2 1, 2, 3, 5 1, 1, 2, 3 x 24 24 16 √

L’arbre generat per aquest exemple correspon a la següent figura:

1

2 3 4 5

6 7 8 9 10 11

12 13 14

16

15

12 3

4

2

34 3 4 4

3 4

4

4 4

Figura 6: Arbre de cerca generat en el problemade l’optimització de terminis

3.2.3. EL PROBLEMA DE LA MOTXILLA

Enunciat: Tenim una col·lecció de n objectes que cal col·locar en una caixa que resisteix un pes màxim M. L’objecte i té un pes pi i un valor vi. Dissenyar un algorisme que trobi aquell conjunt

d’objectes de la col·lecció tal que la suma dels seus pesos no superi M i la suma dels seus valors sigui màxima.

TIPUS Objecte = TUPLA Pes: Enter Profit: Enter FTUPLA


- 40 -

TaulaObjectes = TAULA [1..NObjectes] DE Objecte TaulaBooleans = TAULA [1..NObjectes] DE Boolea Solucio = TUPLA Objectes: TaulaBooleans NObjectes: Enter Pes: Enter ProfitMinim: Enter ProfitMaxim: Enter FTUPLA CuaNodes = Cua(Solucio) FTIPUS

FUNCIO OmplirMotxilla(Candidats:TaulaObjectes, Pes:Enter) RET Solucio VAR SActual, SOptima, SNova: TuplaSolucio q: CuaNodes ProfitLlindar: Enter FVAR

Inicialitzar MENTRE NO CuaBuida(q) FER SActual:= Primer(q) Desencua(q) SI (SActual.ProfitMaxim > ProfitLlindar) LLAVORS SNova:= SActual AfegirObjecte ProcessarNouNode

SNova:= SActual NoAfegirObjecte ProcessarNouNode FSI FMENTRE RETORNA(SOptima) FFUNCIO

ACCIO Inicialitzar

Crear(q) ProfitLlindar:= 0 ProfitMaxim:= SumarProfits(Candidats, 1, Pes) SOptima:= <<>, 0, 0, 0, ProfitMaxim> SActual:= <<>, 0, 0, 0, ProfitMaxim> Encua(q, SActual) FACCIO

5. Backtracking

- 41 -

FUNCIO SumarProfits(Candidats: TaulaObjectes; i,Pes: Enter) RET Enter VAR j, Profit, PesAcumulat: Enter FVAR

Profit:= 0 PesAcumulat:= 0 j:= i MENTRE ((j ≤ NObjectes) AND (PesAcumulat < Pes)) FER PesAcumulat:= PesAcumulat + Candidats[j].Pes Profit:= Profit + Candidats[j].Profit {profit per exces} j:= j+1 FMENTRE RETORNA(Profit) FFUNCIO

ACCIO AfegirObjecte VAR i: Enter FVAR

i:= SNova.NObjectes + 1 SNova.NObjectes:= i SNova.Objectes[i]:= Cert SNova.Pes:= SNova.Pes + Candidats[i].Pes SNova.ProfitMinim:= SNova.ProfitMinim + Candidats[i].Profit FACCIO

ACCIO NoAfegirObjecte VAR i: Enter FVAR

i:= SNova.NObjectes + 1 SNova.NObjectes:= i SNova.Objectes[i]:= Fals SNova.ProfitMaxim:= SNova.ProfitMaxim - Candidats[i].Profit FACCIO

ACCIO ProcessarNouNode

SI Acceptable AND PotGenerarSolucioMillor LLAVORS SI SolucioCompleta AND EsSolucioMillor LLAVORS SOptima:= SNova


- 42 -

ProfitLlindar:= SNova.Profit ALTRASI (NO SolucioCompleta) LLAVORS Encua(q, SNova, SNova.ProfitMaxim) FSI SI LlindarMillor LLAVORS ActualitzarLlindar FSI FSI FACCIO


RETORNA(SNova.Pes ≤ Pes) FFUNCIO

FUNCIO EsPotTrobarSolucioMillor RETORNA Boolea

RETORNA(SNova.ProfitMaxim > ProfitLlindar) FFUNCIO


RETORNA(SNova.NObjectes = NObjectes) FFUNCIO

FUNCIO EsSolucioMillor RETORNA Boolea

RETORNA(SNova.Profit > SOptima.Profit) FFUNCIO

FUNCIO LlindarMillor RETORNA Boolea

RETORNA (SNova.ProfitMinim > ProfitLlindar) FFUNCIO

ACCIO ActualitzarLlindar

ProfitLlindar:= SNova.ProfitMinim FACCIO

En la formulació anterior s’ha construit una solució composta d’un conjunt de booleans, que indiquen si un determinat objecte forma part o no de la solució. Aquest plantejament ha degenerat l’algoritme resultat ja que cada node pot tenir dos fills, que corresponen a posar o no l’objecte

5. Backtracking

- 43 -

corresponent al nivell considerat. Cal remarcar que l’algoritme suposa una entrada ordenada decreixenment per la relació entre profit i pes.

El profit d’una solució també serveix per descartar aquells nodes que no arriven a uns mínims. Cal remarcar el fet que a més d’existir la solució òptima, existeix una variable que guarda el profit mínim que es segur que s’aconseguirà per tal de retallar aquells nodes que no puguin donar aquest valor. Aquest llindar de profit és un valor estimat, ja que en treballar per nivells i tenir solucions de mida fixa (el nombre d’objectes) no s’aconsegueix un resultat fins que s’han generat diversos nodes.

Um exemple d’execució amb n = 4, pes màxim de la motxilla de 15, i objectes de pesos 2, 4, 6 i 9 i profits de 10, 10, 12 i 18, dona lloc a la següent taula:

Node Objectes Pes Profit valors total vàlid valors mínim màxim llindar vàlid 1 ? - 0 √ - 0 50 0 √ 2 1, ? 2 2 √ 10 10 50 10 √ 3 -, ? - 0 √ - 0 40 10 √ 4 1, 2, ? 2, 4 6 √ 10, 12 22 50 22 √ 5 1, -, ? 2 2 √ 10 10 40 22 √ 6 -, 2, ? 4 6 √ 10 10 40 22 √ 7 -, -, ? - 0 √ - 0 30 22 √ 8 1, 2, 3, ? 2, 4, 6 12 √ 10, 10, 12 32 50 32 √ 9 1, 2, -, ? 2, 4 6 √ 10, 12 22 38 32 √ 10 1, -, 3, ? 2, 6 8 √ 10, 12 22 40 32 √ 11 1, -, -, ? 2 2 √ 10 10 28 32 x 12 -, 2, 3, ? 4, 6 10 √ 10, 12 22 40 32 √ 13 -, 2, -, ? 2 2 √ 10 10 28 32 x 14 -, -, 3, ? 6 6 √ 12 12 30 32 x 15 -, -, -, ? 0 0 √ 0 0 18 32 x 16 1, 2, 3, 4 2, 4, 6,

9 21 x 10, 10, 12, 18 - - 32 -

17 1, 2, 3, - 2, 4, 6 12 √ 10, 10, 12 32 32 32 √ 18 1, 2, -, 4 2, 4, 9 15 √ 10, 10, 18 38 38 38 √ 19 1, 2, -, - 2, 4 6 √ 10, 10 20 20 38 x 20 1, -, 3, 4 2, 6, 9 17 x 10, 12, 18 - - 38 -


- 44 -

21 1, -, 3, - 2, 6 8 √ 10, 12 22 22 38 x 22 -, 2, 3, 4 4, 6, 9 19 x 10, 12, 18 - - 38 - 23 -, 2, 3, - 4, 6 10 √ 10, 12 22 22 38 x

A primer cop d’ull, sembla com si no es tingues cap guany pel fet d’utilizar la funció limitadora. El valor utilitzar com a llindar és un valor molt conservador, ja que s’utilitza com a tal el valor de profit ja aconseguit amb els objectes que s’han posat a la motxilla. Un valor millor s’obtindria en agafar el valor màxim aconseguible amb els objectes que resten utilitzant un algoritme voraç (fàcilment calculable). Aquest valor, en ser superior, podaria una major nombre de nodes.

TIPUS Objecte = TUPLA Pes: Enter Profit: Enter FTUPLA TaulaObjectes = TAULA [1..NObjectes] DE Objecte TaulaBooleans = TAULA [1..NObjectes] DE Boolea Solucio = TUPLA Objectes: TaulaBooleans NObjectes: Enter Pes: Enter Profit: Enter { valor ja aconseguit } ProfitMinim: Enter {valor minim abastable} ProfitMaxim: Enter {valor maxim abastable} FTUPLA CuaNodes = Cua(Solucio) FTIPUS

FUNCIO OmplirMotxilla(Candidats:TaulaObjectes, Pes:Enter) RET Solucio VAR SActual, SOptima, SNova: TuplaSolucio q: CuaNodes ProfitLlindar: Enter FVAR

Inicialitzar MENTRE NO CuaBuida(q) FER SActual:= Primer(q) Desencua(q) SI PotGenerarSolucioMillor LLAVORS SNova:= SActual AfegirObjecte ProcessarNouNode

5. Backtracking

- 45 -


ACCIO Inicialitzar VAR ProfitMinim, ProfitMaxim: Enter

Crear(q) ProfitLlindar:= 0 ProfitMaxim:= SumaMaxima(Candidats, 1, Pes) ProfitMinim:= SumaMinima(Candidats, 1, Pes) SOptima:= <<>, 0, 0, 0, 0, 0> {no es consideren les estimacions} SActual:= <<>, 0, 0, 0, ProfitMinim, ProfitMaxim> Encua(q, SActual) FACCIO

FUNCIO SumaMaxima(Candidats: TaulaObjectes; i,Pes: Enter) RET Enter { aquesta funcio calcula una cota superior del profit aconseguible amb els objectes que resten per posar a la motxilla utilitzant un metode vorac. el metode consisteix en posar-hi aquells objectes que tenen mes profit per unitat de pes i afegir-hi un valor que asseguri que el valor retornat no sera mai inferior a l’aconseguible} VAR j, Profit, PesRestant: Enter FVAR

Profit:= 0 PesRestant:= Pes j:= i MENTRE ((j ≤ NObjectes) AND (PesRestant > 0)) FER SI (PesRestant < Candidats[j].Pes) LLAVORS Profit:= Profit + Candidats[j].Profit*PesRestant/Candidats[j].Pes PesRestant:= 0 ALTRAMENT Profit:= Profit + Candidats[j].Profit PresRestant:= ResRestant - Candidats[j].Profit FSI j:= j+1


- 46 -

FMENTRE RETORNA(Profit) FFUNCIO

FUNCIO SumaMinima(Candidats: TaulaObjectes; i,Pes: Enter) RET Enter { aquesta funcio calcula una cota inferior del profit aconseguible amb els objectes que resten per posar a la motxilla utilitzant un metode vorac. el metode consisteix en posar-hi aquells objectes que tenen mes profit per unitat de pes } VAR j, Profit, PesRestant: Enter FVAR

Profit:= 0 PesRestant:= Pes j:= i MENTRE ((j ≤ NObjectes) AND (PesRestant > 0)) FER SI (PesRestant ≥ Candidats[j].Pes) LLAVORS Profit:= Profit + Candidats[j].Profit PesRestant:= PesRestant - Candidats[j].Pes FSI j:= j+1 FMENTRE RETORNA(Profit) FFUNCIO

ACCIO AfegirObjecte VAR i, ProfitMinim, ProfitMaxim, PesRestant: Enter FVAR

i:= SNova.NObjectes + 1 SNova.NObjectes:= i SNova.Objectes[i]:= Cert SNova.Pes:= SNova.Pes + Candidats[i].Pes SNova.Profit:= SNova.Profit + Candidats[i].Profit ProfitMinim:= SumaMinima(Candidats, i+1, Pes-SNova.Pes) SNova.ProfitMinim:= SNova.Profit + ProfitMinim ProfitMaxim:= SumaMaxima(Candidats, i+1, Pes-SNova.Pes) SNova.ProfitMaxim:= SNova.Profit + ProfitMaxim FACCIO

ACCIO NoAfegirObjecte VAR i: Enter FVAR

5. Backtracking

- 47 -

i:= SNova.NObjectes + 1 SNova.NObjectes:= i SNova.Objectes[i]:= Fals SNova.Profit:= SNova.Profit + Candidats[i].Profit ProfitMinim:= SumaMinima(Candidats, i+1, Pes-SNova.Pes) SNova.ProfitMinim:= SNova.Profit + ProfitMinim ProfitMaxim:= SumaMaxima(Candidats, i+1, Pes-SNova.Pes) SNova.ProfitMaxim:= SNova.Profit + ProfitMaxim FACCIO


SI Acceptable AND PotGenerarSolucioMillor LLAVORS SI SolucioCompleta AND EsSolucioMillor LLAVORS SOptima:= SNova ProfitLlindar:= SNova.Utilitat ALTRASI (NO SolucioCompleta) LLAVORS Encua(q, SNova) FSI SI LlindarMillor LLAVORS ActualitzarLlindar FSI FSI FACCIO


RETORNA(SNova.Pes ≤ Pes) FFUNCIO

FUNCIO PotGenerarSolucioMillor RETORNA Boolea

RETORNA(SNova.ProfitMaxim > ProfitLlindar) FFUNCIO


RETORNA(SNova.NObjectes = NObjectes) FFUNCIO

FUNCIO EsSolucioMillor RETORNA Boolea

RETORNA(SNova.Profit > SOptima.Profit) FFUNCIO


- 48 -

FUNCIO LlindarMillor RETORNA Boolea

RETORNA (SNova.ProfitMinim > ProfitLlindar) FFUNCIO

ACCIO ActualitzarLlindar

ProfitLlindar:= SNova.ProfitMinim FACCIO

Node Objectes Pes Profit valors total vàlid valors mínim màxim llindar vàlid 1 ? - 0 √ - 32 38 32 √ 2 1, ? 2 2 √ 10 32 38 32 √ 3 -, ? - 0 √ - 22 32 32 √ 4 1, 2, ? 2, 4 6 √ 10, 12 32 38 32 √ 5 1, -, ? 2 2 √ 10 22 36 32 √ 6 -, 2, ? 4 6 √ 10 22 32 32 √ 7 -, -, ? - 0 √ - 30 30 32 x 8 1, 2, 3, ? 2, 4, 6 12 √ 10, 10, 12 32 38 32 √ 9 1, 2, -, ? 2, 4 6 √ 10, 12 38 38 38 √ 10 1, -, 3, ? 2, 6 8 √ 10, 12 22 36 38 √ 11 1, -, -, ? 2 2 √ 10 28 28 38 x 12 -, 2, 3, ? 4, 6 10 √ 10, 12 22 32 38 x 13 -, 2, -, ? 2 2 √ 10 28 28 38 x 14 1, 2, 3, 4 2, 4, 6,

9 21 x 10, 10, 12, 18 - - 38 -

15 1, 2, 3, - 2, 4, 6 12 √ 10, 10, 12 32 32 38 x 16 1, 2, -, 4 2, 4, 9 15 √ 10, 10, 18 38 38 38 √ 17 1, 2, -, - 2, 4 6 √ 10, 10 20 20 38 x 18 1, -, 3, 4 2, 6, 9 17 x 10, 12, 18 - - 38 - 19 1, -, 3, - 2, 6 8 √ 10, 12 22 22 38 x

Un plantejament alternatiu, es podria realitzar utilitzant una cua de prioritat:

TIPUS ... {tot el que no es posi, es igual que el cas anterior} CuaNodes = CuaPrioritat(Solucio, Enter) FTIPUS

5. Backtracking

- 49 -

FUNCIO OmplirMotxilla(Candidats:TaulaObjectes, Pes:Enter) RET Solucio VAR SActual, SOptima, SNova: TuplaSolucio q: CuaNodes iObjecte, ProfitLlindar: Enter FVAR

Inicialitzar MENTRE NO CuaBuida(q) FER SActual:= Primer(q) Desencua(q) SI (SActual.ProfitMaxim > ProfitLlindar) LLAVORS SNova:= SActual AfegirObjecte ProcessarNouNode


ACCIO Inicialitzar

Crear(q) ProfitLlindar:= 0 ProfitMaxim:= SumarUtilitats(Candidats, 1, Pes) SOptima:= <<>, 0, 0, 0, ProfitMaxim> SActual:= <<>, 0, 0, 0, ProfitMaxim> Encua(q, SActual, ProfitMaxim) FACCIO

...


SI Acceptable AND PotGenerarSolucioMillor LLAVORS SI SolucioCompleta AND EsSolucioMillor LLAVORS SOptima:= SNova ProfitLlindar:= SNova.Profit ALTRASI (NO SolucioCompleta) LLAVORS Encua(q, SNova, SNova.ProfitMaxim)


- 50 -

FSI SI (SNova.ProfitMinim > ProfitLlindar) LLAVORS ProfitLlindar:= SNova.ProfitMinim FSI FSI FACCIO

...

L’algoritme està basat en una cua de prioritat de manera que sempre es treballa amb els nodes que poden donar lloc a més profit. La funció principal disposa d’un bucle controlat pel nombre d’objectes que resten a l’estructura de dades, de manera que quan no queden més objectes a l’estructura de dades, finalitza l’algoritme. Com que l’estructura de dades retorna els objectes de forma prioritzada, seria millor cosa com a condició de control que el primer element retornat tingues un profit màxim superior al llindar, cosa que permetria descartar tots els elements finals de l’estructura.

Node Objectes Pes Profit valors total vàlid valors mínim màxim llindar vàlid 1 ? - 0 √ - 32 38 32 √ 2 1, ? 2 2 √ 10 32 38 32 √ 3 -, ? - 0 √ - 22 32 32 √ 4 1, 2, ? 2, 4 6 √ 10, 12 32 38 32 √ 5 1, -, ? 2 2 √ 10 22 36 32 √ 8 1, 2, 3, ? 2, 4, 6 12 √ 10, 10, 12 32 38 32 √ 9 1, 2, -, ? 2, 4 6 √ 10, 12 38 38 38 √ 14 1, 2, 3, 4 2, 4, 6,

9 21 x 10, 10, 12, 18 - - 38 -

15 1, 2, 3, - 2, 4, 6 12 √ 10, 10, 12 32 32 38 x 16 1, 2, -, 4 2, 4, 9 15 √ 10, 10, 18 38 38 38 √ 17 1, 2, -, - 2, 4 6 √ 10, 10 20 20 38 x

5. Backtracking

- 51 -

4. EXERCICIS

1.- El problema de la motxilla. Tenim una col·lecció de n objectes que cal col·locar en una caixa que resisteix un pes màxim M. L’objecte i té un pes pi i un valor vi. Dissenyar un algorisme que

trobi aquell conjunt d’objectes de la col·lecció tal que la suma dels seus pesos no superi M i la suma dels seus valors sigui màxima.

2.- El convit. S’han de distribuir n convidats en una taula on hi ha lloc per n comensals. Es disposa d’una funció Adjacent(i,j) que retorna cert si els llocs i i j són adjacents i fals si no ho són. També hi ha una funció Afinitat(k,l) que retorna un valor comprès entre 0 i 10 segons el grau d’afinitat que els convidats k i l tinguin entre si (0 indica aversió profunda i 10 simpatia desbordant). Les funcions Adjacent(i,j) i Afinitat(k,l) són simètriques.

Dissenyeu, segons el mètode d’assaig i error, un algorisme que calculi la distribució de convidats a la taula que optimitza el seu benestar. Aquest benestar es calcularà sumant les Afinitats dels comensals asseguts en posicions adjacents.

3.- Els matrimonis estables. Tenim dos conjunts disjunts A i B, de n elements cada un. Es demana trobar un conjunt de n parelles (a,b), tals que a ∈ A i b ∈ B, que satisfacin la restricció coneguda amb el nom de matrimonis estables. Suposeu que A és un conjunt d’homes i B és un conjunt de dones. Cada home i cada dona estableixen les preferències que tenen entre els seus possibles acompanyants, per exemple, numerant-los de 1 a n. Si s’escullen n parelles de manera que hi hagi algun home i alguna dona que, sense estar aparellats entre ells, es prefereixin mútuament a les seves parelles respectives, l’assignació és inestable. Si no hi ha cap parella d’aquest tipus l’assignació és estable. Desenvolupar un algorisme que trobi tots els aparellaments estables.

4.- El cub de Rubik. Dissenyar un algorisme que trobi la seqüència més curta de manipulacions per passar d’una combinació a una altra en un cub de Rubik. Una manipulació equival a fer un quart de volta en una cara qualsevol.

5.- El problema de les reines. Es disposa d’un tauler d’escacs de dimensions n x n. Col·locar-hi n reines sense que es matin. Cal recordar que en el joc d’escacs dues reines es maten si estan a la


- 52 -

mateixa fila, a la mateixa columna o a la mateixa diagonal. El cas n = 8 és una particulatizació del problema.

6.- El salt del cavall. Es disposa d’un tauler d’escacs de n x n posicions. Cal fer passar un cavall per totes les posicions del tauler una vegada i només una, seguint els moviments que realitza aquesta figura en el joc d’escacs.

7.- (7/6/93) Cifras y letras. Cada dia de dilluns a divendres La 2 (TV-2) emet de 15 a 15:30 un programa concurs anomenat “CIFRAS Y LETRAS”. La part de xifres del concurs consisteix a fer el següent:

• Els concursants elegeixen sis valors numèrics d’entre quatre files. Les tres primeres files corresponen a valors entre 1 y 9 mentre que la darrera disposa dels valors 10, 25, 50, 75 i 100.

• A continuació la presentadora selecciona un número entre 100 i 999.

• A partir d’aquest moment els concursants disposen de 45 segundos per trobar una combinació que doni com a resultat el nombre seleccionat. Es poden utilitzar els sis valors i posar-hi entre ells les operacions +, -, *, /, amb els parèntesis que es vulgui i en els llocs que es vulgui.

Exemple: Si els valors escollits pels concursants són 10, 50, 7, 8, 1, 3 i el seleccionat per la presentadora és el 557 es poden obtenir les següents combinacions:

10 10 + 50 10 + 50 + 7 (10 + 50) + 7 10 + (50 + 7) ... 10 * 50 10 * 7 10 * (50 + 7) (10 * 50) + 7 ... (10 + 50) * 7 - (3 + 1) (10 + 50) * (7 - 3 + 1) ...

fins a trobar una combinació que doni el resultat seleccionat que, en aquest cas correspont a:

5. Backtracking

- 53 -

50 * (8+3) + 7 50 * (10 + 1) + 7

En cas de no trobar el valor exacte es dona com a bona la millor aproximació, ja sigui per excés com per defecte.

Es demana: Fer un programa que utilizant un esquema de tempteig sistemàtic (backtraking) no recursiu simuli un concursant.

• Se suposa que els valors escollits pels concursants estaran en un vector Operants: TAULA [1..6] DE Enter (els dos primers corresponen a la quarta fila i les restants a xifres de la restants files) i el valor seleccionat per la presentadora estarà en una variable Resultat: Enter.

• Per a que el programa no sigui molt complex se dispone de la següent acció:

ACCIO Evalua (OpEnt: TAULA [1..6] DE Enter; OperaEnt: TAULA [1..5] DE '*', '/', '+', '-'; NumOpent: Enter; Resultat: Enter; VAR Millor: Real; VAR Combinacio: Cadena[100])

que a partir d’una combinació de xifras y operadors, a més del resultat que es vol obtenir, retorna la millor aproximació i la cadena amb la fórmula de la millor aproximació. Així, en el exemple anterior, si s’entra amb:

OpEnt = [10, 50, 7, 3, ?, ?] OperaEnt = [+, *, +, ?, ?] NumOperant = 4 Resultado = 557

evaluarà:

10 + 50 * 7 + 3 (10 + 50) * 7 + 3 10 + (50 * 7) + 3 10 + 50 * (7 + 3) (10 + 50) * (7 + 3) (10 + 50 * 7) + 3 10 + (50 * 7 + 3)


- 54 -

donant com a resultat:

Millor = 560 Combinacio = '10 + 50 * (7 + 3)'

Nota: no cal optimitzar el procés.

8.- (5/9/94) Generació de seqüència. Disenyar un algoritme recursiu que generi totes les seqüencies de N elements que no contengn subseqüències adjacents (de qualsevol longitut) que siguin iguals. Els elements de les seqüències seran els M primers nombres naturals (M<<N).

M, N Secuencias correctas: Secuencias incorrectas 3, 5 12321 12323, 12123 3, 6 132123 132122, 132132 3, 7 1232132 1232121, 1231231

9.- (17/1/94) La tria de despatxos El personal de l’empresa Estam Pocs i Sols, que és la delegació que té a Riumorts la multinacional Unitat de Ganancials, es vol traslladar a les noves oficines. Els N despatxos d’aquestes noves oficines es troben disposats de forma alineada a un costat d’un pasadis i, per motius arquitectònics, tenen capacitats dierents. La direcció de l’empresa vol optimitzar la colocació dels seus empleats en els despatxos del nou edifici. Per això vol colocar el personal dels M departaments de l’empresa de forma que en un mateix despatx no hi hagi persones de departaments diferents i que el personal d’un mateix departament ocupi despatxos contigus. Es pot suposar que:

N. de despatxos: N. Persones per despatx: PDesi, 1 ≤ PDesi ≤ 5, ∑PDesi = T.

N de departaments: M. Persones per departament: PDepi, 1 ≤ PDepi ≤ 7, ∑PDepi = T.

Escriure l’algoritme per resoldre aquest problema. Es valorarà l’eficiència de la solució obtinguda. Discutir les diferències que hi hauria si els membres d’un mateix departament no haguessin d’ocupar despatxos contigus.

10.- (27/6/94) EL TETRIS. El Tetris és un joc d’ordinador molt conegut (un exemple és la màquina del bar de l’Escola) en el que es disposa de 7 peces de formes diferents i de la mateixa mida (4 unitats) amb les que es vol ‘enrejolar’ una superficie sense que hi quedin forats. Les diferents peces poden ser girades angles multiples de 90˚, però no és possible invertir-les usant simetria axial

5. Backtracking

- 55 -

Es vol obtenir un algoritme que ompli una superficie rectangular de dimensions donades (AxB) amb un conjunt de n peces fixes i també donades, sabent que les peces ocupen tota la superfície de manera exacta (A*B = 4*n).

NOTA: L’algoritme complet serà molt llarg (encara que no difícil). Per tal de simplificar-lo, pot suposar-se un TAD amb les operacions pertinents i només implementar la representació i operacions-mostra (si una operación s’ha d’aplicar a cada tipus de peça o a cada posició de gir, una operació-mostra només haurà de tenir el códi per a un dels casos).

Nota per “adictes”: L’enunciat anterior suposa algunes simplificacions respecte al joc del Tetris real. Aquestes simplificacions cal que siguin respectades per resoldre l’exercici.

Girs possibles Simetria (no!)

Peces del TetrisSOLUCIÓ

A=B=6, n=9

11.- (6/6/94) Cercar la ruta. L’Excelentísim Ajuntament d’Entenim i Noendeixem ha decidit promoure la instalació d’un servei de metro dins de la seva zona urbana. La comisió urbanística d’aquest municipi ha fet un estudi per determinar la situació idónia de les diferents estacions de la xarxa i el seu conexionat. A partir d’aquest estudi (en el que s’han contemplat aspectes tan diversos como poden ser la densitat de població de les diferents zones, la localizació dels principals serveis de la ciutat o la residència dels regidors del partit en el poder) s’ha obtingut el nombre i la situació de les diferents estaciones necessàries per donar un correcte servei a tota la comunitat, així como el recorregut de les diferents línies necessàries.

Desenvolupar un algoritme que, a partir de dues estacions, determini el recorregut a realizar entre elles de manera que es minimitzi el nombre d’estacions visitades (es considera que el temps del


- 56 -

viatge és proporcional al nombre d’estacions visitades). Existeixen estacions d’enllaç entre les línies (estacions per les que hi pasen diverses línies), que caldrà contabilitzar-les com a dues estacions en cas de realitzar un intercanvi entre dues línies.

Es considera coneguda la llista de estacions (taula d’estacions) i els recorreguts de les diferents línies (taula de taula d’estacions). Per guardar els recorreguts pot usar-se una taula com la següent:

Líniaprimera

C

C

D B

BA

Estació A

Estació C

Estació B

Estació D

Taula de Recorreguts: Exemple d'una línia

Següent

Estació

Estació

Anterior

Esta

ció

A

Esta

ció

C

Esta

ció

B

Esta

ció

D

Lín

ia p

rim

era

11.- El problema del viatger. Un viatger ha de visitar un cert nombre de ciutats. Es coneixen les distàncies entre les diferents ciutats. Determinar la seqüencia de ciutats visitades que minimitza l’espai recorregut.

12- Optimització de terminis. Es disposa d’un conjunt de n tasques que necessiten una certa quantitat de temps per ser processades, que pot ser diferent entre elles. Cal realitzar-les de manera seqüencial. Cada tasca té associat un cert benefici que només s’obtè si es pot realitzar abans del termini que té fixat per ser acabada. Determinar la seqüencia de tasques que produeix un major benefici.

13.- (19/6/95) El viatjant europeu ric. Una empresa de la Nova Mancomunitat Europea té representació de les seves empreses a totes les capitals dels països que la formen (Alemania, Andorra, Anglaterra, Austria, Belgica, Dinamarca, Espanya, França, Grecia, Holanda, Irlanda, Italia, Luxenburg, Portugal) i la seva seu central a una de les capitals, Andorra la Vella. Un viatjant de l’empresa que treballa a la seu central vol recorrer totes les representacions que es troben a la resta de capitals i per això demana que es prepari un circuit de visites. Com que és una persona que li

5. Backtracking

- 57 -

agrada molt viatjar vol fer aquell recorregut que representi fer un major nombre de quilòmetres, sempre viatjant amb avió.

Es demana: realitzar un programa utilitzant el mètode d’assaig i error que determini la seqüencia de ciutats a visitar, passant un i només un sol cop per cadescuna d’elles, per tal de maximitzar la longitut del recorregut a realitzar. Se suposa que totes les ciutats disposen d’aeroport i que es conneixen les distàncies entre les diferents ciutats.

14.- (22/6/98) El cub rosegat. Es disposa d’un cub format per 27 cubs més petits (3 per costat). Un cuc vol fer un recorregut per tots els cubs petits de manera que comença pel cub de l’extrem superior dret de la cara frontal i acabi en el cub de l’extrem inferior esquerra de la cara posterior (l’oposat en diagonal). Només és possible passar d’un cub al veí seguint els eixos coordenats.

El cubs estan fets de fusta molt fàcil de rossegar, però existeixen unes separacions entre ells que són de material més dur. No totes les separacions tenen la mateixa duresa. La funció Duresa(IdCub1, IdCub2) retorna la duresa del material que hi ha entre dos cubs donats, donant valors entre 0 i 10 (i negatiu si no és possible el pas entre cubs). Evidentment, aquesta funció és conmutativa.

És demana:

• Declarar les estructures de dades necessàries per resoldre el problema.

• Quin és l’ordre de selecció dels candidats que permet accelerar l’obtenció d’una solució?

• Implementar un algoritme de backtracking que trobi el recorregut de duresa mínima SENSE tenir en compte aquest ordre òptim de l’apartat b).

• Fer una estimació de l’arbre de cerca/graf resultant.

15.- (2/6/98) Es disposa de 8 cubs diferents que tenen les cares de 7 colors: vermell, groc, verd, blau, gris, blanc o negre. El joc consisteix a formar un cub més gran com a unió dels 8 cubs petits de manera que cadescuna de les sis cares sigui d’un mateix color.

Es demana:

• Proposar una representació del tipus cub i les seves operacions (sense implementar-les).


- 58 -

• Implementar un algoritme que descobreixi totes les solucions del joc.

• Estimar l’ordre de l’arbre generat per descobrir totes les solucions.

• A quina estratègia correspondria un algoritme probabilista que fes el mateix?

16. (1/6/99) Es disposa d’una frase qualsevol a la qual s’ha fet un prectactament per treure’n els caràcters no alfabètics (no té massa importància com es fa aquest tractament, només cal recordar que la frase només conté lletres majúscules sense espais en blanc). Es vol crear un petit jeroglific per amagar aquesta frase a l’interior d’una matriu bidimensional. Les regles són molt simples:

• És comença en una casella qualsevol i s'hi posa la primera lletra de la frase.

• Es va escrivint cadescuna de les lletres de la frase en una casella adjacent a l'anterior (una de les vuit caselles adjacents).

• Si la casella adjacent ja es troba ocupada, només s’hi pot accedir si la lletra és la mateixa que ja conté.

• Si la casella adjacent és buida, pot ocupar-se per qualsevol lletra.

• S’acaba el jeroglífic quan es finalitza la frase.

Es demana:

• Dissenyar un algoritme que descobreixi una solució del problema anterior que tingui la mínima superfície (ull! superfície equival a alçada per amplada, amb les possibles caselles desocupades incloses).

• Fer una estimació del cost (mida de l�’arbre de cerca generat).

Nota: si s’estima convenient, es pot suposar l’existència d’un tipus MatriuSenseLimits a la qual es poden posar elements en qualsevol posició sense els límits (per sobre i per sota) que tenen les matrius estàtiques. En aquest nou tipus de dades es poden suposar operacions per posar elements (Posar(Matriu, PosX, PosY, Valor)), consultar elements (Consultar(Matriu, PosX, PosY) RET Valor), desocupar una posició (Desocupar(Matriu, PosX, PosY)), determinar la superficie (NFiles*NColumnes) ocupada (Superficie(Matriu) RET Enter) i qualsevol altre que s’estimi convenient. Evidentment, en ocupar i desocupar una posició, s’adapta la superficie ocupada en conseqüencia.

5. Backtracking

- 59 -

17. (23/6/99) El joc del dòmino té 28 fitxes diferents. Les fitxes són rectangulars i porten gravat a cada extrem un nombre entre 0 i 6. Seguint les regles del joc, les fitxes es col·loquen formant una cadena de tal manera que cada parella de fitxes consecutives té iguals els nombres corresponents als extrems que es toquen. Un exemple de cadena és el següent:

Es vol dissenyar un algorisme que determini la cadena de N fitxes que tingui la suma dels seus punts mínima, sense usar cap fitxa blanca.

És demana:

• Adjuntar una declaració de les estructures de dades necessàries.

• Implementar l’algoritme.

• Fer una estimació de l’arbre de crides que es genera.

introducciÓ als esquemes algoritmicsima.udg.es/docencia/3105ig0003/5.backtracking.pdf ·...

Documents