分享
 
 
 

排列组合与回溯算法浅谈

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

[原创] KuiBing 2003-11-14

这篇论文主要针对排列组合对回溯算法展开讨论,在每一个讨论之后,还有相关的推荐题。在开始之前,我们先应该看一下回溯算法的概念,所谓回溯:就是搜索一棵状态树的过程,这个过程类似于图的深度优先搜索(DFS),在搜索的每一步(这里的每一步对应搜索树的第i层)中产生一个正确的解,然后在以后的每一步搜索过程中,都检查其前一步的记录,并且它将有条件的选择以后的每一个搜索状态(即第i+1层的状态节点)。

需掌握的基本算法:

排列:就是从n个元素中同时取r个元素的排列,记做P(n,r)。(当r=n时,我们称P(n,n)=n!为全排列)例如我们有集合OR = {1,2,3,4},那么n = |OR| = 4,切规定r=3,那么P(4,3)就是:

{1,2,3}; {1,2,4}; {1,3,2}; {1,3,4};{1,4,2};{1,4,3};{2,1,3};{2,1,4}; {2,3,1}; {2,3,4}; {2,4,1}; {2,4,3}; {3,1,2}; {3,1,4}; {3,2,1}; {3,2,4}; {3,4,1}; {3,4,2}; {4,1,2}; {4,1,3}; {4,2,1}; {4,2,3}; {4,3,1}; {4,3,2}

算法如下:

int n, r;

char used[MaxN];

int p[MaxN];

void permute(int pos)

{ int i;

/*如果已是第r个元素了,则可打印r个元素的排列 */

if (pos==r) {

for (i=0; i

cout << (p[i]+1);

cout << endl;

return;

}

for (i=0; i

if (!used[i]) { /*如果第i个元素未用过*/

/*使用第i个元素,作上已用标记,目的是使以后该元素不可用*/

used[i]++;

/*保存当前搜索到的第i个元素*/

p[pos] = i;

/*递归搜索*/

permute(pos+1);

/*恢复递归前的值,目的是使以后改元素可用*/

used[i]--;

}

}

相关问题

UVA 524 Prime Ring Problem

可重排列:就是从任意n个元素中,取r个可重复的元素的排列。例如,对于集合OR={1,1,2,2}, n = |OR| = 4, r = 2,那么排列如下:

{1,1}; {1,2}; {1,2}; {1,1}; {1,2}; {1,2}; {2,1}; {2,1}; {2,2}; {2,1}; {2,1}; {2,2}

则可重排列是:

{1,1}; {1,2}; {2,1}; {2,2}.

算法如下:

#define FREE -1

int n, r;

/*使元素有序*/

int E[MaxN] = {0,0,1,1,1};

int P[MaxN];

char used[MaxN];

void permute(int pos)

{

int i;

/*如果已选了r个元素了,则打印它们*/

if (pos==r) {

for (i=0; i<r; i++)

cout << P[i];

cout << endl;

return;

}

/*标记下我们排列中的以前的元素表明是不存在的*/

P[pos] = FREE;

for (i=0; i<n; i++)

/*如果第I个元素没有用过,并且与先前的不同*/

if (!used[i] && E[i]!=P[pos]) {

/*使用这个元素*/

used[i]++;

/*选择现在元素的位置*/

P[pos] = E[i];

/*递归搜索*/

permute(pos+1);

/*恢复递归前的值*/

used[i]--;

}

}

相关习题

UVA 10098 Generating Fast, Sorted Permutations

组合:从n个不同元素中取r个不重复的元素组成一个子集,而不考虑其元素的顺序,称为从n个中取r个的无重组合,例如OR = {1,2,3,4}, n = 4, r = 3则无重组合为:

{1,2,3}; {1,2,4}; {1,3,4}; {2,3,4}.

算法如下:

int n, r;

int C[5];

char used[5];

void combine(int pos, int h)

{

int i;

/*如果已选了r个元素了,则打印它们*/

if (pos==r) {

for (i=0; i<r; i++)

cout<< C[i];

cout<< endl;

return;

}

for (i=h; i<=n-r+pos; i++) /*对于所有未用的元素*/

if (!used[i]) {

/*把它放置在组合中*/

C[pos] = i;

/*使用该元素*/

used[i]++;

/*搜索第i+1个元素*/

combine(pos+1,i+1);

/*恢复递归前的值*/

used[i]--;

}

}

相关问题:

Ural 1034 Queens in peaceful position

可重组合:类似于可重排列。

[例] 给出空间中给定n(n<10)个点,画一条简单路径,包括所有的点,使得路径最短。

解:这是一个旅行售货员问题TSP。这是一个NP问题,其实就是一个排列选取问题。

算法如下:

int n, r;

char used[MaxN];

int p[MaxN];

double min;

void permute(int pos, double dist)

{

int i;

if (pos==n) {

if (dist < min) min = dist;

return;

}

for (i=0; i<n; i++)

if (!used[i]) {

used[i]++;

p[pos] = i;

if (dist + cost(point[p[pos-1]], point[p[pos]]) < min)

permute(pos+1, dist + cost(point[p[pos-1]], point[p[pos]]));

used[i]--;

}

}

[例]对于0和1的所有排列,从中同时选取r个元素使得0和1的数量不同。

解 这道题很简单,其实就是从0到2^r的二元表示。

算法如下:

void dfs(int pos)

{

if (pos == r)

{

for (i=0; i<r; i++) cout<<p[i];

cout<<endl;

return;

}

p[pos] = 0;

dfs(pos+1);

p[pos] = 1;

dfs(pos+1);}

相关问题:

Ural

1005 Stone pile

1060 Flip Game

1152 The False Mirrors

[例]找最大团问题。

一个图的团,就是包括了图的所有点的子图,并且是连通的。也就是说,一个子图包含了n个顶点和n*(n-1)/2条边,找最大团问题是一个NP问题。算法如下:

#define MaxN 50

int n, max;

int path[MaxN][MaxN];

int inClique[MaxN];

void dfs(int inGraph[])

{

int i, j;

int Graph[MaxN];

if ( inClique[0]+inGraph[0]<=max ) return;

if ( inClique[0]>max ) max=inClique[0];

/*对于图中的所有点*/

for (i=1; i<=inGraph[0]; i++)

{

/*把节点放置到团中*/

++inClique[0];

inClique[inClique[0]]=inGraph[i];

/*生成一个新的子图*/

Graph[0]=0;

for (j=i+1; j<=inGraph[0]; j++)

if (path[inGraph[i]][inGraph[j]] )

Graph[++Graph[0]]=inGraph[j];

dfs(Graph);

/*从团中删除节点*/

--inClique[0];}

}

int main()

{

int inGraph[MaxN];

int i, j;

cin >>n;

while (n > 0)

{

for (i=0; i

for (j=0; j

cin >>path[i][j];

max = 1;

/*初始化*/

inClique[0]= 0;

inGraph[0] = n;

for (i=0; i

dfs(inGraph);

cout<

cin >>n;

}

return 0;}

参考论文 感谢Bamboo、LeeMaRS的帮助 相关问题: acm.zju.edu.cn: 1492 maximum clique 相关网站 http://acm.uva.es/p

http://acm.timus.ru/

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有