魔方吧·中文魔方俱乐部

标题: 计算机解三阶魔方 [打印本页]

作者: lin134340    时间: 2008-12-5 19:33:49     标题: 计算机解三阶魔方

我是刚接触cfop2个月的新手,现在成绩将将sub40。现在想编个程序,让电脑利用最少步数计算出复原公式(尽量少就行,能平均三四十步就够了),不知道需要的数学理论有哪些?需要的魔方知识又有哪些?(我现在在看吧里的魔方组合原理和一式解万方,但都只看了一点)我现在大二,有一些c语基础。
希望在编程解魔方方面有了解的人不吝指点一下~~~


p.s.我找到了Cube Explorer 作者的网站:
http://kociemba.org/cube.htm


cube explore大概是现在算法最好的软件了,速度快,步数少。

网站里面有Two-Phase-Algorithm的简介,即二阶段算法
The Two-Phase-Algorithm
The following description is intended to give you a basic idea of how the algorithm works.
The 6 different faces of the Cube are called U(p), D(own), R(ight), L(eft), F(ront) and B(ack). While U denotes an Up Face quarter turn of 90 degrees clockwise, U2 denotes a 180 degrees turn and U' denotes a quarter turn of 90 degrees counter-clockwise. A sequence like U D R' D2 of Cube moves is called a maneuver.
If you turn the faces of a solved cube and do not use the moves R, R', L, L', F, F', B and B' you will only generate a subset of all possible cubes. This subset is denoted by G1 = <U,D,R2,L2,F2,B2>. In this subset, the orientations of the corners and edges cannot be changed. That is, the orientation of an edge or corner at a certain location is always the same. And the four edges in the UD-slice (between the U-face and D-face) stay isolated in that slice.
In phase 1, the algorithm looks for maneuvers which will transform a scrambled cube to G1. That is, the orientations of corners and edges have to be constrained and the edges of the UD-slice have to be transferred into that slice. In this abstract space, a move just transforms a triple (x,y,z) into another triple (x',y',z'). All cubes of G1 have the same triple (x0,y0,z0) and this is the goal state of phase 1.
To find this goal state the program uses a search algorithm which, in terms of the current research, is called iterative deepening A* with a lowerbound heuristic function (IDA*). In the case of the Cube, this means that it iterates through all maneuvers of increasing length. The heuristic function h1(x,y,z) estimates for each cube state (x,y,z) the number of moves that are necessary to reach the goal state. It is essential that the function never overestimates this number. In Cube Explorer 2, it gives the exact number of moves which are necessary to reach the goal state in Phase 1. The heuristic allows pruning while generating the maneuvers, which is essential if you do not want to wait a very, very long time before the goal state is reached. The heuristic function h1 is a memory based lookup table and allows pruning up to 12 moves in advance.
In phase 2 the algorithm restores the cube in the subgroup G1, using only moves of this subgroup. It restores the permutation of the 8 corners, the permutation of the 8 edges of the U-face and D-face and the permutation of the 4 UD-slice edges. The heuristic function h2(a,b,c) only estimates the number of moves that are necessary to reach the goal state, because there are too many different elements in G1.
The algorithm does not stop when a first solution is found but continues to search for shorter solutions by carrying out phase 2 from suboptimal solutions of phase 1. For example, if the first solution has 10 moves in phase 1 followed by 12 moves in phase 2, the second solution could have 11 moves in phase 1 and only 5 moves in phase 2. The length of the phase 1 maneuvers increase and the length of the phase 2 maneuvers decrease. If the phase 2 length reaches zero, the solution is optimal and the algorithm stops.
In the current implementation the Two-Phase-Algorithm does not look for some solutions that are optimal overall, those that must cross into and back out of phase 2. This increases the speed considerably. Use the Optimal Solver, if you want to prove some maneuver to be optimal.


还有他写软件用到的一些数学工具简介(本部分我只转过来了introduction)
The Mathematics behind Cube Explorer

The following pages are an attempt to give some insight of the mathematical ideas and algorithms developed and used in Cube Explorer.

There are several problems I had to struggle with. First, English is not my native language and some of my explanations may be difficult to understand or incomprehensible at all. Second, I studied mathematics a long time ago and my terminology will surely be incorrect in some parts. Third, I only could sketch the main ideas of all that, what was necessary to write Cube Explorer.

But I hope that nevertheless it is a help for those who are interested in understanding the Two-Phase Algorithm or want to implement the algorithm in their own program.



还有cube explore 的免费下载,还有别的一个算法还是什么的c源程序。这里我不提供链接了,想找的去他网站自己看吧。

我正在学习中,看来是比较难,我不是学计算机的,编程有点困难……



[ 本帖最后由 lin134340 于 2008-12-6 18:00 编辑 ]
作者: roja0828    时间: 2008-12-5 19:41:37

暂时不知道
魔方又不是每次都是一个图案
作者: Cielo    时间: 2008-12-5 19:48:48

有算最少步数的软件了:cube explorer

但那程序到底怎么编出来的我也不知道……
作者: lin134340    时间: 2008-12-5 19:57:27

原帖由 Cielo 于 2008-12-5 19:48 发表
有算最少步数的软件了:cube explorer

但那程序到底怎么编出来的我也不知道……



我这也有个最小步数的软件,但是我的根本意图是把程序植到单片机里,控制机器人还原魔方。在读取魔方状态信息和操作魔方方面我的初步设想都能解决,现在的问题就是怎样做到智能。用人解魔方的思路,比如cfop就不好用,因为底十字,f2l并没有所有状态的公式。
作者: conwood    时间: 2008-12-5 21:03:17

在单片机里做最好还是用cfop。
感觉更容易一些
作者: lin134340    时间: 2008-12-5 21:18:15

原帖由 conwood 于 2008-12-5 21:03 发表
在单片机里做最好还是用cfop。
感觉更容易一些


我觉得不容易啊,十字和f2l怎么编程呢?还有就是f2l的总步数大了点,f2l平均得五六十步以上了吧,我们的机器人比较笨,转一步得好几秒呢。
作者: shifujun    时间: 2008-12-5 22:01:05

好几秒一步是够笨的了……晕
教它玩二阶吧!
作者: lin134340    时间: 2008-12-6 00:07:45

原帖由 shifujun 于 2008-12-5 22:01 发表
好几秒一步是够笨的了……晕
教它玩二阶吧!



二阶的不典型,给没怎么接触过魔方的人还是看三阶好点。网上有机器人复原魔方的视频,做一步都要3秒左右,我们的机器人结构还没开始设计,不过我觉得快不了。我学的是电控,机械方面一无所知。
作者: kexin_xiao    时间: 2008-12-6 12:22:04

这方面我也是外行,和大家学习了
作者: light13    时间: 2008-12-6 15:27:13

C语言要编的话有点困难……
毕竟要做出来的是图形界面,C有点心有余而力不足
作者: light13    时间: 2008-12-6 15:28:43     标题: 回复 4# 的帖子

让机器人转层先法吧,那样好测一点
作者: lin134340    时间: 2008-12-6 18:07:45

原帖由 light13 于 2008-12-6 15:27 发表
C语言要编的话有点困难……
毕竟要做出来的是图形界面,C有点心有余而力不足



最后植到单片机里,不需要电脑虚拟出画面。还是用c。无论层先还是f2l,前两层在编程上都不好想。




欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/) Powered by Discuz! X2