algorithm - ordenamiento - Necesita ayuda para construir algoritmos de búsqueda exhaustivos eficientes

metodos de busqueda en c++

Question

Hay 10 botones Estos botones pueden desbloquear el bloqueo si se presionan en el orden correcto (5 pulsaciones en secuencia). Cada vez que se presiona un botón se activa la verificación de desbloqueo.

Ejemplo: "contraseña" es 123456 y presiono los botones 0 1 2 3 4 5 6 Desbloqueo el candado desde la 6ª pulsación de botón.

Necesito diseñar un algoritmo que intente todas las combinaciones posibles de la manera más eficiente (es decir, se debe presionar la cantidad mínima de botones).

Puedo interpretar el número de botón como dígito y el número de botón presionado en secuencia como posición de dígito y luego probar todas las 99999 combinaciones para intentar desbloquear el bloqueo, pero creo que hay un algoritmo más eficiente para hacerlo.

¿Hay algo que pueda hacer para optimizar esta búsqueda?

Answer 1

Para optimizar un ataque de fuerza bruta en un bloqueo, puedes usar secuencias De Bruijn .

La secuencia se puede usar para acortar un ataque de fuerza bruta sobre un bloqueo de código tipo PIN que no tiene una tecla "enter" y acepta los últimos n dígitos ingresados. Por ejemplo, un cerrojo de puerta digital con un código de 4 dígitos tendría soluciones B (10, 4), con una longitud de 10,000. Por lo tanto, solo a lo sumo 10,000 + 3 = 10,003 (dado que las soluciones son cíclicas) se necesitan presiones para abrir el bloqueo. Probar todos los códigos por separado requeriría 4 × 10,000 = 40,000 prensas.