Foros del Web » Programación para mayores de 30 ;) » Programación General »

Curso o info sobre Fuerza bruta y Backtracking?

Estas en el tema de Curso o info sobre Fuerza bruta y Backtracking? en el foro de Programación General en Foros del Web. Información sobre las dificultades de aplicación, es decir que haya muestras de "ejercicios resueltos" en los cuales (a medida que avanza el libro) las condiciones ...
  #1 (permalink)  
Antiguo 01/04/2017, 07:05
Avatar de Tachikomaia  
Fecha de Ingreso: agosto-2011
Mensajes: 399
Antigüedad: 5 años, 10 meses
Puntos: 5
Curso o info sobre Fuerza bruta y Backtracking?

Información sobre las dificultades de aplicación, es decir que haya muestras de "ejercicios resueltos" en los cuales (a medida que avanza el libro) las condiciones que los candidatos deban cumplir sean cada vez más difíciles de describir (en los programas), y que los problemas se vayan complicado por ese y otros motivos como la presencia de efectos incontrolables como azar o acciones de un rival.

No tengo claro lo que es Backtracking, yo le llamo así a una forma de Fuerza bruta, que posiblemente sea lo que llaman lógica.
En ciertos casos, lo más bruto digamos que sería probar series de acciones, como "acción nro 1, luego 1 otra vez", reset si no funciona, probar "acción 1 luego 2", reset si no funciona, "1, 3", etc. Aumentando la cantidad de acciones por serie cuando se hicieron todas las combinaciones.
El método que yo uso consiste en ir grabando las nuevas situaciones que se produzcan y cómo se llegó a ellas, y así no hay reset ni repetición de acciones en iguales condiciones, lo que hay es volver a una situación conocida y en ella probar acciones que en ella no se hayan probado. Cuando se logra el objetivo se van cargando las situaciones "hacia atrás" y se va viendo cual es la serie de acciones más óptima.
Obviamente ese método no serviría si hay azar, entre otras cosas, o al menos no así como está.
Si el backtracking es algo distinto a lo que dije, entonces disculpas y no es lo que busco. ¿Cómo se le llama, fuerza bruta lógica? Pues eso entonces.

Gracias.
__________________
"No se puede borrar hasta", PHPeros.
  #2 (permalink)  
Antiguo 01/04/2017, 08:39
 
Fecha de Ingreso: enero-2015
Mensajes: 391
Antigüedad: 2 años, 5 meses
Puntos: 52
Respuesta: Curso o info sobre Fuerza bruta y Backtracking?

Es muy curioso que no sepas hacer un hola mundo ni conozcas los rudimentos básicos de la programación en nivel inicial, y pretendas implementar algoritmos complejos.
  #3 (permalink)  
Antiguo 01/04/2017, 09:55
Avatar de Tachikomaia  
Fecha de Ingreso: agosto-2011
Mensajes: 399
Antigüedad: 5 años, 10 meses
Puntos: 5
Respuesta: Curso o info sobre Fuerza bruta y Backtracking?

Cita:
Iniciado por agleiva Ver Mensaje
Es muy curioso que no sepas hacer un hola mundo ni conozcas los rudimentos básicos de la programación en nivel inicial, y pretendas implementar algoritmos complejos.
Lo muy curioso es que tú, teniendo tanta experiencia en el foro, aún no hayas aprendido que es para hacer consultas o responderlas, no para decir lo que te parece muy curioso ni decir tus interpretaciones sobre lo que el consultante puede, sabe o pretende hacer, o al menos no cuando no es la consulta o tema, o cuando al hacer eso no lo respondes. Lo que acabas de hacer se llama trolleo, tomar el pelo, etc, y normalmente cuando haces eso un moderador te da una advertencia o algo. ¿No ha sido eso, ha sido sólo una descripción de hechos? Ah, perdona, pero es que no lo parece.

Para empezar, habría que ver a qué llamas hacer un hola mundo, pero tengo entendido que es dar instrucciones por medio de un lenguaje de programación de modo tal que cuando el intérprete las lee muestra ese mensaje en la pantalla. Probablemente sea otra cosa, pero por ahí va la mano ¿no? Recuerdo haberlo hecho en Python por ejemplo.
Entonces ¿por qué afirmas que no sé hacerlo? Si no ha sido para burlarte de mí, no sé qué otro motivo puede ser. Hablas como si me conocieras mucho, pero entonces sabes que he hecho cosas más complejas que un hola mundo. Entonces, parece que te has burlado, definitivamente. mentido sobre mi persona. ¿Yo he mentido sobre ti? ¿te debo algo? ¿por qué me tomas el pelo?

"ni conozcas los rudimentos básicos de la programación en nivel inicial"
Ni siquiera sé el significado de rudimentos, pero lo que se considere básico en las universidades o en la cultura general de la programación o los programadores no me interesa, sé lo que son los condicionales, la definición de variables, las repeticiones, y ese tipo de cosas, lo cual para mí es suficiente. ¿Me equivoco? Puede ser, puede que si por ejemplo no sé la diferencia entre método y función o si nunca uso arrays entonces no pueda hacer siquiera un "hola básico", pero por ahora no he tenido problema que me parezca por esos motivos. Puede que esté equivocado...

"algoritmos complejos"
Quiero por ejemplo ir aprendiendo a hacer descripciones de condiciones cada vez más complejas. Llamarle a eso "agoritmos complejos" me parece que no corresponde, no es tan simple. Es como que digas que quiero pasar el nivel 3 de un videojuego cuando ni siquiera sé si voy a llegar, yo lo que planteo es empezar desde el inicio e ir avanzando. El inicio en cuanto a descripción de condiciones es por ejemplo "Si Candidato > 10", lo cual no me parece tan complejo, pero claro, como según tú yo no sé hacer un hola mundo eso es complejo para mi nivel.

Ahora, a ver si además de profesional en programación como dices ser eres sincero y admites que has respondido para tomarme el pelo, y que te manden unas merecidas vacaciones.
__________________
"No se puede borrar hasta", PHPeros.
  #4 (permalink)  
Antiguo 03/04/2017, 17:47
Avatar de Carlangueitor
Moderador ლ(ಠ益ಠლ)
 
Fecha de Ingreso: marzo-2008
Ubicación: México
Mensajes: 9.947
Antigüedad: 9 años, 3 meses
Puntos: 1310
Respuesta: Curso o info sobre Fuerza bruta y Backtracking?

@Tachikomaia: No estoy justificando el comentario de @aglevia, pero creo que ya se te ha comentado varias veces (incluso yo mismo), sería bueno que por lo menos leyeras un poco más formal acerca de lo que quieres aprender/hacer por lo menos para que te puedas explicar de que es lo que quieres.

¿Exactamente que quieres? ¿Un curso/info de lo que tu llamas backtraking? No entiendo bien tu problema, no entiendo a que te refieres con "grabar las nuevas situaciones que se se produzcan", así que ¿podrías poner un ejemplo más práctico y/o concreto y menos abstracto?

Por otro lado si quieres algo más general, no estoy seguro de que es lo que buscas (por lo mismo de que no compartimos los términos comunes del area), quizá te interesaría la llamada Teoría de Juegos e incluso más específicamente la Teoría de Juegos Algorítmica, que incluso podrías revisar el material de este curso de la universidad de Stanford en el tema.


Saludos
__________________
Grupo Telegram Docker en Español
  #5 (permalink)  
Antiguo 20/04/2017, 01:10
Avatar de Tachikomaia  
Fecha de Ingreso: agosto-2011
Mensajes: 399
Antigüedad: 5 años, 10 meses
Puntos: 5
Respuesta: Curso o info sobre Fuerza bruta y Backtracking?

Cita:
Iniciado por Carlangueitor Ver Mensaje
@Tachikomaia: No estoy justificando el comentario de @aglevia, pero creo que ya se te ha comentado varias veces (incluso yo mismo), sería bueno que por lo menos leyeras un poco más formal acerca de lo que quieres aprender/hacer por lo menos para que te puedas explicar de que es lo que quieres.
Lo que interpreto de eso es que me sugieres ser más formal al hablar o leer algo formal. Sé que la wikipedia no es formal, pero pienso que debería ser suficiente para empezar.
https://es.wikipedia.org/wiki/B%C3%B...e_fuerza_bruta

Se menciona 2 ejemplos:
- encontrar el divisor de un número natural n consistiría en enumerar todos los enteros desde 1 hasta n, chequeando si cada uno de ellos divide n sin generar resto.
- solucionar el problema de las ocho reinas (posicionar ocho reinas en el tablero de ajedrez de forma que ninguna de ellas ataque al resto), consistiría en examinar todas las combinaciones de posición para las 8 reinas, comprobando en cada una de ellas si las reinas se atacan mutuamente.

Es evidente que aplicar la fuerza bruta en el 1er caso es mucho más fácil que aplicarla en el 2ndo, porque en él las condiciones a chequear son más difíciles de describir. En el 1er caso es algo como:
Código:
Resultado = N/Candidato
Si Resultado == Floor(Resultado)
   // Condición cumplida.
El 2ndo caso no lo voy a pensar ahora, pero evidentemente sería más difícil.

Y si en vez del problema de las 8 reinas hablamos de ganar una partida a un rival, más aún.

Entonces, quisiera un libro que tenga MUCHOS problemas resueltos con fuerza bruta, por supuesto mostrando el código de dicha fuerza, no simplemente la solución del problema.

Cita:
¿Exactamente que quieres? ¿Un curso/info de lo que tu llamas backtraking? No entiendo bien tu problema, no entiendo a que te refieres con "grabar las nuevas situaciones que se se produzcan", así que ¿podrías poner un ejemplo más práctico y/o concreto y menos abstracto?
Ok, no fui claro en eso. Te aviso que estoy fuera de forma en ese tema (lo que yo llamo Backtracking), así que no prometo mucho.

Supongamos que esto:

es un laberinto, nuestro personaje se encuentra en la zona 2 y la salida en la 6. El programa comienza a probar acciones, a mover al personaje. La 1era acción lo lleva a la zona 1. En ese momento, se crea un archivo llamado como la situación (1) y que contiene cómo llegó a ella:
Situación_Anterior = 2
Acción_Realizada = 1
Cantidad_de_acciones_realizadas = 1
También se puede hacer con arrays o variables así:
Sit1.Situación_Anterior = 2
Sit1.Acción_Realizada = 1
Sit1.Cantidad_de_acciones_realizadas = 1
...pero prefiero el otro método.
También creamos un archivo llamado Nueva1 que contiene la nueva situación a la que llegamos. Tenemos una variable Nuevas que va aumenta cuando llegamos a una nueva.
Bueno ¿ha llegado la zona 6? No. Entonces volvemos a la situación anterior ¿es posible en ella realizar una acción aún no probada? Sí, una que lleva a la zona 5. ¿Existe el archivo 5.txt? No. Lo creamos con los datos correspondientes, y creamos un archivo Nueva2, idem.
...
Volvemos a la situación anterior ¿queda alguna acción por probar? Sí, una que lleva al 3. Repetimos el proceso. Cuando ya no quedan acciones posibles en una situación, probaremos acciones en las situaciones nuevas, que hemos guardado en los archivos Nueva(númeo aquí) y cuyos datos están en los otros archivos. O sea, los archivos Nueva indican qué archivos cargar.
Cuando se llega a la zona 6, se comienza a crear una lista de las acciones realizadas, para lo cual se carga el archivo que se marque en las variables "Situación_Anterior". Este proceso sería ir hacia atrás, como antes había comentado.

Básicamente, eso. Puede ser búsqueda de camino más corto, pero se puede aplicar en casos en que no hay caminos (sino series de acciones, por ejemplo para lograr un jaque mate), en definitiva no sé técnicamente cómo se le llamaría a mi método. Yo pensé que era Backtracking pero con el tiempo me convencí de que no sé.

Tal vez alcanzaba con cambiar "grabar" con "anotar", pero sino, ya tienes todo el método.

...

Teoría de juegos parece muy avanzado para mí, al menos del modo en que se trata en wikipedia, pero tendría que leerlo con mucha tranquilidad a ver qué logro. Además, es que tiempo después de hacer este tema he tratado de entender (otra vez) cuales son las condiciones posibles básicas en relación con un número, o sea estoy concentrado en eso y ya por ahora no puedo volver a concentrarme en este tema (que supongo es más amplio), pero están relacionados ya que como mencioné me interesa ver ejercicios ordenados por su complejidad lo cual depende de la complejidad de las condiciones a cumplir. En un tiempo supongo que tendré algo interesante, por ahora lo que puedo mostrarte esto esto:
Código:
Nota: Sustituir ? por un símbolo comparador: ==, >, <, =>, <= o !=

Obtener un número ? X
	Obtener un núm ? X o ? Y		Ej: 2 o >4
	*Obtener un núm ? X y ? Y		Ej: >2 y <10
	*Obtener un núm == X Tolerancia Y	Ej: 3 T1: 2 o 3 o 4: =>2 y <= 4
	Obtener un núm ? X y otro ? Y		Ej: 5 y otro != 5
	Obtener el número mínimo
	Obtener el número máximo
	Obtener un número que al sumarle X resulte ? Y
	Obtener un número que al restarle X resulte ? Y
	Obtener un número que al multiplicarlo por X resulte ? Y
	Obtener un número que al dividirlo por X resulte ? Y
		Obtener un número que al dividirlo por X el resto sea ? Y
		Obtener un número que al dividirlo por X tenga ? Y decimales
	Obtener un número que al elevarlo a la X resulte ? Y
	Obtener un número que al radicarlo a la X resulte ? Y
		Obtener un número que al radicarlo a la X el resto sea ? Y
		Obtener un número que al radicarlo a la X tenga ? Y decimales
	Obtener un número cuyo 1er caracter sea ? X
	Obtener un número entero
		Obtener un número cuya parte entera sea ? X
		Obtener un número cuya parte entera tenga ? X números
	Obtener un número decimal
		Obtener un número cuya parte decimal sea ? X
		Obtener un número que tenga ? X decimales
	Obtener un número que al convertirse a binario sea ? X
		Obtener un número que al convertirse a combinatoria bin sea ? X
	Obtener un número de largo ? X
	Obtener un número que al agregarle X al final, sea ? X
		Obtener un número que al "multiplicarlo" por X sea ? Y
			Obtener un número que al "elevarlo" a la X sea ? Y
	Obtener un número que al convertirse a abs sea ? X
	Obtener un número que al aplicarse floor sea ? X
	Obtener un número que al aplicarse ceil sea ? X
	Obtener un número que al aplicarse round sea ? X
	Obtener un número que al quitarle el último num, sea ? X
		Obtener un número que al quitarle los Xs, sea ? Y
			Obtener un número que al quitarle el punto sea ? X
			Obtener un número que al "dividirlo" entre X sea ? Y
				Obte. un núm q al "radicarlo" a la X sea ? Y
Varios puede que no los entiendas, pero no hay problema. Los que están anidados (si es que se dice así) o más anidados es que los considero más complejos que los que lo están menos. La lista no está completa. Y no es que quiera anidar cosas infinitamente, justamente estoy pensando en cual sería "la estructura". Por ejemplo:
"Obtener número..." y acá imaginate que habría un menú que tuviera opciones, como "que sea", "que al", "cuya parte", etc, y luego otro menú de opciones basadas en la que hayas elegido, por ejemplo:

Código:
que sea
	? X
	el mínimo
	el máximo
	entero
	decimal

que al
	sumarle X
	restarle X
	multiplicarlo por X
	dividirlo por X
	elevarlo a la X
	radicarlo a la X
La idea es percibir condiciones sin ser tan repetitivo como lo estaba siendo en la lista que te mostré. Ya esto no tiene tanto que ver con el tema, o al menos no espero hallarlo en un libro, pero bue.
__________________
"No se puede borrar hasta", PHPeros.
  #6 (permalink)  
Antiguo 20/04/2017, 01:56
Avatar de Malenko
Moderador
 
Fecha de Ingreso: enero-2008
Mensajes: 5.264
Antigüedad: 9 años, 5 meses
Puntos: 594
Respuesta: Curso o info sobre Fuerza bruta y Backtracking?

Cita:
Iniciado por Tachikomaia Ver Mensaje
Entonces, quisiera un libro que tenga MUCHOS problemas resueltos con fuerza bruta, por supuesto mostrando el código de dicha fuerza, no simplemente la solución del problema.
Aquí tienes un punto de donde empezar, aunque ya te adelanto que no vas a encontrar exactamente lo que buscas porque es demasiado específico. Existen muchos problemas que se pueden resolver por fuerza bruta y no tiene ningún sentido escribir un libro sobre como resolverlos, sino que te explican unos pocos y te dan las herramientas para que seas tú mismo quien aprenda como resolver el resto. Porque la idea de un libro (y menos el de una materia como esta que forma parte de estudio en las ingenierías) es que aprendas, no darte resueltos todos los problemas que puedan existir.
__________________
Aviso: No se resuelven dudas por MP!



La zona horaria es GMT -6. Ahora son las 06:00.