Diagrama Estaño-Plomo
Eyvar Trejo Garrido Maestría en Ingeniería
Algoritmo de las N REYNAS
clc
close all
clear all
tic;
hold on
reinas=4;
x=-reinas:1:0;
yx=-reinas:1:0;
b=-reinas:0;
c=-reinas:0;
m=0;arbol={};visitado={};
%%%%%%%%%%%%%%%pinta el tablero
for i=1:length(b)
y=m*x+b(i);
plot(x,y);
x1=m*yx+c(i);
plot(x1,yx);
end
tablero = zeros(reinas,reinas);
%%%%%%%%%%%%%%%%%%
raiz=tablero;%nodo raiz
arbol(1)={raiz};%al principio de la lista
index_raiz=2;
index_vis=1;
flag=1;
inicio1=1;
inicio2=1;
while (flag==1)
%colisiones y siguiente movimiento
[iqx iqy]=find(9==tablero);%buscamos las reinas del tablero
queen=[iqx iqy];%reinas del tablero
if isempty(queen)%si no hay reinas
if inicio2==reinas%iniciamos 1 reina en la primer casilla
inicio1=inicio1+1;
inicio2=1;
end
if inicio1==reinas
inicio1=1;
end
tablero(inicio1,inicio2)=9;%la ponemos en el tablero
arbol(index_raiz)={tablero};%la metemos en la pila
visitado(index_vis)={tablero};
index_raiz=index_raiz+1;
index_vis=index_vis+1;
index_i=inicio1;index_j=inicio2;
posx=(-reinas+index_i)-.5;%pintamos en el tablero
posy=-index_j+.5;
text(posx,posy,'R');
inicio2=inicio2+1;
cond=0;
else
Eyvar Trejo Garrido Maestría en Ingeniería
fou=0;dodiag=0;
for i=1:reinas%recorremos todo el tablero
for j=1:reinas
cond=0;cont=0;
move_done=0;%condicion para movimientos repetidos
next_move=[i j];%siguiente posible jugada
if dodiag==0
diagonal=zeros(12*reinas,2);
for z=1:size(queen,1)
for m=1:reinas-1
diagonal(m+cont,1)=queen(z,1)+m;%diagonales
de colision
diagonal(m+cont,2)=queen(z,2)+m;
diagonal(m+1+cont,1)=queen(z,1)-m;%diagonales
de colision
diagonal(m+1+cont,2)=queen(z,2)-m;
diagonal(m+2+cont,1)=queen(z,1)-m;%diagonales
de colision
diagonal(m+2+cont,2)=queen(z,2)+m;
diagonal(m+3+cont,1)=queen(z,1)+m;%diagonales
de colision
diagonal(m+3+cont,2)=queen(z,2)-m;
cont=cont+reinas-1;
end
cont=cont+reinas-1;
end
dodiag=1;
end
for d =1:size(next_move,1)%virificamos las colisiones
for c=1:length(diagonal)%si choca en diagonal
if next_move(d,1)==diagonal(c,1)...
&& next_move(d,2)==diagonal(c,2)
cond=1;
index_i=next_move(1);index_j=next_move(2);
posx=(-reinas+index_i)-.5;
posy=-index_j+.5;
text(posx,posy,'C');
pause(.5);
text(posx,posy,'\color{white}\bfC','BackgroundColor',[1 1 1]);
[ix iy]=find(9==tablero);%pintamos en el
tablero
queens_in=[ix iy];
for n=1:size(queens_in,1)
index_i=queens_in(n,1);index_j=queens_in(n,2);
posx=(-reinas+index_i)-.5;
posy=-index_j+.5;
text(posx,posy,'R');
end
break;
end
end
if cond==1
break;
end
Eyvar Trejo Garrido Maestría en Ingeniería
end
for x=1:size(queen,1)
if next_move(1,1)==queen(x,1) ||
next_move(1,2)==queen(x,2)
cond=1;%si choca en fila o columna
index_i=next_move(1);index_j=next_move(2);
posx=(-reinas+index_i)-.5;
posy=-index_j+.5;
text(posx,posy,'C');
pause(.5);
text(posx,posy,'\color{white}\bfC','BackgroundColor',[1 1 1]);
[ix iy]=find(9==tablero);%pintamos en el
tablero
queens_in=[ix iy];
for n=1:size(queens_in,1)
index_i=queens_in(n,1);index_j=queens_in(n,2);
posx=(-reinas+index_i)-.5;
posy=-index_j+.5;
text(posx,posy,'R');
end
end
if cond==1
break;
end
end
if cond==1%si choca otra jugada
continue;
else
tablero(next_move(1),next_move(2))=9;%si no la
tomamos
move=tablero;
for t=1:length(visitado)%verificar si no es edo
visitado
ya_visitado=cell2mat(visitado(t));
if ya_visitado == tablero
move_done=1;%si ya fue visitado no lo metemos
a la lista
cond=1;
tablero(next_move(1),next_move(2))=0;
continue;
end
end
if move_done==0%si no es visiado lo pintamos y
agragamos a la lista
index_i=next_move(1);index_j=next_move(2);
posx=(-reinas+index_i)-.5;
posy=-index_j+.5;
text(posx,posy,'R');
fou=1;
pause(.3);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
arbol(index_raiz)={move};%lo ponemos al tope de
la lista
Eyvar Trejo Garrido Maestría en Ingeniería
visitado(index_vis)={move};%lo ponemos como edo
visitado
index_raiz=index_raiz+1;%incrementamos contador
index_vis=index_vis+1;
break;
end
end
end
if fou==1
break;
end
end
if cond==1%si no hay mas movimientos
index_raiz=index_raiz-1;
arbol{index_raiz}={};%borramos el ultimo de la lsita
tablero=cell2mat(arbol(index_raiz-1));%tomamos el de la pila
de la lista como estado inicial
[ix iy]=find(9==tablero);%pintamos en el tablero
queens_in=[ix iy];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
hold off
x=-reinas:1:0;
yx=-reinas:1:0;
b=-reinas:0;
c=-reinas:0;
m=0;
for i=1:length(b)%pintamos el tablero
y=m*x+b(i);
plot(x,y);
x1=m*yx+c(i);
plot(x1,yx);
hold on
end
%%%%%pintamos en el tablero las reinas
for n=1:size(queens_in,1)
index_i=queens_in(n,1);index_j=queens_in(n,2);
posx=(-reinas+index_i)-.5;
posy=-index_j+.5;
text(posx,posy,'R');
end
pause(.5);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%
%disp('No hay posibles. Retroceso')
else
tablero=move;%nueva jugada
solu=find(9==tablero);%verificar si ya llegamos a la solucion
if size(solu,1)==reinas%solucion termiar
flag=2;
disp('solucion encontrada');
end
end
end
end%continuar
toc;
Eyvar Trejo Garrido Maestría en Ingeniería
Algoritmo genético
clc;
clear all;
gen=input('Da el número de generaciones que deseas manejar: ');
n=input('Da el tamaño del individuo: ');
pob=input('Da el tamaño de la población: ');
pc_2=input('Da la probabilidad de cruce en escala de 1 a 9: (n*0.1)');
pc=pc_2*0.1;
probMut_2=input('Da la probabilidad de mutación en escala de 1 a 9:
(n*0.01) ');
probMut=probMut_2*0.01;
A=[];
for i=1:pob
for j=1:n
A(i,j)=round(rand); %generamos número aletorios para definir la
población matriz de pob*n
end
end
hold on;
%iniciamos generaciones de evolución
for g=1:gen
fprintf('Generación %d\n',g);
fprintf('Pob. Inicial\n');disp(A);
%generamos arreglo con enteros X
X=[];
for i=1:pob
X(i)=bin2dec(num2str(A(i,:)));%convertimos vector numerico a cadena y
éste de binario a sistema decimal
end
fprintf('X= ');disp(X);
%evaluamos x; f(x)=x^2 y obtenemos la sumatoria
fX=[]; sumatoria=0;
for i=1:pob
fX(i)=X(i)^2;
sumatoria=sumatoria+fX(i);
end
fprintf('fX= ');disp(fX);
%graficamos
if g==1
plot(X,fX,'+r');
else
plot(X,fX,'og');
end
%Obtenemos la probabilidad de selección
%Algoritmo Genetico Simple
Eyvar Trejo Garrido Maestría en Ingeniería
%Desarrollado por Luigi Pérez Calzada
%28/08/2012
%Download from: hrrp://puraslineas.com
probSel=[];
for i=1:pob
probSel(i)=fX(i)/sumatoria;
end
fprintf('Prob. Sel.= ');disp(probSel);
%obtenemos la probabilidad acumulada
probAcum=[]; probAcum(1)=probSel(1);
for i=2:pob
probAcum(i)=probAcum(i-1)+probSel(i);
end
fprintf('Prob. Acu.= ');disp(probAcum);
%obtenemos los valores aleatorios de r
R=[];
for i=1:pob
R(i)=rand;
end
fprintf('R= ');disp(R);
%obtenemos población intermedia
pobInt=[];
for i=1:pob
for j=1:pob
if probAcum(j)>R(i) %si prob.Acum(j)>r(i) tomamos al ind. si no
incrementamos j
pobInt(i,:)=A(j,:); %asignamos en la posicion i (de r) al nuevo
individuo de la pos. j
break;
end%end if
end %end for j
end%end for i
fprintf('Población Intermedia \n');disp(pobInt);
%Obtenemos prob. de cruza si es menor cruzamos, además de obtener el
punto
%Algoritmo Genetico Simple
%Desarrollado por Luigi Pérez Calzada
%28/08/2012
%Download from: hrrp://puraslineas.com
%de cruza y obtenemos generacion cruzada
pobCruz=[];
if (mod(pob,2)~=0)%si es impar la poblacion
pobCruz(pob,:)=pobInt(pob,:); %asignamos el ultimo elemento
directamente
end
for i=1:2:pob
probCruz=rand; %obtenemos la probabilidad de cruce
fprintf('probCruce=%f -- %f\n',probCruz,pc);
if(probCruz<pc) %si es menor cruzamos
ptoC=round(rand*n); %obtenemos el punto de cruce de forma aleatoria
>1 & <n
while ptoC>n-1 || ptoC<1
Eyvar Trejo Garrido Maestría en Ingeniería
ptoC=round(rand*n);
end%end while
fprintf('P.C.=%d\n',ptoC);
for j=1:n
if j>ptoC
pobCruz(i,j)=pobInt(i+1,j);
pobCruz(i+1,j)=pobInt(i,j);
else
pobCruz(i,j)=pobInt(i,j);
pobCruz(i+1,j)=pobInt(i+1,j);
end
end%end for
else
pobCruz(i,:)=pobInt(i,:);
pobCruz(i+1,:)=pobInt(i+1,:);
end%end probCruz < pc
if (mod(pob,2)~=0)
if i==pob-2 %si es impar la poblacion y estamos en el penultimo
elemento (de 2 en 2) rompemos
break;
end
end %end if mod
end
fprintf('Población Cruza\n');disp(pobCruz);
%obtenemos mutación
probMut=0.06;
pobMut=[];
for i=1:pob
for j=1:n
mutacion=rand;
if(mutacion<probMut)
fprintf('Si hay mutacion en la iter i=%d,j=%d; mutacion
fue=%f\n',i,j,mutacion);
pobMut(i,j)=(pobCruz(i,j)-1)^2;%obtenemos el contrario del
binario 0=1 y 1=0
else
pobMut(i,j)=pobCruz(i,j);%si no pasamos como tal
end
end
end
fprintf('Población Mutada\n');disp(pobMut);
A=pobMut;
%generamos arreglo con enteros X
X=[];
for i=1:pob
X(i)=bin2dec(num2str(A(i,:)));%convertimos vector numerico a cadena y
éste de binario a sistema decimal
end
fprintf('X= ');disp(X);
%evaluamos x; f(x)=x^2 y obtenemos la sumatoria
fX=[]; sumatoria=0;
for i=1:pob
fX(i)=X(i)^2;
Eyvar Trejo Garrido Maestría en Ingeniería
sumatoria=sumatoria+fX(i);
end
fprintf('fX= ');disp(fX);
end %end for generaciones
hold off;
%Algoritmo Genetico Simple
%Desarrollado por Luigi Pérez Calzada
%28/08/2012
%Download from: hrrp://puraslineas.com
%obtener el mejor de la última generación
mayor=0;
for i=1:pob
if fX(i)>=mayor
mayor=fX(i);
end
end
fprintf('El mejor de la última generación es: %f',mayor);
Eyvar Trejo Garrido Maestría en Ingeniería
