Algoritmo de búsqueda de palabras

Estoy tratando de llegar a un mejor enfoque que el método de la "fuerza bruta", pero me siento algo perdido.Algoritmo de búsqueda de palabras

Aquí hay un caso simple:

Dado un número finito de letras pre-elegido, y una escotilla (como una superposición de crucigrama) Estoy tratando de encontrar una combinación de palabras que se pueden utilizar. (Las palabras se recuperan desde una base de datos de diccionario.)

Ejemplo:

Dadas las letras:
a, c, r, e, t, u, p, l, m, o
cómo muchas combinaciones de palabras puede caber en el siguiente crucigrama?

_ 
_ _ _ _ 
    _ 
    _ 
    _ _ _

Un ejemplo:

c 
t r e e 
    e 
    e 
    p o t

Por supuesto, el tiempo de búsqueda se incrementa dramáticamente con cada letra o adición a la escotilla de crucigramas. ¿Alguna sugerencia para una mejor forma de buscar?

Fuente

2011-09-09 kylex

Puedo reducir un diccionario de 62 000 palabras con 'sed 's | /.* ||' /var/cache/postgresql/dicts/en_us.dict | egrep "^ [acretuplmo] {3,5} $" | wc 'a 566 palabras en un primer corte aproximado. Pero tengo curiosidad: estás usando 4 veces 'e', pero no' a' en absoluto. ¿Está bien? –

sí, las palabras se crean usando cualquiera de las letras provistas (y cada letra se puede usar varias veces) – kylex

Echa un vistazo a la fuente abierta arccc, que rellena las cuadrículas de crucigramas tratándolas como constraint satisfaction problem. Si desea hacer esto usted mismo como un ejercicio de aprendizaje, leer sobre los CSP debería ser un buen punto de partida.

En cuanto a la limitación del alfabeto, es mejor hacerlo como un paso de preproceso en el diccionario de origen.

Fuente

2011-09-09 02:57:35

Respuesta

Cuestiones relacionadas