Algoritmo de la Tarta

Hola a todos:

Bien , hace poco leyendo un libro que pille ,de teoría de juegos , vi una algoritmo que me gusto bastante y que de lo sencillo que es de manera conceptual , me pareció curioso lo intente implementar y me lleve una desilusión por que es mas complejo de lo que yo pensé.

La cosa es muy sencilla dos niños y una trata , vamos a poner nombre y caras a ambos niños , EL primero se llama Pepe y el Otro Alfonso ( los mimos del dilema del prisionero) , están solos en casa ,Jose Carlos los ha dejado para ir a por unas cervezas para ver el partido, y les a dejado una trata de postre que ninguno puede tocar, el problema es el siguiente como repartir la trata de manera justa.

Cada uno no dice que es lo que quiere, cuando llega la hora Jose coge el cuchillo y lo corta 50% para cada uno, ¿pero el reparto es justo?.

Pepe que es un goloso  solo quería la parte de chocolate pero no quería la nata ni el bizcocho.Alfonso quería algo de chocolate  y mas nata. A los dos el reparto les parece injusto.

El problema es fácil de decir pero no ver. Lo primero es el concepto de igual cantidad de pastel es justo , quizá uno tenga mas y otro menos ,sea mas justos. Y lo mas importante “ambos” estén mas contentos.

Como resultado de este reparto Pepe y Alfonso tiene lo que quería y Jose tiene cervezas mas pastel y los niños no les molestaría durante el partido.

Ahora la parte mas referida a el “BI” , yo trabajo con empresas y tengo que repartir beneficios como puedo repartir las cosas para que ambas partes  se queden igualmente satisfechas y así hacer negocio con ambas sabiendo mis margenes de ganancias.Este seria mas bien un algoritmo predictivo.

El objetivo de todo la rama de Teoría de Juegos que hago es siempre en base de que el Bi no da soluciones apriori solo aporteriori ,  cuando ya tienes datos lo que yo quiero plasmar es el hecho de conseguir un Bi mas activo mas greedy como yo le llamo y no ahora como yo le llamo lazy.

Mucha gente me pregunta , bueno mucha no, pero me pregunta en que tiene que ver esto con un sistema de reporting , primero es que RC no es solo reporting , yo no quiero hacer eso , lo que quiero es que pueda sacar informacuion de un reporte de la manera mas eficaz posible sin coste aun usuario.Por ahora solo saca informes pero pretendo que no sea solo eso.

Hay otro algoritmo que es parecido  , en forma , ” Hay una tarta y sois dos a repartir, tú y otro. Ambos queréis el mayor trozo de tarta posible “, Ahí entra dos conceptos nuevos Minimax y Maximin. Del que hablare mas adelante así de como usar Teoría de juegos en redes sociales (esto va por JC).

Problema de Toeria de juagos Aplicados

Bueno como un  amigete me comento en el post del dilema del prisionero ahi pongo una ejerciceo que me saque de  un libro que lei este verano sobre TG . Ahí va el enunciado la haber si alguien sabe sacarlo jaaaa jaaaa ,JC seguro y ¿el resto?.

Dos empresas de supermercados de sean montar sus nuevas instalaciones en un  area todav a
no explotada. Este  área comprende cuatro ciudades A,B,C y D, su localizacion viene dada en el
siguiente mapa:

mapa1

Si la primera empresa, con mayor prestigio, coloca su tienda mas cerca de una ciudad q
la otra empresa, se hace con el 80% del mercado; si la coloca a igual distancia que la segun
con el 60%; y si la construye mas alejada, el 40%. Las cuatro ciudades se consideran de ig
importancia y se quiere saber cual de las posibles localizaciones es la mas indicada.
Realizar el estudio de mercado, decidiendo en que ciudad se deberia localizar cada empresa.

Pues eso el guante queda lanzado 😀

PD: A peticion de JC.

jc

Busqueda Tabu

La búsqueda Tabú surge, en un intento de dotar de “inteligencia” a los
algoritmos de búsqueda local. Según Fred Glover, su primer definidor, “la
búsqueda tabú guía un procedimiento de búsqueda local para explorar el
espacio de soluciones más allá del óptimo local”. La búsqueda tabú toma de la Inteligencia Artificial el concepto de memoria y lo implementa mediante estructuras simples con el objetivo de dirigir la búsqueda teniendo en cuenta la historia de ésta, es decir, el procedimiento trata de extraer información de lo sucedido y actuar en consecuencia. En este sentido puede decirse que hay un cierto aprendizaje y que la búsqueda es inteligente. La búsqueda tabú permite moverse a una solución aunque no sea tan buena como la actual, de modo que se pueda escapar de óptimos locales y continuar estratégicamente la búsqueda de soluciones aún mejores.

Algoritmo

Supongamos que en cada punto solo pueden hacerse dos movimientos, hacia un estado con un número anterior o a un estado con un número posterior y supongamos que nuestra lista tabú es de tamaño 3.

Supongamos que inicialmente estamos puestos en el punto marcado con el número 1. De ahí se pueden hacer dos movimientos (hacia 0 y hacia 2). Se elige el mejor (hacia 2), denotemoslo como $mov(1,2)$ y se actualiza la lista tabú (inicialmente vacía). Registramos el movimiento inverso en la lista ($mov(2,1)$) para evitarlo en el futuro.

Problema

Bueno como en el otro , post he puesto un ejemplo que he encontrado en la Wikipedia.

El problema del Agente viajero es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.

La respuesta al problema es conocida, es decir se conoce la forma de resolverlo, pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado (Para una mayor profundidad en el tema ver el artículo NP-completos).

El problema del viajante (también conocido como problema del viajante de comercio o por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejor estudiado) en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, el TSP es uno de los más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otros problemas aparentemente mucho más complejos que han retado a los matemáticos desde hace siglos.

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación P = {c0,c2,…,cn − 1} tal que d_P=\sum_{i=0}^{N-1}{d[c_i,c_{i+1mod(N)}]} sea mínimo. La distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x, y] representa la distancia que hay entre la ciudad X y la ciudad Y

La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor distancia. El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y… 77.146 años en resolver el problema para sólo 20 ciudades.

Por ejemplo las rutas posibles entre 12 ciudades son (479 millones) 479.001.600 combinaciones y los caminos individuales entre ciudades son el sumatorio de las 12-1 ciudades es decir 66.

Se puede demostrar que el requerimiento de volver a la ciudad de partida no cambia la complejidad computacional del problema.

De ahí nos movemos hacia el estado 3 (el mejor y el permitido dada nuestra lista tabú actual) y después al 4, con lo que la lista tabú se llena con tres elementos: { $mov(4,3), mov(3,2), mov(2,1) $}.

El siguiente movimiento es peor en la función objetivo ($mov(4,5)$), pero es el mejor dentro de los permitidos por la lista tabú y por nuestro esquema de vecindad utilizado. Tambén provoca que se elimine el elemento más viejo que tiene la lista tabú (por estar llena). La lista tabú queda como: { $move(5,4), mov(4,3), mov(3,2) $}.

Este proceso continua hasta que finalmente salimos del mínimo local al movernos del estado 8 al 9.

Puntos:

  • Las soluciones dependen de como se actualiza $T$.
  • No hay condición de óptimo local.
  • Se busca la “mejor” solución en cada paso (función OPTIMO), en lugar de alguna opción que mejore la solución.

OPTIMO puede ser:

s \in S(x) - T) \end{displaymath}

OPTIMO da la mejor solución o la menos peor sujeta a la lista tabú.

En principio, se podría tomar alguna solución que mejore (en caso de que sea difícil encontrar la mejor), pero normalmente se sigue la estrategia más agresiva.

La razón principal es que los óptimos locales no presentan problemas.

Normalmente la lista tabú se implementa como una lista circular, añadiendo elementos en la posición 1 y eliminando los que sobrepasen la posición $t$ (para una $t$ fija).

Una forma efectiva de implementar la lista $T$ sería:

s = s_h \mbox{ para } h > k - t\} \end{displaymath}

donde $k$ es el número de iteración y $s^{-1}$ es el movimiento inverso de $s$.

Por lo que el paso de actualización de $T$ sería: = T - s^{-1}_{k-t} + s^{-1}_k$.

En general, lo que se trata de evitar en caer en estados solución previos.

Esto no quiere decir que se tenga que escoger una $t$ muy grande.

En la práctica $T$ no toma la forma anterior: (i) $s^{-1}$ previene un conjunto más grande de movidas, (ii) por consideraciones de memoria es deseable guardar sólo un subconjunto de atributos que caracterizan el movimiento.

Bajo estas condiciones, la lista tabú representa una colección de movidas $C_h$.

Cuando la lista $S - T = \emptyset$ se pueden eliminar los elementos más viejos de $T$ para permitir continuar con el proceso.

Dilema del Prisionero

try {
_uacct = “UA-4775371-3”;
urchinTracker();
} catch(err) {}
Bueno , como ya anuncia , he aquí un post basico de un problema que me interesa personalmente que es el dilema del prisionero.

Bien aqui va:

Imaginemos 2 prisioneros ( Ej: Mi amigo Pepe  As Nemesis y mi otro amigo Skiter ) .:D

Han hecho un delito, pero no hay pruebas suficientes para condenarlos, así que la policía opta por interrogarlos por separado y ver que pasa.

A cada uno , le hacen la misma pregunta .

– Si Nemesis confiesa y  Skiter no  , Skiter se lleva toda la pena y Nemesis se va de rositas.

– Si es al revés  , es Skiter el que se va de rositas.

-Si Nemesis y Skiter callan salen en 1/2 tiempo.

-Si ambos no callan salen  2/3 antes

Bien , ahora la parte mas teórica.

El dilema del prisionero es un ejemplo claro, pero atípico, de un problema de suma no nula. En este problema de teoría de juegos, como en otros muchos, se supone que cada jugador, de modo independiente, trata de aumentar al máximo su propia ventaja sin importarle el resultado del otro jugador.

Las técnicas de análisis de la teoría de juegos estándar, por ejemplo determinar el equilibrio de Nash [

f_i(x^*_{i}, x^*_{-i}) \geq f_i(x_{i},x^*_{-i}).

], pueden llevar a cada jugador a escoger traicionar al otro, pero curiosamente ambos jugadores obtendrían un resultado mejor si colaborasen.
Desafortunadamente , cada jugador está incentivado individualmente para defraudar al otro, incluso tras prometerle colaborar. Éste es el punto clave del dilema.

En el dilema del prisionero iterado, la cooperación puede obtenerse como un resultado de equilibrio. Aquí se juega repetidamente, por lo que, cuando se repite el juego, se ofrece a cada jugador la oportunidad de castigar al otro jugador por la no cooperación en juegos anteriores. Así, el incentivo para defraudar puede ser superado por la amenaza del castigo, lo que conduce a un resultado mejor, cooperativo.

Aquí un vídeo explicativo , pero algo basico.

Aquí ya algo mas serio una mini-reposrtaje para que podamos entender

Bueno , después de todo ,esto ¿ por que hacer un plugin ?.

Por varias razones la primera que nadie ha usado esta tecnologia , en el BI y es algo a tener encuenta como ya he comentado ,es el siguiente paso a dar, segunda por que si a una herramienta le das esta potencia puede analizar de una manera no habitual si le menreze la pena hacer un negocio con una empresa o no.

Bueno , el proximo post sera sobre el metodo plugin , y requisitos para poder hacer un plugin en redClover.

Saludos