algorithm - significado - problema del agente viajero fuerza bruta

qué es exactamente el algoritmo de fuerza bruta

Question

1. ¿Cuál es exactamente el algoritmo de fuerza bruta? (además del solo enfoque)

2. cuando un problema puede usar un enfoque de fuerza bruta, y cuándo no?

3. ¿Qué características hay en un algoritmo cuando el algoritmo usa un enfoque de fuerza bruta?

Answer 1

1 y 3: la fuerza bruta significa que atravesarás todas las soluciones posibles extensivamente . Por ejemplo, en un juego de ajedrez, si sabes que puedes ganar en dos movimientos, la fuerza bruta pasará por todas las combinaciones posibles de movimientos, sin tomar nada en consideración. Así que el pequeño peón en la espalda que no puede influir en el resultado aún será considerado.

2: Al considerar todo, el problema rápidamente sale de control. La fuerza bruta a través de 15 movimientos en el ajedrez es imposible debido a la explosión combinatoria (demasiadas situaciones para considerar). Sin embargo, los algoritmos más inteligentes que toman en cuenta el "conocimiento sobre el problema" pueden ir mucho más allá (20-30 movimientos adelante)

Editar: para aclarar, la fuerza bruta es la forma más simple (¿la más estúpida?) De explorar el espacio de las soluciones . Si tiene un problema establecido en un espacio countable (los movimientos de ajedrez son contables, las contraseñas son contables, las cosas continuas son incontables) la fuerza bruta explorará este espacio considerando todas las soluciones por igual. En el ejemplo del ajedrez, quieres jaque mate a tu oponente. Esto se hace a través de una secuencia de movimientos, que es contable. La fuerza bruta pasará por todas las secuencias de movimientos, por improbables que sean. La palabra improbable es importante, porque significa que si usted tiene conocimiento de su problema (usted sabe lo que es poco probable que sea la solución, como sacrificar a su reina), puede hacer mucho mejor que la fuerza bruta.