Hopping dots (独立钻石棋变种)攻略

版权申请有特殊教育需求:冠词是视频博客作者的原型文字。,不博主答应,不得推测转载。。

序言:冠词,我以为议论一整个的游玩。,呼叫跳频 dots,翻译成逻辑难以应付的成绩或制约。

关键词:独立钻石棋、吃水表面下的搜索、可能性辨析、条款紧缩、静态展现节略办法

一,下载互连

点击翻开互连(是人互联网网络) 或许点击翻开的互连(是人我的百度云)

我的版本:Hopping dots 1.1

二,游玩相间的、西洋跳棋盘、起草人

(下面是第做事有效率的)

西洋跳棋盘是由13点结合的。


起草人:1颗白色的种子和大多数人的绿色的种子。

三,主力队员

鉴于独立钻石棋的主力队员举行吃子,只剩一孩子了。,为了红少年,那就是赢。不管怎样白色在哪里。

这是我本身的主力队员。,罕有的简约,开端时样子是笔误的。,慎重故意的有效地和权力构成释义相当地。。

四,初步看法

1,起草人的本利之和

至多有12件。,至多有1个。。

这13片必然是死了。,因缺勤办法用双手触摸、举起或握住。。

12卒制约,缺勤生活环境。,这是权未知的。。

2,起草人数的变奏

每个用双手触摸、举起或握住,件数少于1件。,因而,无论哪一个期望,至多后果却11个手术。

3,成绩使简易

成绩使简易版:后果却绿色的少年缺勤白色的结实器官。,倘若只剩一孩子了。那就是赢(异样无论评价地)

这般的版本就更将近独立钻石棋了,精确,除非西洋跳棋盘和独立钻石棋不相当地那一边,缺勤区别对待。。

为球员,原成绩和成绩使简易版不符合并变动从而产生断层很大,这快要是很难玩的。。

向那些的意指或意味做原理辨析的人,,构成者的成绩辨析起来很复杂。,覆盖物大多数人法度。

倘若你只想正好写吃水表面下的搜索顺序到S,缺勤必要举行使简易。,再倘若你想设法对付更刚硬的。,率先,从原理上辨析了可能性变得越来越大。,因而使简易是要做的第一步。。

4,期望的本利之和(成绩使简易版)

有13点可能会有孩子。,因而制约的本利之和是2 ^ 13=8192。

它也包含很多闭塞不通的一头。,有这么些具体制约?,人们非物质的。。

5,编号


6,记载全部边(不思索形势)

不难计数,有16个关心。

以2、6、8、12向暗正中鹄的每一侧,有1个。,如1-2-3

以4、5、9、10个暗中有2个边。,如1-4-7,2-4-6

以7为暗中点,有4个关心。,如2-7—12,4-7-10

不思索形势,因无论哪一个工夫。,一面对应于一可塑的的用双手触摸、举起或握住。,

以边1-2-3为例,在异样的制约下,从1到3和从3到1都是不克不及整个用双手触摸、举起或握住的。。

注意到,每边的3个数字是相当的限度局限。,因而附和只需求记载2位数字。,

这般,你可以应用2个16个上浆的限度局限来记载16个边。。

int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};

五,吃水表面下的搜索的可能性辨析(成绩使简易版)

因至多后果却11个手术。,因而吃水表面下的搜索变动从而产生断层很深。。如今需求计算的是,每个用双手触摸、举起或握住有这么些种选择?

1,在无论哪一个制约下有这么些选择?

人们需求一重大聚会。,出口一期望,出口数值,通知人们人们有这么些选择。。

若何出口?应用条款紧缩是最手边的的。。

13点,每个点对应于一多少。,1打算孩子。,0打算缺勤孩子。,这般,8192个期望便可以和8192个13位二元系数一一对应了。

出口后来的,该重大聚会可以正好计算选择的本利之和。,工夫是O(1)。

用这么重大聚会,只从0到8191详表n。,你可以找出f(n)的峰值。,出狱10

信号:

#includeusingnamespace std;int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};intf(int n){int r =0, s, e, m;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if((n >>(13- m))&1)r +=((n >>(13- s))&1)^((n >>(13- e))&1);}return r;}intmain(){int maxx =0;for(int n =0; n <8192; n++)if(maxx <f(n))maxx =f(n);
	cout << maxx;return0;}

2,吃水表面下的搜索的错综复杂的状态

找出后面。,一制约至多可以运转11次完毕。,每个用双手触摸、举起或握住至多10种选择,这么,用吃水表面下的搜索处理这么成绩至多需求10^11次详表计算。这是一罕有的大的数字。,普通笔记本电脑要花很长工夫。。

而是,人们可以简单明了地发现物。,并非每个用双手触摸、举起或握住都有10种选择,譬如只剩2身材的时分至多后果却2种选择。

倘若制约有K(1)

只需应用下面重大聚会f。。

信号:

#includeusingnamespace std;int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};int num[14];voidf(int n){int r =0, s, e, m, k =0;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if((n >>(13- m))&1)r +=((n >>(13- s))&1)^((n >>(13- e))&1);}while(n){
		k += n &1;
		n /=2;}if(num[k]< r)num[k]= r;}intmain(){for(int i =0; i <14; i++)num[i]=0;for(int n =0; n <8192; n++)f(n);for(int i =2; i <=12; i++)cout << num[i]<<"  ";return0;}

运转后果:

2  4  7  7  9  10  9  9  8  6  4

2*4*7*7*9*10*9*9*8*6*4=548674560,因而无论哪一个制约下。,举行吃水表面下的搜索的话,至多需求约5亿次详表计算

计算性能在一秒钟内计算大概1亿次。,因而这次是可以受理的。。

七,处理原始成绩

最好的的成绩是鉴于对白色子女的限度局限。,去训练更为复杂。,但缺勤必要倾斜。。

这般,你可以经过吃水表面下的搜索来处理这么成绩。,同时,因制约的本利之和是直达的火车或汽车的。,因而用静态展现节略办法来预防反复任务。

信号:

#include#includeusingnamespace std;int r[8192][14];int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};
stack<int>ans;boolf(int n,int k){if(n ==(n&-n))returntrue;if(r[n][k]<0)returnfalse;int s, e, m;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if(m == k)continue;if(!((n >>(13- m))&1))continue;if(!(((n >>(13- s))&1)^((n >>(13- e))&1)))continue;int nn, kk = k, tem;if(k == s || k == e)kk = s + e - k;
		tem =(1<<(13- s))+(1<<(13- e));
		nn = n -(n&tem)+ tem -(n&tem)-(1<<(13- m));if(f(nn, kk)){
			ans.push(i);
			m =-1;break;}}if(m ==-1)returntrue;
	r[n][k]=-1;returnfalse;}intmain(){int n =0, k;
	cout <<按编号\n1    2    3\n  4    5\n6    7    8\n  9    10\n11   12   13\n";
	cout <<完全。,从左往右,顺次出口每个点阵。\n1打算孩子。,0打算缺勤孩子。,全部都被空白表格隔开了。\n";for(int i =1; i <=13; i++){
		cin >> k;
		n = n *2+ k;}
	cout <<"出口红子评价格子的序号(1-13)\n";
	cin >> k;for(int i =0; i <8192; i++)for(int j =0; j <14; j++)r[i][j]=0;while(!ans.empty())ans.pop();f(n, k);
	cout <<"答案为:(共有的表现一用双手触摸、举起或握住),每个行正中鹄的2个整体区别对待表现获得学位点和完毕点。\n";while(!ans.empty()){int i = ans.top();
		ans.pop();
		cout << st[i]<<"   "<< en[i]<< endl;}return0;}

示例:




发表评论

电子邮件地址不会被公开。 必填项已用*标注