Project Communication

到现在为止有了一种用来搜索的算法，我们都已经了解了。但是关于估价函数的选择似乎还有争议。我们之前所选择的估价函数是给定状态的魔方小块到它复原的位置和朝向所用的距离，其中这个距离并不是以空间距离衡量，而是由其初始位置到它当前状态所需要旋转魔方的次数衡量的。

现在它导致了一个问题，就是尽管算法可以保证最终结果不会收敛至局部最优，但是它有相当大的几率会一直搜索到一个局部最优的值然后再把它剪掉。比如当前有两种状态可供选择，一个是10，一个是20。10的那个经过20步会收敛至2。但是我们知道，一个复原的魔方无论将哪面旋转一次都会让各个小块距离的总和由0升为8，而程序不知道这一点，所以它会搜索到2发现在状态2所能应用的全部操作最终都会使得这个值比2大的时候，才会将整个从10开始的子树剪掉。

那么现在面临两个问题。一个是我的数据结构可能不太合适。因为我用了一个长为81的数组，用它来表示每一个状态所有可供选择的步数将会增加一个长为1557的数组。这样下去体积就会变得很大，所以需要编码，或者是设计新的数据结构。另外一个就是需要重新考虑估价函数。

1. /**  
2. //VideoIM文档生成日期：2005.10.12  
3. //  
4. //(1)概述：  
5. //类名称：StoreResources  
6. //类说明：  
7. //  将本应用中所有的固定字符串以及RMS所需要的KEY数值均集中于此,声明为static变量  
8. *   
9. //所在子系统：VideoIM  
10. //  
11. //系统总描述:  
12.         我们提供的VideoIM手机自动拍照上传器J2ME版本[开源]是  
13.         一个可以下载到手机(例如Nokia7610已经确实可以下载安装并正常运行)的应用程序，  
14.         用来自动驱动手机摄像头定时拍摄,并后台将JPEG图像(很小，大约几KB)上传到服务器上，  
15.         这样就可以帮助其他系统工作，比如PC机上的MSN Messenger可以和你的移动MSN Messenger  
16.         通过这种方式视频聊天，对方可以每隔十几秒钟看到你的手机所看到的画面了。  
17.   
18.      子系统描述：  
19.         VideoIM的功能列表：  
20.             1:我要MobileWebCam  
21.                 启动MobileWebCam  
22.                 停止MobileWebCam  
23.             2:MobileWebCam设置  
24.             3:关于我  
25.             4:退出  
26.   
27.   
28. //(2)历史记录:  
29. //创建人: 郑昀(2005.10.12)  
30. //联系我: Google Talk >> zhengyun@gmail.com  
31. //Blogs:    http://blog.csdn.net/zhengyun_ustc/以及http://www.cnblogs.com/zhengyun_ustc  
32.   
33. //(3)版权声明:  
34. //由于我这个版本的VideoIM手机自动拍照上传器也是基于Mowecam的设计理念基础上改编而来的，  
35. //所以决定遵照GPL协议的大意开放源代码，您可以自由传播和修改，在遵照GPL协议的约束条件的前提下。  
36.   
37. //(4)相关资源:  
38. 1：《[J2ME]VideoIM手机自动拍照上传器开源说明》  
39. 2：《[J2ME]VideoIM手机自动拍照上传器设计说明》  
40. 3：下载源代码：  
41.   
42. ////////////////////////////////////////////////////////////////////*/   
43. package com.ultrapower.common;   
44.    
45.    
46. /**********************************************************  
47. //StoreResources  
48. //  
49. //Class Description:  
50. //  提供一些常用的字符串资源以及RMS所需要的KEY数值  
51. //  
52. //Author:  
53. //     zhengyun@ultrapower 2005.10.12  
54. //  
55. **********************************************************/   
56. public class StoreResources {   
57.     /*  
58.      * RecordStore名  
59.      */   
60.     public static final String RECORDSTORE_NAME = "VideoIMStore";   
61.        
62.     /*  
63.      * 默认的player name  
64.      */   
65.     public static final String DEFAULT_PLAYER_NAME = "VideoIM";   
66.     /*  
67.      * 默认的抓拍图像的保存类型  
68.      */   
69.     public static final String DEFAULT_IMAGE_TYPE = "jpeg";   
70.     /*  
71.      * 远程服务器接受上传图像的页面地址  
72.      */   
73.     public static final String DEFAULT_REMOTESERVER    
74.         = "http://219.238.168.183/videoim/postimage.asp";   
75.        
76.     /////////////////////////////////////////   
77.     // 以下是关于抓拍图像的参数设置   
78.     /** Key for "抓拍图像的保存类型" (char[])*/   
79.     public static final int SNAPSHOT_IMAGE_TYPE     = 0;   
80.     /** Key for "抓拍图像的宽度" (int)*/   
81.     public static final int SNAPSHOT_IMAGE_WIDTH    = 1;   
82.     /** Key for "抓拍图像的长度" (int)*/   
83.     public static final int SNAPSHOT_IMAGE_HEIGHT   = 2;   
84.     /////////////////////////////////////////   
85.        
86.     /////////////////////////////////////////   
87.     // 以下是关于上传图像的参数设置   
88.     /** Key for player name(用来作唯一标示,以使用户将来能够取出上传的图像) (char[])*/   
89.     public static final int PLAYER_NAME             = 3;   
90.     /** Key for "远程服务器接受上传图像的页面地址" (char[])*/   
91.     public static final int REMOTESERVER_URL        = 4;   
92.     /////////////////////////////////////////   
93.        
94.     /////////////////////////////////////////   
95.     // 以下是关于抓拍图像的定时参数设置   
96.     /** Key for "每多少秒钟抓拍一次图像" (int)*/   
97.     public static final int TIMER_SNAPSHOT          = 5;;   
98.     /////////////////////////////////////////   
99.        
100. }   

这是用计算机摄像头的

首先到SUN下载最新的JMF，然后安装。http://java.sun.com/products/java-media/jmf/index.jsp

　　然后，说一下需求
　　1． 用摄像头拍照
　　2． 在文本框输入文件名
　　3． 按下拍照按钮，获取摄像头内的图像
　　4． 在拍下的照片上有一红框截取固定大小的照片。
　　5． 保存为本地图像为jpg格式，不得压缩画质
　　技术关键，相信也是大家最感兴趣的部分也就是如何让一个摄像头工作，并拍下一张照片了。
　　利用JMF，代码很简单：

//利用这三个类分别获取摄像头驱动，和获取摄像头内的图像流，获取到的图像流是一个Swing的Component组件类 public static Player player = null; private CaptureDeviceInfo di = null; private MediaLocator ml = null; //文档中提供的驱动写法，为何这么写我也不知：） String str1 = "vfw:Logitech USB Video Camera:0"; String str2 = "vfw:Microsoft WDM Image Capture (Win32):0"; di = CaptureDeviceManager.getDevice(str2); ml = di.getLocator(); try { 　player = Manager.createRealizedPlayer(ml); 　player.start(); 　Component comp; 　if ((comp = player.getVisualComponent()) != null) 　{ 　　add(comp, BorderLayout.NORTH); 　} } catch (Exception e) { 　e.printStackTrace(); }

　　接下来就是点击拍照，获取摄像头内的当前图像。
　　代码也是很简单：

private JButton capture; private Buffer buf = null; private BufferToImage btoi = null; private ImagePanel imgpanel = null; private Image img = null; private ImagePanel imgpanel = null; JComponent c = (JComponent) e.getSource(); if (c == capture)//如果按下的是拍照按钮 { 　FrameGrabbingControl fgc =(FrameGrabbingControl) 　player.getControl("javax.media.control.FrameGrabbingControl"); 　buf = fgc.grabFrame(); // 获取当前祯并存入Buffer类 　btoi = new BufferToImage((VideoFormat) buf.getFormat()); 　img = btoi.createImage(buf); // show the image 　imgpanel.setImage(img); }

1.
首先回顾一下Thistlethwaite算法，考虑如何用计算机喜欢的方式来表示它每一步要做什么工作。首先需要进行的工作就是去表示每个阶段应该达到怎样的目的。

1.<U, D, F, B, L, R> -> <U, D, F, B, L₂, R₂>
根据之前Thistlethwaite算法的描述，第一步是要把所有用<U, D, F, B, L₂, R₂>解不开的边块，用<U, D, F, B, L, R>解开。如前所述，魔方上有12个边块，也就意味着一个边块可以放在12种位置。考虑某个边块在任一种位置上都有两种方向(颜色的区别)，那么总的情况就是12*2=24种情况。同样一个边块要怎样才能绕一圈回到它原来的位置同时改变方向呢？它只要走过一个长度为奇数的路径就可以。譬如我们现在要将位于FR位置的边块调整方向，那么我可以进行F'U'R'操作。但是<U, D, F, B, L₂, R₂>群使得所有边块通过的路径均为偶数，所以每个边块只能位居两种方向之一，才能用<U, D, F, B, L₂, R₂>还原整个魔方。如果边块位于相反的方向，由于<U, D, F, B, L₂, R₂>不允许让边块以相反的方向回到那个位置，所以这个魔方是无法用<U, D, F, B, L₂, R₂>解开的。可以很简单地计算出来，12个不同的边块安放在12个不同的位置共有12!*2¹²种不同的排列，考虑组装正确的魔方不可能出现单独出现一个边块位于正确位置而方向错误的情况，所以前面那个数字应该除以2。但是现在“<U, D, F, B, L₂, R₂>能够将魔方开解”这个条件将前面那个数字缩减成了12!，因此这个剪枝的效果还是相当可观的。

同上一贴一样，使用1,2,3,4,5,6六种颜色对魔方的六种不同颜色进行区分。如果F方向为颜色3，那么对于边块{0, 3, _}("_"表示不管哪种颜色)、{3, 0, _}以及{_, 3, 0}都是<U, D, F, B, L₂, R₂>所解不开的，因此最开始的工作就是应该调整魔方，使得这些边块都不复存在。上述边块用Mathematica的表示方法可写为

{0, x_/;Mod[x, 3]==0, 0} (因为3和6是相对的两面)
{x_/;Mod[x, 3]==0, 0, _}
{_,x_/;Mod[x, 3]==0 , 0}

此外位于F、B面的颜色2、5亦受此影响，所以导致<U, D, F, B, L₂, R₂>不可解的边块还应包括

{0, _, x_/;Mod[x, 3]==2}
{x_/;Mod[x, 3]==2, _, 0}
{x_/;Mod[x, 3]==2, 0, _}

直到在上一贴中表示魔方状态的表里面找不到匹配上述模式的小块，那么stage1就算结束了。

2 <U, D, F, B, L₂, R₂> -> <U, D, F₂, B₂, L₂, R₂>
<U, D, F₂, B₂, L₂, R₂>的意思是说前后左右四个面只能转180°，这就意味着能用<U, D, F₂, B₂, L₂, R₂>所规定的操作解开的魔方肯定满足：a) 夹在上下两面中间的四个边块都已经在那一层(当然不一定要归位)和 b) 所有8个角块含有颜色3或者颜色6 (8个角块肯定不是含有颜色3就是含有颜色6)的那一面不是朝上就是朝下。

由于前后左右四个面的颜色分别为2、5、1、4，所以这四个边块只要满足
{x_/;Mod[x,3]==1, y_/;Mod[y,3]==2, 0}
就可以了。如果符合上述条件的边块找到了4个，那么就说明当前魔方的状态已经满足了条件a

8个角块状态的表示可以相对简单一些，因为如果能用<U, D, F₂, B₂, L₂, R₂>开解则意味着它们均满足以下条件
{x_/;x!=0, y_/;y!=0, z_/;Mod[z,3]==0}
如果能够找到8个这样的角块，那么就说明当前模仿的状态液晶满足了条件b

那么到此为止，魔方就可以用群<U, D, F₂, B₂, L₂, R₂>解开了。这一步操作确定了8个角块的朝向。有兴趣的可以自己算一下又将状态空间缩减了多少倍，我这里就不废话了。

3<U, D, F₂, B₂, L₂, R₂> -> <U₂, D₂, F₂, B₂, L₂, R₂>
能用<U₂, D₂, F₂, B₂, L₂, R₂>开解则意味着复原时应当位于相对位置的边块和角块现在已经处于相对位置。
所有角块搜索结束时应当满足
{x_/;Mod[x,3]==1, y_/;Mod[y,3]==2, z_/;Mod[z,3]==0}
位于上下两面夹层的边块条件仍如前所示，左右、前后夹层的边块条件也类似

4.<U₂, D₂, F₂, B₂, L₂, R₂> -> Initial
不废话了

2.接下来，就需要规定动作了。所谓的动作就是状态转移的规则。之前我曾经写过一个含有内部状态的函数，但是后来发现用那个展开搜索树十分不方便。因为Mathematica作为一个函数式编程语言是倡导引用透明的。然而内部状态破坏了引用透明性。所以我重新写了一个版本。

Swap[triple_List, n_Integer]:=Insert[triple[[n]], Reverse[Drop[triple, n]], n]
这个函数使得旋转时小块在位置变化的同时在方向上也能作出相应的改变。其中Drop返回列表中拿走第n个元素剩下的，Reverse是颠倒顺序，triple[[n]]是三元组中第n个，Insert是将位置1的元素插入位置2的列表中位置3的位置。简单地说，就是把第n个拿走，然后剩下的交换，然后再把第n个插回原位。

RotateCube[CubeTable_List, a_Integer, b_Integer]:=
Join[If[Positive[a],Reverse,1][Reverse@Transpose[Map[Swap, CubeTable[[Sequence@@Join[Table[All, {a-1}], b+2]]], {-2}]], CubeTable[[Sequence@@Join[Table[All, {a-1}], b+2-3]]]],{a}]

这个函数实现了全面的抽象旋转过程。它看起来很麻烦，是因为它要将需要旋转的部分抽出来进行操作，然后再把操作完后的结果同剩下的部分再结合起来。就好像将魔方上要旋转的九个小方块复制一份并转90°，再将剩余部分复制出一个副本，然后再将它们拼接起来。注意，它创造了一个新的旋转后的魔方，而原来那个魔方并没有改动。而在之前我写的是这个样子的：

RotateCube[CubeTable_List, a_Integer, b_Integer]:=
CubeTable[[Sequence@@Join[Table[All, {a-1}], b+2]]]=Reverse@Transpose[Map[Swap, CubeTable[[Sequence@@Join[Table[All, {a-1}], b+2]]], {-2}]]

注意上面用了一个等号，也就是赋值符号。上面的就意味着旋转后的新值覆盖了原来的值，同上面的例子相反，这个始终是在同一个魔方上进行操作的，就是CubeTable表。此处这个表就是全局变量了。

两者的差异可以参考按值传递和按引用传递的区别。当然Mathematica里要稍微复杂一些。Mathematica应该属于按引用传递，在函数是编程中并没有“变量赋值”这个概念，对应的概念是“建立规则”。求值的过程其实是将表达式求值得到的结果同表达式本身建立一种等价关系。因此上面两个实现魔方旋转的函数，前者是将函数求值得到的新CubeTable同表达式本身建立了关系，而后者是对原来的CubeTable进行操作，而表达式得到的值是Null。

定义好了RotateCube，生成一个搜索树就非常容易了，并且这种方法非常适用于Iterative Deepening。但是为了应用聪明一点的A*算法，还需要定义一个代价函数

“智能魔方机器人”。很好，我们现在有了魔方，有了NXT机器人，有了Thistlethwaite算法，并且还有下面那一坨代码(其实是一个电脑上显示魔方的可视化程序)，但是我仍然陷入困境。今天我终于有勇气站出来说，看来这个问题年前我解决不了了。不好意思，嘿嘿。

这个问题就是“智能”。

情况是这样的。尽管Thistlethwaite算法能将魔方求解缩减到很短的几个stage。但是在每个stage中仍然有不少状态(不超过四万个)。由于魔方本身结构决定了通过不同的操作可能导致相同的状态，换句话说如果想要将状态空间转化成一棵树，那么这棵树可能存在回路，因此尽管四万个状态并不算太多，但是由于操作的特殊性无法将所有情况枚举，然后探讨对于某种状态可以通过何种最短路径到达下一个stage。简单的BFS或者DFS回溯算法只能用于可行解的搜索，因为它们进行搜索只是单纯地根据拓展节点在搜索表中的顺序进行搜索的。如果说想要找到最优解(当然在我们这里最优解指的是最少的操作就可达到下一个Stage的操作序列)就不得不找到所有可行解然后再放到一起比较一遍，这看起来和枚举完全一样。所以需要一个聪明一点的搜索算法。

智能算法无非是“构造”和“逼近”。神经网络算是“逼近”的一种，它需要不断地犯错来修正内部结构，从而能够对于大部分的输入达到较为满意的响应。而“构造”则是要建立一个相当聪明的函数，这个函数需要设置的足够聪明，以致能够直接了解哪一个选择是正确的。一般这种方法叫做启发式搜索，我对这个还不太了解。搜索技术其实是一个空间非常广阔的领域，掌握扎实的搜索技术知识将会让你变成一个非常拽的程序员。可惜我目前还不是，当然我正在是 :)

尽管在之前的一段时间我并没有掌握搜索算法，但是我做了一些必要的辅助工作。大家都知道，搜索最重要的就是状态表示和状态判定。状态表示说具体一点就是数据结构的设计，我选择了这样的数据结构。

{{{{1,2,3},{1,2,0},{1,2,6}},{{1,0,3},{1,0,0},{1,0,6}},{{1,5,3},{1,5,0},{1,5,6}}},
{{{0,2,3},{0,2,0},{0,2,6}},{{0,0,3},{0,0,0},{0,0,6}},{{0,5,3},{0,5,0},{0,5,6}}},
{{{4,2,3},{4,2,0},{4,2,6}},{{4,0,3},{4,0,0},{4,0,6}},{{4,5,3},{4,5,0},{4,5,6}}}}

表中每个triple代表一个小方块的朝向，而从1至6的六个数字表示六种颜色。如果有一个是0，那么代表这是一个边块，如果有两个0则代表这是一个中心块儿。表的不同层次代表了魔方的不同表面。注意看表的第一行的所有triple的第一位都是1，就是说x轴负方向都是颜色1，而第三行对应位置都是4，就是说x轴正方向都是颜色4。每行前三个triple的第二位都是2，就是说y轴负方向都是颜色2，同理可知y轴正方向都是颜色5。如果按照三个三个将这些三元组分开(也就是倒数第二层括号)，那么每三个triples中第一个triple的最后一位是3，就意味着z轴负方向是颜色3，z轴正方向靠太累了我不说了。

这个数据结构能将魔方的状态唯一的确定，包括所有小块的位置和状态。这个数据结构完全没有进行编码和抽象，所以保留了完整的魔方信息。接下来就是要在这个数据结构上定义旋转操作。

旋转操作可以简单地表示为Reverse@Transpose[#]，#表示待旋转的9个小triples。如果将一个n阶方阵转置后再将第1列和第n列对调，第2列和第n-1列对调，那么得到的新的方阵就是将原来的方阵顺时针旋转90°。证明从略，不信你就试试。用它就可以表示魔方位于同一面的9个小块顺时针转90°。但是仅是位置发生变化还是不够的，因为小块的颜色朝向也会发生变化。譬如小块{1,2,3}如果沿z轴顺时针转动90°，那么z轴方向不变而原来朝着x轴的颜色1现在朝向了y轴，颜色2刚好相反，于是变成了{2,1,3}。如果定义这种选定了triple中的一个元素然后交换另外两个的操作叫做Swap，那么旋转操作就可以抽象地表示为Reverse@Transpose[Swap/@#]。具体实现的Mathematica代码我会稍后粘上来。

我先去研究搜索算法，今天先说这么多。