Roteamento e o Cubo Mágico

• Gustavo Ribeiro Monteiro Universidade Federal do Rio de Janeiro
• Daniel Sadoc Menasché Universidade Federal do Rio de Janeiro http://orcid.org/0000-0002-8953-4003

DOI: https://doi.org/10.5753/sbrc.2020.12336

Resumo

O cubo mágico, também conhecido como cubo de Rubik, é um jogo popular que recentemente atraiu a atenção da comunidade científica como um problema estilizado para ilustrar a aplicabilidade das técnicas de aprendizado de máquina. Neste artigo, mostramos novos resultados que aproveitam as propriedades de simetria do cubo Rubik para fins de roteamento. Dados dois estados alcançáveis do cubo, mostramos que podemos rotear eficientemente de um estado para outro, dada uma solução para o problema padrão do cubo Rubik. Em seguida, indicamos como o algoritmo eficiente proposto pode ser usado para refinar as soluções abaixo do ideal para o roteamento de caminho mais curto entre os estados do cubo Rubik.

Palavras-chave: source routing, rubik's cube, deep learning

Referências

Agostinelli, F., McAleer, S., Shmakov, A., and Baldi, P. (2019). Solving the Rubik’s cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356–363.

Castro, M., Druschel, P., Hu, Y. C., and Rowstron, A. (2003). Topology-aware routing in peer-to-peer networks. In Future directions in distributed computing, pages 103–107. Springer.

Cerpe, R. (2007). Cubo 3x3x3. http://www.cubovelocidade.com.br/tutoriais/cubo-magico-blindfolded.html.

Chan, H. N., Van, K. N., and Hoang, G. N. (2008). Characterizing chord, kelips and tapestry algorithms in p2p streaming applications over wireless network. In Int. Conference on Communications and Electronics, pages 126–131. IEEE.

Delorme, C. and Panaite, P. (1996). Rubik routing permutations on graphs. In European Conference on Parallel Processing, pages 283–286. Springer.

Fortin, D., Kirchner, C., and Strogova, P. (1994). Routing in regular networks using rewriting. In Proceedings of the CADE international workshop on automated reasoning in algebra (ARIA), pages 5–8. Citeseer.

Garrett, D. and Hatamian, M. (2019). Cube puzzle solver. US Patent App. 16/099,833.

Hassan, R. M. and Abdulmuim, M. E. (2019). Using Rubik’s cube in fragile audio watermark encryption. Diyala Journal For Pure Science, 15(03):103–124.

Huq, S., Shafiq, Z., Ghosh, S., Khakpour, A., and Bedi, H. (2017). Distributed load balancing in key-value networked caches. In ICDCS, pages 583–593. IEEE.

Johnson, D. B. and Maltz, D. A. (1996). Dynamic source routing in ad hoc wireless networks. In Mobile computing, pages 153–181. Springer.

Korf, R. E. (1997). Finding optimal solutions to Rubik’s cube using pattern databases. In AAAI/IAAI, pages 700–705.

Lai, X., Zhang, P., Zhang, X., Wu, H., Pu, Z., Yu, H., and Li, D. (2019). Reconfigurable microfluidics in a Rubik’s cube. In Micro Electro Mechanical Systems, pages 110–113. IEEE.

Mannone, M., Kitamura, E., Huang, J., Sugawara, R., Chiu, P., and Kitamura, Y. (2019). Cubeharmonic: a new musical instrument based on Rubik’s cube with embedded motion sensor. In ACM SIGGRAPH 2019 Posters, page 53. ACM.

Nvidia (2019). Datasheet nvidia t4 tensor core gpu.

Rokicki, T., Kociemba, H., Davidson, M., and Dethridge, J. (2014). The diameter of the Rubik’s cube group is twenty. SIAM Review, 56(4):645–670.

Ruwix (2019). Pretty Rubik’s cube patterns with algorithms.

Singmaster, D. (1981). Notes on Rubik’s magic cube. Enslow Publishers Hillside, NJ.

Steinparz, C. A., Hinterreiter, A., Stitz, H., and Streit, M. (2019). Visualization of Rubik’s cube solution algorithms. EuroVis Workshop on Visual Analytics.

Zeng, D.-X., Li, M., Wang, J.-J., and Hou, Y.-L. (2018). Overview of Rubik’s cube and reflections on its application in mechanism. Chinese Journal of Mechanical Engineering, 31(1):77.

Zhao, B. Y., Huang, L., Stribling, J., Rhea, S. C., Joseph, A. D., and Kubiatowicz, J. D. (2004). Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on selected areas in communications, 22(1):41–53.