Franco.Chou's Space
Franco's Tech Blog
Where love goes? Chimera or Reality?
Posted by 于 2011年03月11日
I put this question into a carafe, throw it to the ocean, hope to get an answer.
I won’t be bathetic, I am calm enough. After experiencing all these, I am living with analgesia like an apparition. I used to be killed by agony caused by faith breaking, but now I’m OK even when the alergic memory comes back to my mind. Any suffering will be alleviated by time, that’s true. I even got amnesia, i’ve forgotten everything.
As for you, ambling in this world, fate always makes you ambivalent. After all, you are still a kid, maybe you are too callow to handle all these. I know, you are not calculated to hurt anyone including yourself. But, why you live like an apostate, shouldn’t you get the ablution of real love? And now I even feel your ailment aggravated.
In my world, I’m absolutely the authoritarian. I won’t blandish anyone if my soul told me no. You used to be get coronation in my kindom. But after you become acquisitive to some kind of love, the crown fell to the ground, broke into pieces. I concede, I didn’t give you enough aegis. But I guess it is not affordable by then even for now.
Maybe no one was corroded, and I will never be crestfallen of course. Everyone is the kid of God, they should get benediction all the same.
Let’s use astrology to end these. Aquarius doesn’t match to Pisces.
END.
C# WinForm — FolderBrowserDialog 在子线程中的使用（转）
Posted by 于 2011年03月2日
示例如下：
private void button3_Click(object sender, EventArgs e)
{
System.Threading.Thread s = new System.Threading.Thread(new System.Threading.ThreadStart(test));
s.ApartmentState = System.Threading.ApartmentState.STA;
s.Start();}
public void test()
{
FolderBrowserDialog browseDialog = new FolderBrowserDialog();
browseDialog.ShowDialog();
string selectPath = browseDialog.SelectedPath;
textBox2.Text = selectPath;
}
private void textBox2_TextChanged(object sender, EventArgs e)
{
}
以上代码演示了FolderBrowserDialog在子线程的使用，其中设置线程的ApartmentStateSystem.Threading.ApartmentState.STA是关键语句。COM提供的线程模型共有三种：Single－Threaded Apartment(STA单线程套间)，Multithreaded Apartment(MTA多线程套间)和Neutral Apartment/Thread Neutral Apartment/Neutral Threaded Apartment(NA/TNA/NTA中立线程套间，由COM＋提供)。
套间(Apartment),一个由用户界面线程（套间线程）和一个消息循环构成的概念性实体。套间定义了一度对象的逻辑集合，这些对象共享同一组并发性和重入限制。一个线程要想使用COM，必须先进入一个套间。COM规定，只有运行在对象套间中的线程才能访问该对象。
STA一个对象只能由一个线程访问，相当于windows的消息循环，实现方式也是通过消息循环的，ActiveX控件，OLE文档服务器等有界面的，都使用STA的套间。MTA一个对象可以被多个线程访问，即这个对象的代码在自己的方法中实现了线程保护，保证可以正确改变自己的状态。所以创建和访问一个activex或者ole对象时，必须设置线程模式为STA。
Internal linkage vs. External linkage
Posted by 于 2011年02月25日
Linkage
To understand the behavior of C and C++ programs, you need to know about linkage. In an executing program, an identifier is represented by storage in memory that holds a variable or a compiled function body. Linkage describes this storage as it is seen by the linker. There are two types of linkage: internal linkage and external linkage.
Internal linkage means that storage is created to represent the identifier only for the file being compiled. Other files may use the same identifier name with internal linkage, or for a global variable, and no conflicts will be found by the linker – separate storage is created for each identifier. Internal linkage is specified by the keyword static in C and C++.
External linkage means that a single piece of storage is created to represent the identifier for all files being compiled. The storage is created once, and the linker must resolve all other references to that storage. Global variables and function names have external linkage. These are accessed from other files by declaring them with the keyword extern. Variables defined outside all functions (with the exception of const in C++) and function definitions default to external linkage. You can specifically force them to have internal linkage using the static keyword. You can explicitly state that an identifier has external linkage by defining it with the extern keyword. Defining a variable or function with extern is not necessary in C, but it is sometimes necessary for const in C++.
Automatic (local) variables exist only temporarily, on the stack, while a function is being called. The linker doesn’t know about automatic variables, and so these have no linkage.
在大规模的情况下，拜托不要用递归啦
Posted by 于 2011年01月3日
这句话如此重要以至于我用一篇日志的篇幅来点醒自己！！
想想 700*700的矩阵，假如dfs以此递归一次，700*700*4=1914KB=1.86M 什么情况，也就是每次递归仅仅产生一个int，就要消耗1.86M的栈内存。一个进程，系统可是仅仅给你最多2M的内存的喔！！
圖的連通性，環路 以及 兩節點之間的最短路徑問題
Posted by 于 2010年12月30日
先發表點小感慨.. 其實練習算法和軟件工程之間某些準則還是有衝突的。看到算法里一堆全局變量以及閱讀性極差的編程方式，總感覺不爽。雖然老師也有講算法沒必要遵循那一套，但是還是小有糾結。 自己還是偏執的覺得應該儘量面向對象，必要的類和函數還是不可少的。
—–
進入正題，關於圖的一些基本知識。
關於圖的連通性和環路
假若圖是用鄰接矩陣的表示形式，並且矩陣中的值指的是某兩個結點之間的通路數。那麼，鄰接矩陣自乘N次代表N-1步后的通路情況，並且M(i,i)代表環路的情況。
這是線性代數在圖的連通性計算中的重要應用。
證明如下：
—————————————–
有向图的邻接矩阵
设有向图
，
，
。令
为
邻接到
的边的条数，称
为D的邻接矩阵，记作
。
为图7.12的邻接矩阵，不难看出：
(1)
(即第i行元素之和为的出度)，
。
(2)
(即第j列元素之和为的入度)，
。
(3)由(1)，(2)可知，
为D中边的总数，也可看成是D中长度为1的通路总数，而
为D中环的个数，即D中长度为1的回路总数。
D中长度大于等于2的通路数和回路数应如何计算呢？
为此，先讨论长度等于2的通路数和回路数。
在图D中，从顶点
到顶点的长度等于2的通路，中间必经过一顶点
。对于任意的k
，若有通路
，必有
且
，即
。反之，若D中不存在通路，必有
或
，即
。于是在图D中从顶点到顶点的长度等于2的通路数为：
由矩阵的乘法规则知，
正好是矩阵
中的第i行与第j列元素，记
，即
就是从顶点到顶点的长度等于2的通路数，
时，
表示从顶点到顶点的长度等于2的回路数。
因此，
即
矩阵中所有元素的和
为长度等于2的通路总数(含回路)，其中对角线的元素和
为长度等于2的回路总数。
根据以上分析，则有下面的推论。
定义 有向图，
，D中长度为
的通路数和回路数可以用矩阵
(简记
)来表示，这里
，其中
，
即 
则
为顶点到顶点长度为的通路数，
为到自身长度为的回路数。中所有元素之和
为D中长度为的通路数，而中对角线上元素之和
为D中始于(终于)各顶点的长度为的回路数。
在图7.12中，计算
，
，
如下：
观察各矩阵发现，
，
，
。于是，D中
到
长度为2的通路有3条，长度为3的通路有4条，长度为4的通路有6条。由
，
，
可知，D中到自身长度为
的回路各有1条(此时回路为复杂的)。由于
，所以D中长度为2的通路总数为10，其中有3条回路。
从上述分析，可得下面定理。
定理7.5 设
为有向图D的邻接矩阵，，则
中元素为到长度为的通路数，
为D中长度为的通路总数，其中为D中长度为的回路总数。
若再令矩阵
，
，
……
，
上面定理有下面推论。
推论 设
，则
中元素
为D中到长度小于等于
的通路数，
为D中长度小于等于的通路总数，其中
为D中长度小于等于的回路总数。
————————————————————
關於圖的最短路徑，常用的是Dijsktra算法
下面以題目為例：（Sicily 1031）
Sample Input
Copy sample input to clipboard
1 //case的數量 2 //通路的條數 South.xiaolitang South.xiongdelong 2 //通路及metric South.xiongdelong Zhuhai.liyuan 100 South.xiongdelong South.xiaolitang //計算該起始地址到目的地址的最短路徑長度
Sample Output
2 //輸出最短路徑長度
----------------------------------------------
#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#define MAXINT 65535
using namespace std;
class route
{
public:
string src;
string dst;
int metric;
};
int ini_graph(int**& matrix_ptr,map<string,int>& index_location_map);
void printmatrix(int** matrix,int f);
void destorymatrix(int** matrix,int f);
void Dijsktra(int** matrix,int f,map<string,int> index_location_map,string src,string dst);
int main()
{
int c;
cin >> c;
for(int i = 0; i < c; i ++)
{
int f;
int **matrix_ptr = NULL; //图邻接矩阵
map<string,int> index_location_map; //index和location的对应关系
f = ini_graph(matrix_ptr,index_location_map);
//printmatrix(matrix_ptr,f);
string src,dst;
cin >> src >> dst;
Dijsktra(matrix_ptr,f,index_location_map,src,dst);
destorymatrix(matrix_ptr,f);
}
return 0;
}
int ini_graph(int**& matrix_ptr,map<string,int>& index_location_map)
{
int c;
cin >> c; //路的条数
vector<route> routes;
int f = 0;
for(int i = 0; i < c; i ++)
{
route r;
string src;
string dst;
int metric;
cin >> src >> dst;
cin >> metric;
r.src = src;
r.dst = dst;
r.metric = metric;
routes.push_back(r);
r.src = dst;
r.dst = src;
routes.push_back(r); //因为是无向图,两个方向都要
typedef map<string,int> String2int;
if(index_location_map.find(src) == index_location_map.end()) //若找不到src
{
index_location_map.insert(String2int::value_type(src,f));
f ++;
}
if(index_location_map.find(dst) == index_location_map.end()) //若找不到dst
{
index_location_map.insert(String2int::value_type(dst,f));
f ++;
}
}
//构造邻接矩阵
//分配空间
matrix_ptr = new int*[f];
for(int i = 0; i < f; i ++)
matrix_ptr[i] = new int[f];
//初始化邻接矩阵，设为MAXINT
for(int i = 0; i < f; i ++)
for(int j = 0; j < f; j ++)
{
matrix_ptr[i][j] = MAXINT;
}
for(int i = 0; i < f; i ++)
matrix_ptr[i][i] = 0;
for(int i = 0;i < routes.size(); i ++)
{
matrix_ptr[index_location_map[routes[i].src]][index_location_map[routes[i].dst]] = routes[i].metric;
}
return f;
}
void printmatrix(int** matrix,int f)
{
for(int i = 0; i < f; i ++)
{
for(int j = 0; j < f; j ++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
void destorymatrix(int** matrix,int f)
{
for(int j = 0; j < f; j ++)
{
delete[] matrix[j];
}
delete[] matrix;
}
void Dijsktra(int** matrix,int f,map<string,int> index_location_map,string src,string dst)
{
if(src==dst)
{
cout << "0" << endl;
return;
}
if(index_location_map.find(src)==index_location_map.end()||index_location_map.find(dst)==index_location_map.end())
{
cout << "-1" << endl;
return;
}
int srcnum = index_location_map[src];
int dstnum = index_location_map[dst];
//初始化距离向量
vector<int> distance_vector;
for(int i = 0; i < f; i ++)
{
distance_vector.push_back(matrix[srcnum][i]);
}
vector<int> s; //s集合
s.push_back(srcnum);
vector<int> t; //t集合
for(int i = 0; i < f; i ++)
{
if(i != srcnum)
t.push_back(i);
}
int min_num;
int tc;
int d;
for(int i = 0; i < f; i ++)
{
if(i != srcnum)
{
min_num = MAXINT;
tc = 0;
d = t[0]; //这两行不加的话
//第i行
for(int j = 0; j < s.size(); j ++) //最核心部份。遍歷S中各個元素到T中各個元素
{
int k;
for(k = 0; k < t.size(); k ++)
{
if(distance_vector[t[k]]>(distance_vector[s[j]]+matrix[s[j]][t[k]]))
{
distance_vector[t[k]] = matrix[s[j]][t[k]]+distance_vector[s[j]]; //更新距離矢量
}
if(min_num>distance_vector[t[k]])
{
min_num = distance_vector[t[k]];
tc = k;
d = t[k];
}
}
}
s.push_back(d);
t.erase(t.begin()+tc);
}
}
if(distance_vector[index_location_map[dst]]!=MAXINT)
cout << distance_vector[index_location_map[dst]] << endl;
else
cout << "-1" << endl;
}
———————————-
《1988-我想和这个世界谈谈》
Posted by 于 2010年12月20日
中午的时候很惊叹卓越的出货速度，昨晚很晚才订的书今天中午就到了，很是惊喜。于是中午慵懒的爬起来去取书。混迹饭堂，图书馆，自然辩证法课堂，用了大约3个半钟就看完了。
豆瓣上褒贬不一，自己看完也是五味杂陈，似乎书里面的世界是那么熟悉，但又是那么陌生。说实话，不知道是不是我还未充分深入探析，目前来说对这本书倒是也没太多的感觉。
且不去过多研究“公路小说”的成色，受其影响，我总觉得主人公就是“韩寒”，或许他车开多了吧。但是结合书里面的情节把主人公和韩寒本人联系起来，总是感觉怪怪的。至于那个怀孕的妓女，或许他是想表达目前被社会强奸的当代人，而她的“孩子”或者就是她的一个寄托和一个梦。但从书中的描述来看，这个孩子注定却也是悲剧，因为他甚至不知道她的生父是谁，更不知道自己的未来在何方 — 或者去朝鲜留学，回来“光宗耀祖”？ 最后，妓女因为各种各样的病死了，孩子被寄托在了主人公手中，面对浑浊的一切，其实也不知道何去何从。 结合面对着“温水煮青蛙”的谎言，以及青蛙想要跳出而被锅盖挡住，被沸水烫死的过往经验，以及正义必将战胜邪恶，但是掌权者可以定义什么是正义的无奈，整个基调有些低沉及灰暗。
其回忆的儿时的一些东西，我虽然很熟悉，却难以有共鸣 — 不知道是否有“代沟”。在小学的时候，早已经不会把什么“革命”“反革命”之类的挂在嘴边。虽然也会有暗恋女孩子，也会跟要好的朋友讨论女生如何如何；也会有疑惑红领巾是用“鲜血”染红的，那是不是会整天要去工厂用血去染布。但是，在书中的视角下，总是萦绕着一层厚重的折射镜。在我的记忆中，儿时的伙伴都是天真到不行。或者书中想拿那些最终或死或被投去监狱的伙伴来隐喻什么，但是实在难以引起我的共鸣。
至于主人公的女友“孟孟”，那里描述的有段话我倒很喜欢：“我走的比她慢，只是她在超越我和我并肩的时候我推了她一把，仅此，这是所有我能做的，而后，她离开了我的臂长范围，我只能给她喊几句话，再远，她就听不到我说什么了。我不想走得快一些，因为那是我的节奏，在哪个节奏里我已经应接不暇。”或许是自己有类似的经历吧，我也不习惯无休止的追逐，特别是在追求一些我觉得很无趣的事情的时候。现代人确实有些忙碌，追名逐利到疯狂，虚荣的面具带了一层又一层。
其实分析一下自己，自己带着自欺欺人的保护罩幸运的落在了世界上一个比较柔软的地方。对于一些不愿意看到的，或者一些暗面，大可“自欺欺人”的去无视了。当然，世界上不公平大把，好吧，中国不公平的事大把。但，我个人觉得，如果每个人都以各自的理想为主体，而不是一味去埋怨这个时代会更好。毕竟，目前来讲趋势还是好的，并且也没那么那么的黑暗。况且“黑暗势力”再庞大，我们才是未来的主体 — 尚是白纸的婴儿。当然，此类的“鞭挞”必不可少，这是社会进步的催化剂，而我们每个人的努力才是社会进步的驱动力嗬。
反省
Posted by 于 2010年12月10日
<刚刚打开Windows Live Writer的时候，发现上次版本更迭后变成了Writer 2011，不由得嘴角上扬 — 确实蛮符合我现在的心情嘛~>
今天不知道是 出于什么原因，突然有一种心情：要对之前的自己的行为进行反省，以此“赎罪”。每年每年都在反省，而今年又快过去了，我也来慢慢的对今年的“所做所为”来一个总结，对未来有个小小的展望。
2010年是非常神奇的一年，期间发生的事情也跌宕起伏。其实对于命运女神赐予我的身份，总是在“幸运儿”和“弃儿”之间交替。 最大的幸运是：我能听从孙老师的教诲，最终踏上了读研的道路。 孙老师，虽然您可能不知道，但是在我的心里我真的非常非常感谢您，您的教诲真的会影响到我的一生！我永远也不会忘记您没有吃饭等我到晚上10点，开车带我去吃晚饭谈心的那个晚上。 不幸运的是：我对于职场产生了陌生感和不确定感。连带去年去应聘IBM的实习生，到今年年初去应聘腾讯上海研究院，面完之后的心情无论是信心满满还是低落万分，最后都被刷掉了。这让我对自己的职业生涯有些信心不足。
上半年，由于是毕业班，大家都很疯狂。除开忙完毕业论文的事，就被毕业旅行，各种聚餐和各种玩乐占据了。好吧，上半年的得失我就不再去追究，毕竟“毕业”这个理由有够充分。况且加入东校研究生会去当了个学术部副部长虽然是不务正业，但是认识了很多好朋友；加入cisco team更是认识了很多牛人朋友！！
暑假的那两个月，那个项目我也不能多埋怨自己什么，加上做大四孩子们的实训TA也很enjoy，cisco team的training也很enjoy，所以pass….
下半年，开始的踌躇满志，希望能达到某个目标，开始有够认真，一直持续了半个学期。期间一直在好好温习《Thinking in C++》,好好做算法和研习模式识别。但是之后，被老师讲说研究方向性错误，恰逢其中考试，不知道为什么，就如分水岭般懈怠了好多。虽然也有下载论文来看，但总是感觉静不下心来。并且，C++也没看了，算法也懈怠了。之后也被分手这种无聊的事情影响，并以此为借口没有认真学习，跑去AIESEC和一堆小朋友玩去了，整天虽然陪外国友人逛幼儿园逛街很开心，但却是浪费了不少时间。研会的“百川交汇”也故作焦头烂额状，其实也是以此为借口浪费了不少学习时间。至此，已经进入了期末考试月，由于固执的不喜欢java，一做java那死鬼作业也有所怨恨及懈怠。并且10多天来，天天早上逃课睡到中午 — 以不想上无聊课为借口浪费了不少本应该是学习的时间。期末考试的分数也是我追求的目标之一，却天天在抱怨作业的无聊，实属不该！
反省如下：
1。不要轻易被影响情绪，要把握好自己的方向。
2。别借口多多，你其他事情其实没有那么忙
3。要有一个完整的规划，并要严格按照计划来进行
4。还有，别整天微波校内的了，人都变傻了！！！
完
好吧，要淡定… 无论在什么情况下….
最近
Posted by 于 2010年11月16日
最近发生很多事情.
似乎分手以后，让我的记忆力衰退的很严重，这让我很伤脑筋。我试着开心起来，我做不到，虽然我总是试图让自己保持微笑；我试着痛恨起来，我也做不到，每个人的选择不同而已吧。至于对面选择的方式，它将改变我的人生观特别是爱情观也肯定是既定的事实。只留着胸前感觉到的压抑，像广州的天空，像夜半月光下的浮云。
于是我感到特别的寂寞，甚至有些无助。我记得三天前我特别特别渴望别人的拥抱。
我是天生不会流泪的人，只会双手抚耳，听着耳机里不想被人打扰的“呼吸”。
我也曾仰望天空，with my vampire teeth.
但是，愈是这样，愈是感到孤独寂寞啊。
对于人群，既有引力也有斥力。周末的联合书店，也只是一个人倚在三楼到四楼的楼梯上，静静的看看书.. 不经意的无尽的落寞。2个小时后，起身，推搡着陌生的人群，顶着眉际发间恍惚的阳光走进地下铁，眼神呆滞。
我在想，这样的一段时间总是会过去的吧。
写在要我死之前—-回溯，搜索树
Posted by 于 2010年10月26日
好久没有写日志了.. 其实最近还是做了一些东西，只是懒得传上来。
题外话：关于“二维转三维”的议题，看来方向性是对的，只是方法有些偏差了。之前的想法：分析图片，用3D模型来替换的方法显的很傻很天真。近来所做的模式识别方面的工作显得有点不务正业了. 孙老师提的关于“点云”的思想确实有价值很多。
还是把关于模式识别关于贝叶斯分类器和线性分类器的总结传一下.. 在skydrive里头
——————————————————————————————————-
回来这篇文章：回溯和搜索树
近来在sicily上面做了一些题，搜索树和回溯的居多，看来还是很有必要好好总结一下。
其实要注意两个概念：“回溯”和“深搜”是两个不同的概念。虽然，我们经常用“深搜”来“回溯”，但是“回溯”却不一定要是“深搜”。
举个比较简单的例子：N皇后问题【关于题目我就不在赘述了，大家懂的】
核心代码：
#include <iostream>
using namespace std;
void n_queens(int n,int* ans);
bool place(int k,int* ans);
int main()
{
int n;
cout << "please input the quantity of Queens:";
cin >> n;
int *ans = new int[n+1];
n_queens(n,ans);
for(int i = 1; i <= n; i ++)
cout << ans[i]<< " ";
cout << endl;
delete[] ans;
return 0;
}
void n_queens(int n,int* ans)
{
int k = 1;
ans[k] = 0;
while(k>=0)
{
ans[k] ++;
while((ans[k]<=n)&&(!place(k,ans)))
ans[k] ++;
if(ans[k] <= n)
{
if(k == n) break;
k ++;
ans[k] = 0;
}
else
{
ans[k] = 0;
k –;
}
}
}
bool place(int k,int* ans)
{
for(int i = 1; i < k; i ++)
{
if((ans[i] == ans[k])||(abs(ans[i]-ans[k])==abs(i-k))) //检测该位置与之前所摆的位置有没有冲突。
return false;
}
return true;
}
这段代码也经常作为“回溯”的经典教材例子。
在这段代码中，我们可以很清楚的看到并没有用到“搜索树”，而是用了一个解向量就解决了。
但是，“深搜”还是回溯比较常用的方法。原因在于“深搜”对过程的控制更加好。
举个具体的例子：
sicily里面的马周游问题：
——————————————————————————
在一个5 * 6的棋盘中的某个位置有一只马，如果它走29步正好经过除起点外的其他位置各一次，这样一种走法则称马的周游路线，试设计一个算法，从给定的起点出发，找出它的一条周游路线。
为了便于表示一个棋盘，我们按照从上到下，从左到右对棋盘的方格编号，如下所示：
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
马的走法是“日”字形路线，例如当马在位置15的时候，它可以到达2、4、7、11、19、23、26和28。但是规定马是不能跳出棋盘外的，例如从位置1只能到达9和14。
———————————————————————————————-
我们参照N皇后问题的方法，我们可以写如下代码：
#include <iostream>
#include <cstdlib>
using namespace std;
struct step
{
int stepflag;
int position;
};
struct point
{
int x;
int y;
};
void Horsewonder(int m, int n,step* ans,int start);
bool location(int m, int n, int k,step* ans);
int main()
{
int m = 5;
int n = 6;
step* ans = new step[m*n+1];
int start;
cin >> start;
while(start!=-1)
{
Horsewonder(m,n,ans,start);
for(int i = 1; i < m*n; i ++)
cout << ans[i].position << " ";
cout << ans[m*n].position << endl;
cin >> start;
}
return 0;
}
void Horsewonder(int m, int n,step* ans,int start) //对比N皇后问题的代码。
{
int k = 1;
ans[k].position = start;
for(int i = 1;i <= m*n; i++ )
ans[i].stepflag = 0;
k ++;
while(k>1)
{
ans[k].stepflag ++;
while(ans[k].stepflag<=8&&!location(m,n,k,ans))
ans[k].stepflag ++;
if(ans[k].stepflag <= 8)
{
if(k==30) break;
k ++;
ans[k].stepflag = 0;
}
else
{
ans[k].stepflag = 0;
k –;
}
}
}
bool location(int m, int n,int k,step* ans)
{
point p;
int temp;
temp = ans[k-1].position;
p.y = (ans[k-1].position-1)/n;
p.x = (ans[k-1].position-1)%n;
if(ans[k].stepflag == 1)
{
p.x –;
p.y = p.y – 2;
}
else if(ans[k].stepflag == 2)
{
p.x –;
p.y = p.y + 2;
}
else if(ans[k].stepflag == 3)
{
p.x ++;
p.y = p.y – 2;
}
else if(ans[k].stepflag == 4)
{
p.x ++;
p.y = p.y + 2;
}
else if(ans[k].stepflag == 5)
{
p.x = p.x – 2;
p.y –;
}
else if(ans[k].stepflag == 6)
{
p.x = p.x – 2;
p.y ++;
}
else if(ans[k].stepflag == 7)
{
p.x = p.x + 2;
p.y –;
}
else if(ans[k].stepflag == 8)
{
p.x = p.x + 2;
p.y ++;
}
if((p.x<0)||(p.x>(n-1))||(p.y<0)||(p.y>(m-1)))
return false;
temp = p.y*n+p.x+1;
for(int i = 1; i < k; i ++)
if(ans[i].position == temp )
return false;
ans[k].position = temp;
return true;
}
为了应用 ans[k].stepflag ++; 我将每个编号和相应的周游方向进行了映射. 【原谅代码的啰嗦，智商不够…】
当然，在这里我是硬套N皇后问题的代码的。我们可以看出一个问题，这个方法非常暴力。每当到达一个状态，我会非常暴力的搜索接下去的所有状态。
当这个矩阵变成8*8甚至更大时，寻找解向量的速度将会非常非常慢！
当面对大矩阵时，牛人们提出一种方法：比如走到某步为一节点，我们对其子节点的“子节点数目”进行排序。先从“子节点数目”比较少的子结点开始搜索。【我也不知道为什么这样会快很多.. 但结果表明确实是快太多了。= = 无论如何，很明确的一点是：过程控制在搜索过程中非常重要！】
这个时候，单单从以上代码开始修改会显得非常困难。我们用“深搜”的方法，因为“过程控制更加好”。
代码如下：
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
bool flag[8][8];
vector<int> route;
int dir[8][2]={-1,-2,-1,2,1,-2,1,2,-2,-1,2,-1,-2,1,2,1};
class point
{
public:
int x;
int y;
};
class node
{
public:
point location;
int chilcnt;
};
point num2point(int num);
int point2num(point p);
bool legal(point p)
{
if(p.x<0||p.x>7||p.y<0||p.y>7)
return false;
else
return true;
}
bool existbefore(point p)
{
return flag[p.x][p.y];
}
int nodechilcnt(point p)
{
int cnt = 0;
flag[p.x][p.y] = true; //把这个也记录在flag中
for(int i = 0; i < 8; i ++ )
{
point temp;
temp.x = p.x + dir[i][0];
temp.y = p.y + dir[i][1];
if(legal(temp)&&!existbefore(temp))
cnt ++;
}
flag[p.x][p.y] = false;
return cnt;
}
bool cmp(node n1, node n2)
{
return n1.chilcnt < n2.chilcnt;
}
void dfs(int num) //深度优先搜索
{
point p = num2point(num);
if(route.size()<64)
{
route.push_back(num);
flag[p.x][p.y] = true;
}
if(route.size() == 64)
return;
vector<node> childrens; //过程控制体现在这里，我们会记录一系列结点信息，对接下去的搜索进行控制。
int cnt = 0;
for(int i = 0; i < 8; i ++ )
{
point temp;
temp.x = p.x + dir[i][0];
temp.y = p.y + dir[i][1];
if(legal(temp)&&!existbefore(temp))
{
node t;
t.location = temp;
t.chilcnt = nodechilcnt(temp);
childrens.push_back(t);
}
}
sort(childrens.begin(),childrens.end(),cmp);
for(int i = 0; i < childrens.size(); i ++)
dfs(point2num(childrens[i].location));
if(route.size() == 64)
return;
flag[p.x][p.y] = false;
route.pop_back();
}
int main()
{
int num;
cin >> num;
while(num != -1)
{
for(int i = 0; i < 8; i ++)
for(int j = 0; j < 8; j ++)
flag[i][j] = false;
route.clear();
dfs(num);
int i;
for(i = 0; i < route.size()-1; i ++)
cout << route[i] << " ";
cout << route[i] << endl;
cin >> num;
}
}
point num2point(int num)
{
point t;
t.x = (num-1)%8;
t.y = (num-1)/8;
return t;
}
int point2num(point p)
{
return 8*p.y + p.x + 1;
}
关于“深搜”和“回溯”的关系我就先理解到这里，肯定有很多不完善的地方，以后再慢慢改进。
Franco.Chou's Space 
近期评论