¿Cómo puedo evitar las técnicas de fuerza bruta?

Una cosa simple que puede hacer es recorrer su código en un depurador, y cada vez que se encuentre pensando “¡esto es tan tonto!”, Pregúntese: “¿Qué es exactamente lo que sé (tal vez implícitamente) que me permite reconocer la estupidez de los pasos que la computadora sigue servilmente? ”

Por ejemplo, suponga que está construyendo un corrector ortográfico (o un programa de juego de scrabble que necesita verificar la validez de las palabras formadas por los movimientos del jugador humano) dirigido a hardware de baja especificación (procesador lento, RAM lenta). Comienza con una búsqueda lineal, encuentra que es demasiado lenta, pasa a una búsqueda binaria (mejor, pero aún demasiado lenta), ¿qué sigue? Después de recorrer el código, puede notar que una gran ventaja que tiene sobre la computadora es su conocimiento incorporado de las posibles transiciones de una letra a la siguiente que son realmente plausibles / posibles en su idioma de destino. ¿Quizás hay una manera de codificar ese conocimiento de alguna manera “compilando” su léxico en una estructura de datos optimizada que eliminaría por completo la búsqueda? ¿Tal vez algo parecido a un árbol, con cada nodo representando una letra?

(En este caso, como era de esperar, la estructura de datos que busca ya se ha inventado, se llama Gráfico de palabras acíclicas dirigido, o DAWG para abreviar).

Sin embargo, lo anterior sigue siendo válido como ilustración de uno de los (muchos) posibles caminos por los cuales es posible llegar a este tipo de realización.

Su problema es que no está pensando de manera abstracta. Por “técnicas de fuerza bruta” entiendo que quiere decir que es inepto para encontrar soluciones tolerantes a fallas y de talla única cuando programa. Este tipo de soluciones son críticas porque no puede dar cuenta de cada entrada que utilizará un programa.

La única vez que usaría un enfoque de fuerza bruta cuando programe es cuando sé que puedo dar cuenta de cada caso / cada entrada que sé que mi programa tendrá que tratar.

Sugeriría lo siguiente:

• Familiarícese con los conceptos de OOP como: jerarquías de herencia, clases abstractas, interfaces, polimorfismo y encapsulación de datos.
• Lea sobre los patrones de diseño | Diseño orientado a objetos
• Lea el código fuente para marcos populares y bien diseñados, como WordPress y jquery.
• Echa un vistazo a este libro electrónico de algoritmos desde mi dropbox: estructuras de datos y algoritmos.pdf

El punto clave necesario para pasar de una solución de fuerza bruta a una solución “inteligente” es una visión profunda del problema en cuestión. Esto no es necesariamente fácil dependiendo de su experiencia con el dominio del problema.

Puedo dar un consejo general que ayuda en algunos problemas. Al tratar de resolver un problema que se basa en la pregunta de si algo es posible, debe preguntarse “¿Estoy buscando un ejemplo que demuestre que es posible?” O “¿Solo necesito mostrar un argumento de que algo es posible sin tener que mostrar un ejemplo “.

Por ejemplo, suponga que desea escribir un método que determine cuántos subconjuntos se les da un conjunto particular. Una forma de resolverlo es generar todos los subconjuntos y luego contarlos y devolverlos. En este caso es un algoritmo de fuerza bruta. Mirando la pregunta más de cerca, realmente no necesita generar todos los subconjuntos porque el problema solo quiere el número de subconjuntos, por lo que podría aplicar la fórmula matemática que dice que dado un conjunto de tamaño N hay 2 ^ N subconjuntos. Tenga en cuenta que al preguntar qué tipo de valor de retorno está buscando puede cambiar en gran medida su perspectiva sobre cómo resolver el problema.