Les pido a los expertos que usen c para resolver el problema de veinticuatro puntos, de la siguiente manera
Análisis del algoritmo de 24 puntos
Hace mucho tiempo que no estudio el programa y me siento avergonzado. . . Este verano leí brevemente "La belleza de la programación" publicado por Microsoft Research Asia. Realmente me gusta el estilo de este libro y muchos de los temas que contiene son muy interesantes. Lo principal que se destaca en el libro es la palabra "qiao". Lo más importante es encontrar las reglas inmutables a partir de los cambios. La pregunta mencionada esta vez es en realidad muy simple. Dados cuatro números, escriba un programa para generar el resultado de 24 puntos. De lo contrario, genere "Sin respuesta". Pero no es posible escribir un programa utilizando nuestro propio pensamiento para calcular 24 puntos, porque es un método de "maquillaje" que implica azar y experiencia. Lo que la computadora puede hacer es encontrar resultados de forma fija. Si no existe una forma general llamada "fija", entonces el problema sólo puede resolverse mediante recorrido y agotamiento. Muchos de los llamados problemas NP-difíciles nacieron con este método. Si la escala de datos original es relativamente grande, llevará mucho tiempo obtener el resultado.
La forma más directa de resolver el problema de 24 puntos es enumerar todas las permutaciones y combinaciones de los cuatro números, además de varios operadores y paréntesis. Una vez procesadas todas las situaciones, puede obtener una lista que contiene todas. resultados de cálculos y lista de fórmulas, solo busque rastros de 24 en ellos. Excluyendo los resultados de cálculo duplicados, hay 7680 resultados finales y la cantidad de datos aún es un poco grande, por lo que este algoritmo necesita una mayor optimización. Por ejemplo, considerando las leyes conmutativas de la suma y la multiplicación, si se encuentra una situación correspondiente, solo se calcula un tipo y el otro tipo se devuelve directamente. Este tipo de procesamiento de poda puede reducir muchas operaciones.
Pero usé otra idea del libro, usando la idea de división. El algoritmo específico es:
Si A es una matriz, defina f(A) como el conjunto de resultados obtenidos por todos los números de la matriz mediante cuatro operaciones aritméticas. Para el caso en el que el número de elementos en A es mayor que 1, A se puede dividir en dos conjuntos y la operación Fork(A, B) se define como las cuatro operaciones aritméticas que toman un elemento de f(A) y f(B). Una colección de resultados. De esta manera, si se enumeran todas las divisiones del conjunto A, entonces la unión de todos los resultados de Fork es el resultado de f(A).
Para el caso de 24 puntos, debido a que la matriz A tiene 4 números, puede obtener el f (A) final dividiéndolo de varias maneras y luego consultar si hay un elemento 24 en él. hay solución o no.
Hay varios puntos que deben explicarse:
1. En la superficie, este problema requiere un algoritmo recursivo, es decir, si solo hay un elemento, devuélvalo directamente; de lo contrario, el problema se convertirá en un cálculo de f múltiple y el cálculo de cada f debe transformarse y repetirse capa por capa hasta que solo quede un elemento. Sin embargo, no olvide que los métodos recursivos generalmente están dirigidos a problemas en los que el número de tiempos de retroceso es incierto. Por ejemplo, en el problema de la Torre de Hanoi, cuando solo hay una placa y cuando hay 64 placas, el número de retrocesos es completamente diferente. Pero para 24 puntos, debido a que solo hay 4 números, la posibilidad de dividir es en realidad fija. y situación tan limitada. La idea del algoritmo recursivo es recorrer desde la raíz del árbol hacia abajo y, en general, se desconoce el tamaño y la escala del árbol. Para el problema de 24 puntos, el tamaño del árbol es fijo. Puede comenzar desde las hojas del árbol y pasar de las hojas a la raíz para obtener el resultado final.
2. Existen ciertas técnicas para dividir, y el método más apropiado es mediante operaciones de bits. Por ejemplo, un método de división es {a1, a2}, {a3, a4}, luego escribe 1100 y 0011. La ventaja de este método es que, por ejemplo, para determinar si 1000 es un subconjunto de 1100, solo necesita hacer Y si el resultado final sigue siendo igual a 1100, indica que de hecho es un subconjunto. Al mismo tiempo, el otro resultado de la división es la diferencia entre los dos. De esta manera, solo necesita comparar más de 10 veces como máximo para enumerar todas las divisiones de cada colección, que es un método más inteligente. Al mismo tiempo, las operaciones de bits también son muy rápidas y no tendrán un impacto importante en el tiempo de cálculo.
3. La desventaja de este método es que lo que se obtiene al final es solo un juicio sin solución o solución, y no se genera ninguna expresión.
Así que hice ciertas mejoras a este algoritmo para que pueda generar expresiones.
Lo primero y más importante a considerar es la estructura de datos de este programa. El objetivo final es, naturalmente, lograr la mínima complejidad de tiempo. Dado que la función f en el método anterior devuelve un "conjunto", no hay elementos duplicados. En tales casos, las tablas hash son naturalmente la estructura de datos preferida.
Para registrar expresiones, es necesario introducir otro conjunto de estructuras de datos. El resultado de cada cálculo debe corresponder a una expresión. De esta manera, cuando la consulta final encuentra un resultado de cálculo de 24, solo necesita buscar la expresión correspondiente para obtener el resultado.
Aquí es donde surge un conflicto. La característica de las tablas hash es que se almacenan desordenadas, es decir, si solo se usa una tabla hash para almacenar los resultados del cálculo y se usa un vector para almacenar expresiones, no se puede generar ninguna correspondencia.
Por lo tanto, hay dos opciones:
La primera opción ahorra espacio de almacenamiento y almacena los resultados del cálculo y las expresiones en dos vectores respectivamente, debido a que ambos están ordenados en la clase Colección, por lo que los respectivos subíndices se pueden hacer coincidir al insertar datos, de modo que la relación correspondiente se pueda obtener fácilmente. Sin embargo, la consecuencia de esto es que al insertar nuevos datos, debe averiguar si el resultado del cálculo ya existe en el vector. Si ya existe, no es necesario insertarlo. La búsqueda de vectores es exhaustiva y la eficiencia es relativamente baja, especialmente cuando el vector es relativamente grande, afectará en gran medida la eficiencia del cálculo. Pero si no busca, inevitablemente calculará muchos resultados duplicados sin sentido, perdiendo así el significado de este algoritmo.
El segundo esquema almacena los resultados del cálculo en datos de una tabla hash adicional basada en el primer esquema. Esto aumenta el espacio de almacenamiento, pero la ventaja de tiempo es obvia. Al insertar, determine si el resultado ya existe buscando en la tabla hash. Dado que la eficiencia de búsqueda de la tabla hash es muy alta, este paso no causará un cuello de botella de tiempo para el programa. Si no existe, simplemente inserte datos en la tabla hash y dos vectores al mismo tiempo. La relación correspondiente entre los resultados del cálculo y las expresiones todavía existe, mientras que la eficiencia de la búsqueda ha mejorado enormemente y la complejidad temporal de todo el programa se ha reducido considerablemente. Este es un método típico de intercambiar espacio por tiempo.
Mi lenguaje preferido para escribir algoritmos es c, pero me da vergüenza no saber cómo usar HashTable de c, así que escribí una versión en java, que fue relativamente exitosa y pudo generar el resultado final. . Antes de escribir el programa, escribí un pequeño programa para probar la eficiencia de búsqueda de HashSet y ArrayList de Java. Los resultados fueron sorprendentes. En 10,000 consultas, HashSet tomó 0 ms, mientras que ArrayList tomó más de 1300 ms. Parece que esta eficiencia no es un orden de magnitud en absoluto. Por lo tanto, adopté la segunda solución mencionada anteriormente y el efecto final no fue malo.
Alguien me preguntó una vez cómo se calcula 5, 5, 5, 1 como 24 puntos. Lo pensé durante mucho tiempo pero nunca lo descubrí. Ahora puedes calcular fácilmente 5*(5-1/5)=24 usando este programa. Parece que este programa puede generar algunos resultados inesperados, lo cual es muy poderoso. Hay muchos ejemplos similares, como 3, 3, 7, 7, etc. En resumen, el método exhaustivo optimizado (mi programa es en realidad un método exhaustivo disfrazado) es una muy buena manera de resolver problemas y vale la pena adoptarlo.
En unos días empezarán las clases. Tal vez solo tengamos tiempo para estudiar este tipo de problemas antes del inicio de clases cada año, y básicamente no haya tiempo después de que comiencen las clases. Bueno, trabaja duro y espero poder conseguir un buen tema este año y hacer un buen trabajo el año que viene. Buena suerte.
PD: Ayer descubrí una solución mejor después de que mis compañeros me la recordaran. Principalmente porque no lo he usado durante mucho tiempo y me olvidé del HashMap de Java.
Esta estructura de datos es adecuada para usar aquí, es decir, no requiere dos HashSets y dos ArrayLists, se puede almacenar directamente en un HashMap.
El método específico es: almacenar el resultado del cálculo en la clave del mapa, y la expresión se almacena en el valor del mapa, y el problema se resuelve por completo. La eficiencia de búsqueda de claves en el mapa es muy alta y la inserción también es muy rápida. Cuando encuentra un resultado de cálculo de 24, puede encontrar directamente el valor correspondiente de acuerdo con esta clave para obtener la respuesta perfecta. HashMap también garantiza que en cada cálculo solo se conserva una expresión en el resultado, evitando la duplicación.
Hice una prueba de rendimiento. En términos generales, la eficiencia de esta versión mejorada es ligeramente mejor que la versión anterior, pero lo más importante es que el espacio de almacenamiento se reduce considerablemente, por lo que puede considerarse como. una mejora al programa. Una gran optimización me hace pensar. Parece que más personas han leído esta publicación en los últimos dos días y espero que mis pensamientos puedan inspirarlos.