elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  IA para Mastermind.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: IA para Mastermind.  (Leído 8,494 veces)
Tachikomaia


Desconectado Desconectado

Mensajes: 1.413


Hackentifiko!


Ver Perfil
IA para Mastermind.
« en: 5 Febrero 2021, 09:13 am »

Mastermind
https://es.wikipedia.org/wiki/Mastermind

En mi caso no usaré colores sino números 0 o 1.

Creo que la solución es:
1- Generar árbol de acciones-reacciones (a las pistas).
2- Elegir código secreto.
3- Ver cuánto tarda el árbol en hallar el número dándole las pistas.
4- Ir al paso 2 hasta que no queden más códigos secretos.
5- Ir al paso 1 hasta que no queden más árboles.

El objetivo es hallar el árbol que adivine los números más rápido.
Sé que hay gente que lo ha hecho, pero por lo que he visto no he entendido.

Estoy trancado en la parte 1 :/

Gracias.


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: IA para Mastermind.
« Respuesta #1 en: 6 Febrero 2021, 16:30 pm »

Ya te he indicado en más de una ocasión que tus 'problemas' suelen tener que ver frecuentemente con combinatoria y teoría de grafos. Haz el esfuerzo por aprender algo al respecto (sin quejarte de que no lo entiendes, solo inténtalo, si no lo entiendes a la primera sigue leyendo y leyendo, llega un momento que tu cabeza tiene suficientes piezas y sin darte cuenta montas el puzzle y acabas por comprender las cosas...)

Esto no puede llamarse IA, por varias razones...
- Es lo suficientemente sencillo como para resolverlo mediante grafos y más eficientemente mediante autómatas.
- El juego acaba tras 8 intentos fallidos (un IA no puede 'aprender' con solo 8 jugadas). Todavía se le podría 'enseñar' partidas (miles) tratando de que al final fuere capaz de satisfacer una solución la mayor parte de las veces. ...pero incluso así es mucho más trabajo (manual) que resolverlo por las formas antedichas.
- La IA se suele reservar para sistemas donde la complejidad se escapa humanamente al análisis, o bien aunque no escape, su resolución conlleve un tiempo (tambien) humanamente inaceptable.

Voy a darte algunas pistas... a ver si logras hacer algo (aparte de protestar).
- De entrada descarta usar unos y ceros (solo complicarás las cosas, sabiendo  cuales son las reglas dle juego y que estas son finitas y de pequeño número), usa letras: siendo 8 bolas: ABCDEFGH
 Una jugada como ACDG supone usar las bolas cuya letra representan en el orden en que aparecen en la jugada (apuesta). Prácticamente todos los lenguajes aceptan tratamiento de textos con caracteres y números por muy básico que sea el lenguaje.
- Como solo son 4 bolas la solución, el número de posibilidades para ordenar 4 bolas son: 1*2*3*4 = 24, es decir aún siendo 4 bolas la solución pueden estar ordenadas de 24 maneras distintas. Resulta de interés determinar el mínimo número de apuestas en que puede hallarse la solución partiendo de un fallo total de orden (más adleante alargo un poquito más este caso, es el más interesante porque a otros casos (no a todos) se llega desde éste, luego resolviendo éste, 'por el camino' resuelves aquellos).
- Tras la apuesta del jugador (en la primera de ellas), hay solo 14 resultados distintos.
 es decir estos resultados son los nodos hijos del nodo raíz de un árbol.
Si las numeramos (por ejemplo para acogerlos en una enumeración, serían):
00 - 0 negras y 0 blancas  (equivale a -12- (4 negras con las bolas no jugadas, es deicr la próxima apuesta usa las 4 no usadas))
01 - 1 negra
02 - 1 blanca
03 - 2 negras
04 - 2 blancas
05 - 1 negra y 1 blanca
06 - 3 negras
07 - 3 blancas
08 - 2 negras y 1 blanca
09 - 2 blancas y 1 negra
10 - 2 negras y 2 blancas
11 - 3 negras y 1 blanca
12 - 4 negras               (fallan en el orden)
13 - 4 blancas              (hallado, fin de partida)
14 - 3 blancas y 1 negra NOTA: que este caso nunca puede darse, se añade solo por que no parezca un olvido... y hacer notar así su caso imposible.

Supongamos que tu primera apuesta fuera: ABCD y el resultado de la apuesta es 12 (4 negras)...
Lo más razonable con el resultado es cambiar solo 2 bolas en la siguiente apuesta, por ejemplo AB--> BA (también podrías cambiar 3 bolas de sitio o las 4, pero las combinaciones de los resultados posibles son más numerosas con tales casos). Por ello ciñámonos solo a considerar un cambio de solo 2 de ellas:
El nodo 10 tendría (en este caso) como hijos nodos a:
12 - 4 negras  ---> es decir sigue sin cambios, pero ahora sabemos que AB ocupan las posiciones 34 y CD las posiciones 12 (después de otra apuesta llegamos al caso 12 o 10, y con otra más al 10 (si antes no llegamos al 13 (la solución).
10 - 2 negras y 2 blancas  ---> caso de que el intercambio arroje a ambas a su orden correcto.  La siguiente apuesta resuelve el enigma: CD--> DC = resultado 11 (reseulto)
11 - 3 negras 1 blanca  ---> A o B es blanca.

...si vas descendiendo de forma exhaustiva caso por caso, finalmente tienes una forma arbórea de explorar los resultados para dirigir la siguiente apuesta y así poder  solucionarlo en el mínimo número de jugadas.
Nota que las resultados son siempre los mismos, por lo que al final se reduce a usar una y otra vez las mismas operaciones con resultados ya conocidos, donde lo que cambia es la información previa que ya hemos obtenido y que será conjugado con el nuevo resultado lo que derive a uno u otro nodo.
Asumo que el árbol incluso podría generarse en forma de Trie, donde la raíz es la solución y se alcanza siempre si el número de profundidad del nodo (actual) no es superior al número de jugadas máximas antes de dar por perdida la partida...
No me he parado a verificar si es posible ganar siempre en el númro de jugadas máximo (8), ni tengo previsto perder tiempo en ello. Creo que con el tiempo dedicado a responderte es más suficiente.

Desde el punto de vista de un autómata, habría que asignar estados con cada jugada: sugiero dotar de un valor de 5 por cada 'bola blanca' y un valor de 1 por cada 'bola negra'  (nota que un valor menor de 5 para blancas dejaría en la ambigüedad el resultado, pués 4 negras suman 4). El estado final del autómata con valor '20' señalaría el estado de aceptación.

Una IA podría ser alimentado con partidas completas (jugada a jugada), recibiendo como retroalimentación precisamente el valor numérico resultante. Si el número de jugadas es lo suficientemente grande, es probable que de una forma algo más monstruosa* acabara llegando a un esquema equivalente al árbol recién descrito (* las IA habitualmente consumen mucho más recursos de memoria (mientras se los entrena), que un sistema equivalente programado de forma manual).

Si no eres capaz de programar un esquema con árboles, ni con autómatas, me temo que tampoco serás capaz de crear una IA, que suele ser más complejo.

...aunque conociéndote un poco, asumo que tienes la mala costumbre de llamar IA, a procesos que no lo son (esto ya ocurre incluso en profesionales idiotizados).


« Última modificación: 6 Febrero 2021, 16:43 pm por Serapis » En línea

Tachikomaia


Desconectado Desconectado

Mensajes: 1.413


Hackentifiko!


Ver Perfil
Re: IA para Mastermind.
« Respuesta #2 en: 6 Febrero 2021, 18:10 pm »

Es muy difícil responder tu mensaje...

Ya te he indicado en más de una ocasión que tus 'problemas' suelen tener que ver frecuentemente con combinatoria y teoría de grafos. Haz el esfuerzo por aprender algo al respecto (sin quejarte de que no lo entiendes, solo inténtalo, si no lo entiendes a la primera sigue leyendo y leyendo, llega un momento que tu cabeza tiene suficientes piezas y sin darte cuenta montas el puzzle y acabas por comprender las cosas...)
Sinceramente si es muy largo o complicado prefiero hacer otra cosa.

Citar
Esto no puede llamarse IA, por varias razones...
Bueno, no sé, pero llega a aprender algo sin que yo se lo diga.

Citar
- Es lo suficientemente sencillo como para resolverlo mediante grafos y más eficientemente mediante autómatas.
¿Cómo es con grafos y autómatas?

Citar
- El juego acaba tras 8 intentos fallidos (un IA no puede 'aprender' con solo 8 jugadas).
Puse el título de Mastermind porque es muy parecido, pero no he puesto un límite a la cantidad de intentos.

Citar
- La IA se suele reservar para sistemas donde la complejidad se escapa humanamente al análisis, o bien aunque no escape, su resolución conlleve un tiempo (tambien) humanamente inaceptable.
Al parecer soy incapaz de resolver el problema por mí mismo.

Citar
- De entrada descarta usar unos y ceros (solo complicarás las cosas, sabiendo  cuales son las reglas dle juego y que estas son finitas y de pequeño número), usa letras: siendo 8 bolas: ABCDEFGH
¿Por qué dices que complico si estoy simplificando? 2 valores es más sencillo que 8. En todo caso puedo usar letras en vez de números si te parece mejor.

Citar
- Como solo son 4 bolas la solución, el número de posibilidades para ordenar 4 bolas son: 1*2*3*4 = 24
Calculo que en mi caso serían 1*2.

Citar
- Tras la apuesta del jugador (en la primera de ellas), hay solo 14 resultados distintos.
 es decir estos resultados son los nodos hijos del nodo raíz de un árbol.
En mi caso son 4:
0 posiciones correctas 0 posiciones equivocadas
01
10
20
11 no puede ser creo

Citar
Si no eres capaz de programar un esquema con árboles, ni con autómatas, me temo que tampoco serás capaz de crear una IA, que suele ser más complejo.
¿Entonces esto es un autómata?
Código
  1.   actions for fotograma 1
  2.      // Situación inicial.
  3.      BaseVS = 10;
  4.      // Guardar Situación inicial.
  5.      SitID = "S"+BaseVS;
  6.      set (SitID+"VS", BaseVS);
  7.      set (SitID+"C", "Ninguno");
  8.      C = 1;
  9.      // Variables de Unsolved situaciones.
  10.      U = 0;
  11.      Us = 0;
  12.   actions for fotograma 2
  13.      // Reset Situación. Aplicación.
  14.      VS = BaseVS+C;
  15.      // ¿Sol?
  16.      if (20<VS) {
  17.         // Solución; iniciar mostrar lista.
  18.         List = C;
  19.         gotoAndPlay (4);
  20.         // Sino ¿la situación está anotada?
  21.      } else if (eval("S"+VS+"VS") == undefined) {
  22.         // No. Anotarla.
  23.         SitID = "S"+VS;
  24.         set (SitID+"VS", BaseVS);
  25.         set (SitID+"C", C);
  26.         Us = Us+1;
  27.         SitID = "U"+Us;
  28.         set (SitID+"VS", VS);
  29.      }
  30.   actions for fotograma 3
  31.      // La situación existe. ¿Modificar candidato es posible?
  32.      if (C<2) {
  33.         // Modificación de candidato.
  34.         C = C+1;
  35.         gotoAndPlay (2);
  36.      } else if (U<Us) {
  37.         // Usar Unsolveds.
  38.         U = U+1;
  39.         BaseVS = eval("U"+U+"VS");
  40.         C = 1;
  41.         gotoAndPlay (2);
  42.      } else {
  43.         // No hay Solución.
  44.         stop ();
  45.      }
  46.   actions for fotograma 5
  47.      SitID = eval("S"+BaseVS+"C");
  48.      BaseVS = eval("S"+BaseVS+"VS");
  49.      if (SitID != "Ninguno") {
  50.         List = SitID+" "+List;
  51.         gotoAndPlay (4);
  52.      } else {
  53.         stop ();
  54.      }

¿Cuales son los requisitos para que sea IA? Nota que en el título simplifiqué, en parte por no saber qué decir. ¿Lo que describí con números no lo es?

Al final has hablado bastante, gracias, pero no me ayudaste con la parte 1...

Yo a lo que he llegado por ahora es a:
Código___Árbol1___Árbol2___etc
________Tiempo que tarda el árbol en hallar el código.

Pero no sé cómo nombrar o crear a los árboles.
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: IA para Mastermind.
« Respuesta #3 en: 6 Febrero 2021, 20:01 pm »

Son varias preguntas. Voy a ver si te respondo a todas sin extenderme demasiado...

Sinceramente si es muy largo o complicado prefiero hacer otra cosa.
Complicado por sí mismo no, es, pero la complejidad es algo subjetivo que depende de los conocimientos de cada uno.

Bueno, no sé, pero llega a aprender algo sin que yo se lo diga.
Nota la diferencia entre 'encontrar una solución' y 'aprender algo'.

¿Cómo es con grafos y autómatas?
Con grafos es siguiendo el camino que tracé en el mensaje anterior.
Puedes en un principio considerar un árbol, y más tarde pasar a considerar un grafo o al revés.
Nota que con grafos y árboles, la recursividad está a la orden del día. Luego el lenguaje usado debe aceptar recursividad. Es posible cambiar cualquier sistema iterativo a recursivo y viceversa pero en la práctica a veces es complicado pasar de uno a otro, en tanto que en un sistema es básicamente intuitivo. Esa lucha 'contraintuitiva' añade una capa de complejidad innecesaria e indeseable.

Para hacerlo con autómatas, necesitas conocer la teoria de autómatas... si no es como querer arreglar la maquinaria de un tren, solo porque lograste arreglar el pedal de la bici de tu sobrino.

Puse el título de Mastermind porque es muy parecido, pero no he puesto un límite a la cantidad de intentos.
Ok.. no limitarlo en prinicipio a un número de intentos no es mala idea.

Al parecer soy incapaz de resolver el problema por mí mismo.
 ¿Por qué dices que complico si estoy simplificando? 2 valores es más sencillo que 8. En todo caso puedo usar letras en vez de números si te parece mejor.
 Calculo que en mi caso serían 1*2.
Una IA se alimenta de datos. Datos que deben sopesarse, para que se adapten. Si el número de entradas es muy escueta, el aprendizaje será complejo, no quedaría claro ni existiría una separación definida de cuando una solución responde a la lógica tras la IA, respecto de la pura causalidad (pués solo hay 4 soluciones entre la que elegir, por fuerza acertaría un 25% de las veces incluso sin ninguna 'intelgencia detrás')
... ahora pon 20 entradas y entonces incluso un 2% de aciertos será más admirable al caso que un 25% con solo 2 entradas.

 
¿Cuales son los requisitos para que sea IA? Nota que en el título simplifiqué, en parte por no saber qué decir. ¿Lo que describí con números no lo es?
Una IA necesita en principio ser un proceso abstracto, aunque luego pueda ser definido expresamente para un cometido único.
Una IA tiene una o más salidas, pero dichas salidas retroalimentan la entrada, sin retroalimentación no hay siquiera memoria, menos aprendizaje.
Nota que la memoria es una retroalimentación de una entrada con algo ya almacenado (una salida previa).
El aprendizaje, consiste en hacer esto mismo a muchas más capas... El aprendizaje podría verse como una simulación d ela simulación de una memoria.
Una IA requiere poder cambiar valores llamados pesos, para estabilizar como reacciona la información, esos pesos hacen una especie de compensacion distinta a diferentes entradas.

 
¿Entonces esto es un autómata?
actions for fotograma 1
      // Situación inicial.
      BaseVS = 10;
No. Para nada.
Eso es un bloque funcional de acciones.
Guarda una cierta similitud pero solo si se comprende. desde luego no en la forma de abordarlo.
Un autómata en principio se desentiende de tu problema particular, es abstracto.
Recibe un estado inicial y una secuencia y va cambiando el estado interno en función de dichas entradas y una función de evolución (llamada de transición), que dicta como cambia (a que éstado evoluciona desd eel estado actual y con el valor actual de la secuencia). A menudo suele generarse una tabla, para representar el funcionamiento de la funcion de transición.
De una forma simplificada con los datos de entrada computa qué reglas se cumplen y hacia qué estado evoluciona, para finalmente señalar si cumple o no la regla.
En realidad se requiere un autómata por cada regla, aunque finalmente pueden aunarse y simplificar el esquema.

Un autómata en este caso se encargaría de evaluar la apuesta y el número de bolas negras y blancas, y así determinar si la secuencia dada es la solución o no, podría además devolver esos estados internos de las bolas (para recibirlos en la siguiente apuesta).

Como te decía más arriba, para hacerlo con autómatas, necesitas conocer la teoria de autómatas...
No es posible enseñar en 2 o 3 párrafos algo que precisa como mínimo 50 páginas.

Al final has hablado bastante, gracias, pero no me ayudaste con la parte 1...

Yo a lo que he llegado por ahora es a:
Código___Árbol1___Árbol2___etc
________Tiempo que tarda el árbol en hallar el código.
Lamentablemente no puedo penetrar en tu cabeza.
Poner un titulo y el texto de una salida, es lo mismo que no haber hecho nada.

En mi mensaje anterior te he dado pie para sigas desde allí, con árboles. ...pero si tampoco sabes crear y usar árboles en el lenguaje que entiendes... lo que hagas o dejes de hacer, entiendas o dejes de atender, depende finalmentee de tus capacidades.

En línea

Tachikomaia


Desconectado Desconectado

Mensajes: 1.413


Hackentifiko!


Ver Perfil
Re: IA para Mastermind.
« Respuesta #4 en: 7 Febrero 2021, 15:46 pm »

Nota la diferencia entre 'encontrar una solución' y 'aprender algo'.
Encontrar una solución es aprender algo.

Bueno, sigo sin saber cómo nombrar o hacer un árbol. Y usarlo.
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: IA para Mastermind.
« Respuesta #5 en: 7 Febrero 2021, 19:57 pm »

Encontrar una solución es aprender algo.
De modo filosófico para una persona sí...
Si lo hace un programa, que encuentre una solución no aprende nada con ello. Toma una calculadora y multiplica 2 números, dime que ha aprendido aunque arroje la solución correcta. De la IA se espera que 'aprenda'...

Es importante no confundir las materias en objeto.

Bueno, sigo sin saber cómo nombrar o hacer un árbol. Y usarlo.
El foro no está concebido para ser una escuela e impartir lecciones, solo apoyos, apuntes, ayuda puntual... el trabajo de aprender recáe en cada persona individualmente.
Si tu ya conocieras los árboles, que tuvieras una duda concreta y puntual, pués vale preguntar y tendrías respuesta, pero no cabe enseñar a nadie desde 0, y mucho menos desde el nivel en que un 'aspirante' esté anclado en conocimientos (habitualmente poder adquirir ciertos conocimientos, supone conocer los que están por debajo de esa capa y que son necesarios para explicar y comprender lo que se cuenta)...

Hay chorrocientos libros para aprender, casi seguro que también haya muchas páginas donde se aborde el tema con mayor o menos proofundidad (incluso probablemente vídeos por youtube), pero vamos un foro no. Un solo hilo donde dijera: "enseño árboles", acabaría teniendo miles d epáginas, pués todo el mundo vendría a preguntar las mismas cosas respondidas mil veces, pero que en vez de buscar prefiere que se lo cuenten de nuevo otra vez bajo su perspectiva particular.

Mi consejo es que te compres un buen libro, si el dinero (como tantas veces) es un problema, seguro que todavía podrás descargarte alguno por la red... y si tampoco te vale por la razón que sea, Wikipedia, es una opción asequible a todo el mundo: Empieza por aquí... lee, lee y lee.
https://es.wikipedia.org/wiki/%C3%81rbol_(inform%C3%A1tica)
En línea

Tachikomaia


Desconectado Desconectado

Mensajes: 1.413


Hackentifiko!


Ver Perfil
Re: IA para Mastermind.
« Respuesta #6 en: 7 Febrero 2021, 20:12 pm »

No sé cómo funciona una calculadora, pero no creo que los resultados que arroja sean producto de haber probado candidatos como hace una fuerza bruta (que por cierto, creo que es lo que hago).

Estoy por leer algo cuando esté más despierto.
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: IA para Mastermind.
« Respuesta #7 en: 7 Febrero 2021, 20:54 pm »

No sé cómo funciona una calculadora, pero no creo que los resultados que arroja sean producto de haber probado candidatos como hace una fuerza bruta (que por cierto, creo que es lo que hago).
La fuerza bruta es la torpeza en forma presente.
Con alguna frecuencia me tengo que enfrentar a problemas cuya solución no es conocida, en esos caso la fuerza bruta es la última opción, cualquier heurística será siempre mucho mejor.

Estoy por leer algo cuando esté más despierto.
Descansa, si lo necesitas, pero lee... es todo un mundo maravilloso al que (al menos todos los interesados en el conocimiento), lejos de temer debieran tener por su 'amigo íntimo'.
En línea

Tachikomaia


Desconectado Desconectado

Mensajes: 1.413


Hackentifiko!


Ver Perfil
Re: IA para Mastermind.
« Respuesta #8 en: 8 Febrero 2021, 11:10 am »

La fuerza bruta es la torpeza en forma presente.
Con alguna frecuencia me tengo que enfrentar a problemas cuya solución no es conocida, en esos caso la fuerza bruta es la última opción, cualquier heurística será siempre mucho mejor.
Pero eso exige pensar y posiblemente cometer algunos prejuicios.

Citar
lee...
Ya leí más o menos esto:
https://es.wikipedia.org/wiki/%C3%81rbol_(inform%C3%A1tica)
Y en ningún momento dicen cómo se describe un árbol. Además dicen que ciertos casos no son árboles, pero creo que yo los precisaría.
Acá
https://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos#Estructuras_matriciales
Dice algo...

V = { 1, 2, 3, 4, 5, 6 }
A = { {1,1}, {1,2}, {1,5},
{2,3}, {2,5}, {3,4},
{4,5}, {4,6} }
Pensaré qué puedo hacer con eso.
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: IA para Mastermind.
« Respuesta #9 en: 9 Febrero 2021, 14:14 pm »

Ya leí más o menos esto:
https://es.wikipedia.org/wiki/%C3%81rbol_(inform%C3%A1tica)
Y en ningún momento dicen cómo se describe un árbol. Además dicen que ciertos casos no son árboles, pero creo que yo los precisaría.
Wikipedia es una 'enciclopedia universal', no exactamente una enciclopedia informática. Recoge muchos artículos del tema, pero ni wikipedia ni ninguna enciclopedia conocida está enfocada a describir el asunto paso a paso como si se fuera un principante absolutamente lego en toda materia.

Por naturaleza del propio asunto, suelen describirse en términos que ya deben dominarse, sino sería inabordable.
Si al explicarte una bicicleta, en vez de decir 'pedal', cada vez tuviera que dar la explicación exahustiva de lo que es un pedal, describir la bicicleta llevaría 5.000 páginas. Ahí ya, si uno no sabe lo que es un 'pedal' puede buscar en la propia enciclopedia qué es un pedal, pero incluso así, un artículo sobre 'pedal' no tiene porqué contener la 'historia del pedal', o puede que solo se dén dos o 3 entradas históricas, ni tampoco tiene porqué venir 'cómo fabricar un pedal' ni los 500 artículos relacionados al pedal que en algún momento a alguien le pudiera interesar, pués eso requeríría un libro específico dedicado al 'pedal'... una enciclopedia solo posicionaría el 'pedal' en un contexto explicando qué es, algo sobre su origen y sus usos. Incluiso desciribiendo el pedal también se asumirá que el lector sabe lo que es 'roscado' y 'tornillo', etc...

En fin, el 'lee...' lleva puntos suspensivos, para indicar que continues, leer solo 2 artículos puede resolver las dudas que puntualmente uno tenga, o puede necesitarse leer bastante más... todo depende del nivel que se tiene   y el nivel al que se quiere llegar, cuanto mayor la diferencia tanto más lectura será conveniente.


Acá
https://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos#Estructuras_matriciales
Dice algo...
V = { 1, 2, 3, 4, 5, 6 }
A = { {1,1}, {1,2}, {1,5},
{2,3}, {2,5}, {3,4},
{4,5}, {4,6} }
Pensaré qué puedo hacer con eso.
Sobre el modo de representación, puedes hacer una abstracción y por ejemplo no necesitas para nada mantener las ridículas llaves '{} , puedes perfectamente sustituir los separadores de contenidos por otros símbolos (por ejemplo las llaves por paréntesis, que al menos en español resultan más cómodos (de teclear al menos)) a tu elección o incluso eliminarlos (como se hará a continuación y conservando aún enteramente su significado).
por ejemplo podrías hacer:
V = ABCDEF
X = AA, AB, AE, BC, BE, CD, DE, DF

Donde claramente se observa que las letras A-F remplazan la identificación de los nodos etiqeutados en la imagen con valores 1-6 y donde no resulta preciso usar las llaves, la concatenacón es suficiente para indicar una separación de elementos individuales y la coma en grupos... es más claro, simple, legible y procesable. Si los nodos además de expresar una identificación del mismo han de expresas un valor, si será preciso otro separador para diferenciar el identificador de su valor...
Nota que 'V = ABCDEF' simplemente describe que 'A-F' son nodos de un grafo llamado 'V', y que 'X = AA, AB, AE, BC, BE, CD, DE, DF' describe las relaciones entre los nodos, así el nodo 'A' (1 en la imagen) está conectado a los nodos 'A', 'B' y 'E' (1, 2 y 5 en la imagen)
También podría describirse del siguiente modo:
V = ABCDEF
A = ABE
B = ACE
C = BD
D = CEF
E = ABD
F = E

Es decir cada nodo apunta a los nodos a los que está conectado.
Mediante iteración (para recorrer los elementos de un nodo) y recursion (para recorrer los elementos de un nodo obtenido durante la iteración). Si metes cada elemento en un array podrás explorar muchas y diferentes soluciones.

Puedes considerar una expresión en la forma 'Y = CDEF' como un nodo 'Y', con 4 nodos hijos 'C','D','E' y 'F', que pueden ser explorados uno a uno en un bucle o ser accedidos de diferentes modos. Y se podrían expresar con valores, por ejemplo 'Y= C:3;D:8;E:0;F:5'.

Yo uso mucho esa disposición para ciertos problemas más o menos complejos... y como 'hablar es fácil', vaya un ejemplo como demostración...

Pongamos como ejemplo, encontrar la solución en un laberinto (tomado de la red)... observa la imagen (que pongo un poco más abajo) se compone de 10x10 cuadrículas, que he etiquetado (para una fácil y clara comprensión) en horizontales 0-9 y en verticales A-J, se marca exactamente como nodo aquella casilla que supone un cruce, un cambio de dirección, que como se puede observar tienen 2, 3 o 4 direcciones (de 4 solo hay una, G6) y también los nodos que son finales (pués pueden ser marcados como punto final).
Carece de sentido práctico anotar como nodo A1, A2, A3, pués A1 lleva a A0 y a A2, pero no cambia de sentido, cualquier ruta que pase por A1, A2, A3... lleva hacia A9 (o hacia A9 si se recorre en sentido contrario), aunque podría ser el caso de que una casilla específica fuera 'la meta' en tal caso se añade, si no, al ser solo de paso, se resume en sus límites (las que llevan a través de ellas directamente sin posibilidad de cambio). La imagen vista, es más claro que detallada con palabras (como tantas veces).


El laberinto puede verse adjunto en la imagen recién adjuntada, y marcado todos los nodos que de él resultan, es un grafo... que yo traduzco como se ve a continuación y que es fácilmente deducible (aunque ya lo he explicado antes):
Vecindad de los nodos del grafo del 'laberinto.png'
------------------------
A0= A9|H0
A9= A0|C9
B1= B2|E1
B2= B1
B3= B5|C3
B5= B3
B6= B8|C6
B8= B6
C2= D2
C3= C4|B3
C4= C3|C6|D4
C6= C4|C9|B6
C9= C6|A9|J9
D2= D3|C2
D3= D2|F3
D4= D5|C4
D5= D4|E5
D6= D7|E6
D7= D6|E7
D8= E8
E1= E2|B1
E2= E1|G2
E4= E5|F4
E5= E4|E6|D5
E6= E5|D6|G6
E7= E8|D7
E8= E7|D8
F1= G1
F3= F4|D3
F4= F3|F5|E4
F5= F4
F7= F8|G7
F8= F7|I8
G1= G2|F1
G2= G3|G1|E2
G3= G2|H3
G4= G6|I4
G6= G7|G4|E6|H6
G7= G6|F7
H0= H3|A0|J0
H3= H0|G3|I3
H5= H6|I5
H6= H7|H5|G6
H7= H6
I1= I3
I3= I4|I1|H3
I4= I3|G4
I5= H5
I6= I8
I8= I6|F8
J0= H0|J9
J9= J0|C9

El programa recibe dos llamadas.
En la primera introduce y prepara los datos, esto es esta lista se concatena mediante un separador, se envía junto a otros parámetro (por ejemplo, el separador de cada campo conceptualizado al caso).
En la segunda se explicita que se va a hacer, (el tipo de búsqueda), si se van a considerar pesos o no, y el criterio del peso o costo (por ejemplo encontrar las soluciones con el valor exacto, con el valor menor a uno dado, etc...) el nodo inicial y final. Si no se señala un nodo inicial, señala que cualquier lo puede ser. del mismo modo el nodo final puede ser un comodín indicando con ello, que cualquiera puede ser el nodo final, pero si se especifica uno, ese y solo ese será el final).

En este ejemplo solo se trata de buscar las soluciones entre un nodo 'X' y otro nodo 'Y' que uno especifique, el programa tendría que buscar las soluciones posibles... la búsqueda puede ser por fuerza bruta (no aconsejable cuando la explosión combinatoria es elevada), o acotada (por ejemplo si se establecen pesos y se busca un peso exacto, una vez superado dicho valor no es preciso seguir explorando soluciones desde el punto en que ya se ha sobrepasado dicho valor pués añadir nodos no haría si no aumentar dicho valor cuando ya sabemos desde cierto punto que ese camino ya no es válido, etc...

El ejemplo actual puede verse como el nodo inicial es A9 y el nodo final es D8, se buscan todas las soluciones posibles entre dichos nodos. Se localizan 4 y se lista la ruta de cada una...


En este ejemplo no se han especificado pesos, pueden establecerse, pués es fácil contar las casillas entre dos nodos, por ejemplo redefiniendo el nodo A0 con pesos sería: A0= A9:9|H0:7
De igual modo desde A9 a A0 habría un peso de 9 y desde H0 a A0 un peso de 7, en tal caso el peso o costo indicaría la distancia y en tal caso la búsqueda sería ligeramente distinta, pués al final devolvería (interesaría que fuera así), la de menor costo, es decir la solución que menos distancia arroje desde A9 hasta D8...
El grafo no está dirigido, esto es, se puede ir desde un nodo a cualquier otro y al revés no está restringido, cuyando un grafo está dirigido señala que solo s epuede recorrer desde un nodo a los adyacentes que estén dirigidos, por ejemplo,
imaginemos que una flcechita hubiera desde A0 a A9, A0 tendría la siguiente especificación: A0= A9|H0 , peor para A9, si no hubiera una flecha apuntando hacia A0, su especificación sería: A9= C9 en vez de A9= A0|C9


Esto es solo un ejemplo, la variedad de usos es enorme... muchos problemas que a veces uno les busca solución de cierta manera pueden igualmente ser resueltos con grafos, de hecho los lenguajes funcionales tiran mucho de esto.



Pero eso exige pensar y posiblemente cometer algunos prejuicios.
Guau. Si pensar es para ti un esfuerzo, entonces tu relación con la informástica se remite a que te quedes solo como un 'usuario', no un 'desarrollador'... Lo primero solo exige utilizar (mejor o peor), lo segundo exige sí o sí, pensar.

Suena como a alguien que dice que quiere ser submarinista, pero que le da miedo cualquier masa de agua mayor que la que cabe en el lavabo de su baño.

Con 'prejuicios' no tengo claro a que te refieres resulta ambiguo.

Si pensar es para ti un problema, no podrás hacer otra cosa que 'copiar y pegar' y me temo que en ninguna parte vas a encontrar lo que exactamente tu requieras justo para copiar y pegar. Considero que te pienses seriamente qué quieres conseguir y qué estas dispuesto a hacer, si lo uno no encaja con lo otro, estás perdiendo el tiempo y me parece que sería mejor que te dedicaras a otra cosa donde esos dos puntos estén en equilibrio (igualados).
« Última modificación: 9 Febrero 2021, 14:32 pm por Serapis » En línea

Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Mastermind
Programación C/C++
N0body 1 5,392 Último mensaje 1 Mayo 2010, 04:01 am
por N0body
Juego Mastermind
Programación C/C++
adeur 3 5,134 Último mensaje 5 Julio 2012, 15:08 pm
por maxim_o
Ayuda juego Mastermind en C++
Programación C/C++
TheXiiscoZ 4 5,239 Último mensaje 11 Diciembre 2017, 03:56 am
por Serapis
¿Hacer fuerza bruta para ganar en juego similar a Mastermind?
Programación General
Tachikomaia 8 5,105 Último mensaje 30 Abril 2019, 18:13 pm
por Tachikomaia
Juego mastermind
Programación C/C++
Raskera 1 2,094 Último mensaje 26 Abril 2019, 20:05 pm
por Tachikomaia
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines