Un estudio computacional del grupo de Rubik

Autor: Colmenarejo Pérez, Lucía
Přispěvatelé: Santini, Simone (Tutor), UAM. Departamento de Ingeniería Informática
Jazyk: Spanish; Castilian
Rok vydání: 2021
Předmět:
Zdroj: Biblos-e Archivo. Repositorio Institucional de la UAM
instname
Popis: Eneste trabajo se han abordado diferentes métodos de cara a la resolución de uno de los rompecabezas más conocidos mundialmente, el cubo de Rubik. Los algoritmos escogidos son muy distintos y por ello se realizará un estudio comparativo entre ambos. Previamente, se explica el origen del cubo de Rubik así como se explican las matemáticas que hay detrás de este rompecabezas. De igual manera, se emplearán dos representaciones en función del algoritmo, teniendo por un lado una representación basada en la interfaz gráfica y otra en los pilares matemáticos en los que se basa. Por un lado, se ha estudiado el grupo de Rubik donde usamos las permutaciones y las nociones másimportantes de grupo como base para uno de los métodos empleados, el algoritmo A* (A-estrella). Adicionalmente se hace una implementación especial de las configuraciones de los cubitos que componen al cubo de Rubik representadas por tuplas de dos y tres letras, que identifican las caras. Sobre estas permutaciones se aplican los movimientos del cubo de cara a encontrar la solución. Para el método de A* se han desarrollado unas heurísticas con el fin de valorar cuál de ellas es más eficiente. Adicionalmente, para poder comparar las heurísticas entre sí, se realiza un estudio en el que se ven la cantidad de nodos que ha sido necesario generar y explorar para llegar a la solución. Por otro lado, se ha implementado el Algoritmo del Principiante el cual se desglosa en siete pasos distintos. En cada uno de estos pasos se tendrá en cuenta las distintas casuísticas en las cuales se puede encontrar el cubo para dar una solución parcial a cada uno de ellos. La representación del cubo para este algoritmo se basa en su forma geométrica en el plano tridimensional, la cual se emplea en la interfaz gráfica para mostrar la resolución del rompecabezas. Por último, se realiza un estudio en el que se comparan el Algoritmo del Principiante con el A* usando cada una de las heurísticas para así poder estudiar su eficiencia. Finalmente, tras el estudio se concluye que el método de A* es mucho más eficiente en términos de número de movimientos que el Algoritmo del Principiante; sin embargo, consume una mayor cantidad de recursos, no pudiendo llegar a una solución en ciertas situaciones por tiempos de ejecución.
Databáze: OpenAIRE
Externí odkaz: