P9------------------------------------
P;        TECNICAS DE IA (IV)
P9------------------------------------P8

 (c) P:WarlordP8 1993


 Bueno, aquí estoy otra vez dando la
lata a los pocos que leen esto, pero
en fin ... es que soy un "masoka".


 Bueno, hoy voy rápido  y  sin ganas
de extenderme demasiado.  Hoy  voy a
dar el pseudocódigo  de un algoritmo
que  podéis  utilizar para buscar el
centro  de  algún dibujo, grafo o lo
que sea.


 Por ejemplo,  si  tenéis  20 puntos
situados en el mapa y queréis buscar
otro punto que sea el  centro  en el
sentido P<MINIMAXP8, esto  es, un  punto
que  nimimice  la  máxima  distancia
podéis resolverlo mediante este al-
goritmo.

 Un ejemplo:

P:           A   3    B
            O------O
          1/      /1
          O------O
         C   2   D
P8

 Tenemos 4 ptos, A,B,C y D.

 La tabla de distancias es:

P: d(A,A)=d(B,B)=d(C,C)=d(D,D)=0
 d(A,B)=d(B,A)=minimo(3,1+2+1)=3
 d(A,C)=d(C,A)=minimo(1,3+1+2)=1
 d(A,D)=d(D,A)=minimo(3+1,1+2)=3P8
 etc....

  Si  queremos que el centro sea uno
de  los  puntos , la programación de
esto es bastante fácil, el  problema
es que el centro no sea uno de estos
puntos A,B,C o D, sino que pueda ser
un punto a distancia 1 de A y que se
encuentra en el camino que une A-B.

 Como podéis  ver,  esto  vale  para
cualquier cosa:demos,  juegos .... y
resolver  esto  no  es nada pero que
nada fácil. Yo he programado el  me-
jor algoritmo que he encontrado.  Se
llama P<METODO MODIFICADO DE HAMIKIP8  y
es dificilísimo de  programar  (aun-
que no os lo parezca)  ya que se re-
suelve  geometricamente   (dibujando
líneas y hallando puntos  de corte).
Yo lo he resuelto, pero  bajo  cier-
tas condiciones que siempre se  sue-
len dar en la  práctica, como es que
la distancia  de A a B sea igual que
la de B a A, y algunas mas que co-
mento en el source ... bien, ahí va:

 Como veréis es facilito de entender
(jo, jo).Si alguien está MUY intere-
sado en  que  se  lo explique, puede
contactar  conmigo, pero  sólo si de
veras está muy interesado o lo nece-
sita para algo:P? Apdo 232,San Fernan-
do 11100 (Cádiz)P8
/*P:BUSQUEDA DE CENTRO MEDIANTE EL AL-
GORITMO MODIFICADO DE HAMIKIP8

(c)Warlord/Ims, 1993
(para mi próximo juego de estrategia
(je,je...)
*/

/* Programado en un VAX
esto  es  pseudocódigo. Creo que tal
como está debería funcionar en el
Lattice C con pocas variaciones
*/

#include "stdio.h"
#include "stdlib.h"
#include "float.h"

float lista[100];
int nver=0,indice[100];
main()
{
float p,vk,h,h1,h2,
      l[100][100], pcorte[100],
      posicion,minpos,minra;
float d[100,100],d1,d2,corte(),
      minimo(),maximo();
int i=0,j=0,k=0,nodo1,nodo2,q;

/* INTRODUCCION DE DATOS */

 printf(" Dame el número de vertices:
        ");
scanf("%d",&nver);
printf(" Gracias. Ahora introduzca
las longitudes de los arcos (Cij)
 \n");
 for (i=1;i<=nver;i++){
  for (j=i+1;j<=nver;j++){
   if (i==j){
    l[i][j]=999999999;
    j++;
    }
   else{
    printf("C(%d,%d)= ",i,j);
    scanf("%f",&d[i][j]);
    l[i][j]=d[i][j];
/*    printf("Estan conectados?
    (si=1, no=0):"); 
      scanf("%d",&q);*/
    if (q==0) l[i][j]=999999999;
   }
  }
 }


 h=0.0;
 h2=999999999;
 for(i=1;i<=nver;i++){
  for(j=i+1;j<=nver;j++){
   for(k=1;k<=nver;k++){
   d1=d[k][i];
   d2=d[k][j];
   printf("%f %f",d1,d2);
    h1=v[k]*minimo(d1,d2);
    if (h1 > h){
     h=h1; /*
    }
   }
   printf("arco %d %d ",i,j);
   h=h+(1/2)*d[i][j];
   h2=minimo(h,h2);
   h=0;
  }
 }
   h=0;
 for (i=1;i<=nver;i++){
  for (j=i+1;j<=nver;j++){
   for (k=1;k<=nver;k++){
   d1=d[k][i];d2=d[k][j];
    h1=minimo(d1,d2);
    if (h1>h) h=h1;
   }
   if (h>=h2){
    l[i][j]=99999999;
    printf("Descartamos el arco
    %d->%d\n",i,j);
   }
  }
 }

/*P:AQUI EMPIEZA EL METODO DE HAMIKIP8*/

 /* Bien, esta parte del algoritmo
 sólo es válida para el caso de que
 los vértices tengan todos pesos 1.
 En caso de solución múltiple, sólo
 detectará una
 

 h=0;h1=0;h2=0;
 for (i=1;i<=nver;i++){
  for (j=1;j<=nver;j++){
   if (l[i][j] !=999999999){
  /*ie, no ha sido decartado*/
    for (k=1;k<=nver;k++){
     pcorte[k]=corte(1,d[j][k],-1,
   d[i][j]+d[i][k]);/*corte Ti,Ti'*/
     h1=maximo(h1,d[j][k]);
     h2=maximo(h2,d[i][k]);
    }
    h=maximo(h1,h2);
    posicion=0; /* Inicialmente, la
   mejor solucion esta a distancia 0
   del nodo j*/    

for (k=1;k<=nver;k++){
     lista[i]=d[j][k];
     indice[i]=k;
    }
    ordena (1,nver);
    
    for(k=nver-1;k>=1;k--){
     p=corte(-1,d[i][j]+d[i]
   [indice[k+1]],1,d[j][indice[k]]);
     if (p<pcorte[indice[k+1]]){ /*
      if (p<h){
       h=d[i][j]+d[i][indice[k]];
       posicion=p;
      }
      else{
       indice[k]=indice[k+1]; 
      }
     }
    }
  printf("En el arco %d->%d\n",i,j);
  printf(" El minimo se encuentra a
    distancia %f del nodo %d\n",
    posicion,j);
    printf(" El radio es %f\n",h);
    if (h<minra){
     h=minra;minpos=posicion;
     nodo1=i;nodo2=j;
    }
   }
  }
 }
 printf("EL RESULTADO FINAL ES:\n");
 printf(" El centro esta en el arco
 que une %d con %d",i,j);
 printf(" A distancia %f de este
 ultimo",posicion);
 printf(" Y su radio es: %f",minra);

/*Fin del programa principal*/

}
/* Funcion minimo*/
 float minimo (x,y)
 float x,y;
{
 y= (x<y) ? x : y;
 return(y);
}
/* Funcion maximo*/
 float maximo (x,y)
 float x,y;
{
 y= (x>y) ? x : y;
 return(y);
}
/* Esta funcion da el punto
 de corte de dos rectas,
 almacenadas de laforma:
 y=ax+b e y=cx+d
*/
 float corte (a,b,c,d)
 float a,b,c,d;
{
 float z;
 z=(d-b)/(a-c);
 return (z);
}
/* FUNCION ORDENAR
por metodo Quick"

ordena(izqda,dcha)
 int izqda,dcha;
 {
 int i=izqda,j=dcha;
 float x;
 x=lista[(izqda+dcha)/2];
 while (i<=j)
 {
  while (lista[i]<x) i++;
  while (x<lista[j]) j--;
   if (i<=j){
    intercambia(&lista[i],&lista[j],
    &indice[i],&indice[j]);
    j--;i++;
   }
  }
  if (izqda<j) ordena (izqda,j);
  if (i<dcha) ordena (i,dcha);
 }

intercambia (a,b,c,d)
 int *a,*b,*c,*d;
 {
 int e;
 e=*a;*a=*b;*b=e;
 e=*c;*c=*d;*d=e;
 }