n皇后问题和罗马尼亚问题实习报告

1、 人工智能课程实人工智能课程实习报告习报告题目：n 皇后问题和罗马尼亚问题皇后问题和罗马尼亚问题 班号： 191122 学号： 20211003553 姓名： 叶叶 超超 指导老师：赵曼赵曼 目录目录 人工智能课程实习报告人工智能课程实习报告.1目录目录.2罗马尼亚问题罗马尼亚问题.4一、问题描述一、问题描述.4二、图的数据结构二、图的数据结构.5三、实现算法三、实现算法.5.51.1数据结构：.5：.6：.62.深度优先 .72.1数据结构：.7：.7：.73.贪婪算法 .83.1数据结构：.83.2算法思想：.83.3运行结果：.84.A*算法.94.1数据结构：.94.2算法思想：.94

2、.3运行结果：.9四、比拟结论四、比拟结论.9N N 皇后问题皇后问题.11一、问题描述一、问题描述：.11二、数据结构二、数据结构.11三、实现算法三、实现算法.111、回溯法 .121.1数据结构：.121.2算法思想：.121.3运行结果:.122、遗传算法 .122.1数据结构：.132.2算法思想：.13.133、CSP 最小冲突法.133.1数据结构：.133.2算法思想：.143.3运行结果:.14四、比拟结论四、比拟结论.14总结总结.15附源代码附源代码.15罗马尼亚问题 .15N 皇后问题.26递归算法.27遗传算法.29csp 最小冲突法.35 罗马尼亚问题罗马尼亚问题一

3、、问题描述一、问题描述1罗马尼亚问题：Find Bucharest starting at Arad分别用宽度优先、深度优先、贪婪算法和 A*算法求解“罗马利亚度假问题。要求：分别用文件存储地图和启发函数表，用生成节点数比拟几种算法在问题求解时的效率，列表给出结果。（2）附罗马尼亚地图（3）3各结点启发值：二、图的数据结构二、图的数据结构(1)节点信息：typedef structchar cityname20;城市名int value;启发函数值int cost;路径花费Ver;()地图信息typedef structVer VMaxV;一维城市数组int edgeMaxVMaxV;二维边数

4、组int numofedges;Graph;3图的操作函数void Read_V(Graph &G)；/从文件读取顶点信息void Read_edge(Graph &G)；/从文件读取边的信息int GetFirstV(Graph G,int v)；/取节点 v 的第一个子节点int GetNextV(Graph G,int v1,int v2)；/取节点 v1 子节点 v2 后的第一个子节点三、实现算法三、实现算法 1.1 数据结构：数据结构： 队列BFS，贪婪，*公用typedef structint queueMaxSize;int rear;int front;int

5、count; SeqCQuene; 队列操作： void QueueInitiate(SeqCQuene *Q)； int QueueNotEmpty(SeqCQuene Q)； int QueueDelete(SeqCQuene *Q,int *d)； int QueueAppend(SeqCQuene *Q,int x)；先进先出BFS 记录父亲用于打印路径typedef structint father;int me;way; ： 从 Arad 结点出发，判断是否为目标结点，假设否， 宽度优先搜索系统地 探寻与该结点相连 的结点，算法首先搜索和 Arad 相距深度为 k的所有顶点，然后再

6、去搜索和 Arad 相距为 k+l 的其他顶点 ，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，假设否那么从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，假设是，那么返回失败。 该算法同时能生成一棵根为 Arad 且包括所有可达顶点的宽度优先树 ：2.深度优先深度优先 2.1 数据结构：数据结构： 堆栈 typedef struct int a100;记录入栈城市序号int top1;栈顶int weight;最大路径用于剪枝 Stack; ： 深度优先搜索是一种每次都要到达被搜索结构的叶结点的搜索方法 ，直到不能再深入为止，然后返回到另一个结点，继续对该结

7、点进行深搜。当有目标结点出现时，返回目标结点，搜索结束；否那么，假设待扩展结点表已空，且未找到目标结点，那么返回失败，停止搜索。同样，深度优先搜索从 Arad 结点出发，判断是否为目标结点，假设否，探寻与该结点相连的结点，算法首先搜索一条分支上的所有顶点，然后再去搜索和 Arad 的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，假设否，那么从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，假设是，那么返回失败。该算法同时能生成一棵根为 Arad 且包括所有可达顶点的深度优先树。在深度优先搜索中，我用到堆栈来存储待扩展结点表。 ： 说明：深度优先找

8、到解生成的节点数为 12，路径长度为 605，程序中增加回溯和剪枝功能，所以会继续搜索优于当前解的路径，当生成 14 个节点时找到了最优解 418，但此时不能确定该解就是最优解，因为还有路径没有遍历，当生成30 个节点时，所有路径都已尝试，确定最优解为 418。3.贪婪算法贪婪算法 3.1 数据结构：数据结构： 队列BFS，贪婪，*公用typedef structint queueMaxSize;int rear;int front;int count; SeqCQuene;队列操作： void QueueInitiate(SeqCQuene *Q)； int QueueNotEmpty(Se

9、qCQuene Q)； int QueueDelete(SeqCQuene *Q,int *d)； int QueueOrderAppend(SeqCQuene *Q,int x,Graph G)；越小优先级越高记录父亲用于打印路径typedef structint father;int me;way; 3.2 算法思想：算法思想： 贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。贪婪算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。在解决罗马尼亚度假问

10、题时，贪婪算法通过比拟每个待扩展结点的 h 值，即启发函数生成的到目标结点的启发函数值，选取一个最小的，来确定当前要扩展的结点，并将生成的结点放进 fringe 结点表。在贪婪算法中，我用到队列存储待扩展结点表。 3.3 运行结果：运行结果：4.A*算法算法 4.1 数据结构：数据结构： 队列BFS，贪婪，*公用typedef struct int queueMaxSize;int rear;int front;int count; SeqCQuene; 队列操作： void QueueInitiate(SeqCQuene *Q)； int QueueNotEmpty(SeqCQuene Q)

11、； int QueueDelete(SeqCQuene *Q,int *d)； intQueue_A_OrderAppend(SeqCQuene *Q,int x,Graph G)越小优先级越高 4.2 算法思想：算法思想： A*算法用公式表示为： f(n)=g(n)+h(n), 其中 f(n) 是从初始点经由结点 n 到目标点的估价函数；g(n) 是在状态空间中从初始节点到 n 节点的实际代价， h(n)是从 n 到目标节点最正确路径的估计代价。 A*能找到最优解的条件，关键在于估价函数 h(n)的选取；假设估价值35 时，用回溯法已不能较好的解决 n 皇后问题。2、遗传算法、遗传算法2.1

12、 数据结构：数据结构： int *arry =NULL; arry=new int *zhongqun;/种群 arryi=new int n+1;/个体2.2 算法思想：算法思想：遗传算法Genetic Algorithm是模拟物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。对于一个求函数最大值的优化问题，首先初始化，包括种群的大小，编码的方案，遗传的代数，变异的概率，等等；然后进行选择操作；接着是将选择的个体进行交叉；然后再进行选择，并将选择的个体进行变异；最后就是更新最优值了。大概分为：初始化，循环杂交、变异、选择、检测解，终止计算。遗

13、传算法优点是能很好的处理约束，能很好的跳出局部最优，最终得到全局最优解，全局搜索能力强；缺点是收敛较慢，局部搜索能力较弱，运行时间长，且容易受参数的影响。3、CSP 最小冲突法最小冲突法3.1 数据结构：数据结构： structstruct dddd intint csp;/csp;/冲突数冲突数 intint position;/position;/位置位置 ; dddd *arry;*arry; NQueen=newNQueen=new intn;/intn;/皇后矩阵皇后矩阵 arry=newarry=new ddn;/CSPddn;/CSP 矩阵矩阵3.2 算法思想：算法思想：最小冲突

14、法根本思想和爬山法相同，每次寻找使冲突值最小的状态，直至找到冲突值为 0 的情况、既满足条件的 N 皇后摆放位置。3.3 运行结果运行结果: 与爬山法一样 CSP 最小冲突法容易陷入局部最优，86%的时间会卡住；但是CSP 最小冲突法较简单，在皇后的个数较多时表达出来效率最高，处理多约束大规模问题时往往不能得到较好的解。四、比拟结论 Nt/ms816 24 32 3550 64100200回溯1111511027142469812865301 - - - -GA1140243931 - - 9103451819280 - -CSP470 16 156 500 62512972266139898

15、回溯法在皇后数目较小的，很占优势，它的速度非常的快，但随着皇后数目的增加，回溯法显得很不实用，在 n=35 时，用回溯法已不能较好的解决 n 皇后问题。遗传算法优点是能很好的处理约束，能很好的跳出局部最优，最终得到全局最优解，全局搜索能力强；缺点是收敛较慢，局部搜索能力较弱，运行时间中等，且容易受 n 值的影响。遗传算法的运行时间在 n 很小时没有回溯法快，但是随着 n 值的增加，遗产算法的优点也就显现出来，它能够解决回溯法不能解决的问题。CSP 最小冲突法是一种始终都比拟快的算法，它的运行时间与皇后是个数没有必然的联系，而且在 n 很大时，它显现出来运行时间短，效率高的优势，但它的缺点是会出

16、现山脊、高原，86%的时间会卡住。总的来说，CSP 最小冲突法较简单，也比拟快，在皇后的个数较多时表达出来效率最高，处理多约束大规模问题时往往不能得到较好的解。 总的来说，回溯在 n 值很小时，效率很高，但其求解范围很小，超过 35 根本就解不出来，遗传算法求解范围适中。在 n 值很大(100)时，前两者都不能再解决，此时，CSP 最小冲突法的效率最高，且与 n 值没有必然的联系。总结总结 通过此次课程实习不仅大大加深了我对几种经典搜索算法的理解，而且帮助我很好的复习了队列、堆栈、图、文件读写这几局部的内容，使我对几种根本的数据结构类型的运用更加熟练。在解决这些问题的过程中我不但很好的稳固了数

17、据结构的相关知识，而且提高了编程及程序调试能力，增强了自己编程的信心。 总之，在这次课程实习过程中我是实实在在学到了一些课堂上学不到的东西，同时也提高了实践能力。同时在这个过程中也暴露了自己的不少问题，在今后的学习过程成也会更加有针对性。最后还要感谢老师的悉心指导，解答我编程过程中的疑问、指出我程序中的缺乏，及提出可行的解决方法，让我的程序的功能更加完善。附源代码附源代码 罗马尼亚问题罗马尼亚问题 /*罗马尼亚问题*/*代码清单：main.cpp*/ /*Graph.h*#include#include#include#include#define MaxV 20 typedef struct

18、char cityname20;int value;int cost;Ver;typedef structVer VMaxV;int edgeMaxVMaxV;int numofedges;Graph;void Read_V(Graph &G) int i,v;char ch20;fstream infile(heuristic_value.txt,ios:in); i=0; while(infilech & infile v) G.Vi.value=v;G.Vi.cost=0;strcpy(G.Vi.cityname,ch);i+;void Read_edge(Graph &

19、amp;G)int valu,i;fstream infile(map.txt,ios:in); i=0; while(infilevalu) G.edgei/20i%20=valu;/coutG.edgei/20i%20;i+; int GetFirstV(Graph G,int v)int col;if(v=20)return -1;for(col=0;col0&G.edgevcol1000)return col;return -1;int GetNextV(Graph G,int v1,int v2)int col;if(v1=20|v2=20)return -1;for(col

20、=v2+1;col0&G.edgev1col1000)return col;return -1; /*Stack.h*#include#includeGraph.htypedef structint a100;int top1;int weight;Stack;bool StackNotFull(Stack *st)if(st-top1top10)return true;elsereturn false;void InitiateStack(Stack *st) st -top1=0;st-weight=0;void StackPop(Stack *st,Graph G) int x;

21、if( StakNotEmpty(st)st-top1-; x=st-ast-top1; if(st-top10 )st-weight=st-weight-G.edgest-ast-top1-1x;elsecout栈已空！ast-top1=x;if(st-top10 )st-weight=st-weight+G.edgest-ast-top1-1st-ast-top1;st-top1+;elsecout栈已满！endl;void PrintStack(Stack *st,Graph G)int x;x=0;while(xtop1)cout ax.cityname ;x+;/cout路径长度为：

22、weightendl;coutrear=0;Q-front=0;Q-count=0;int QueueNotEmpty(SeqCQuene Q)if(Q.count!=0)return 1;else return 0;int QueueAppend(SeqCQuene *Q,int x)if(Q-count0&Q-rear=Q-front)cout队列已满queueQ-rear=x;Q-rear =(Q-rear +1)%MaxSize;Q-count +;return 1;int QueueDelete(SeqCQuene *Q,int *d)if(Q-count =0)cout队列

23、已空queue Q-front;Q-front=(Q-front+1)%MaxSize;Q-count-;return 1;int QueueOrderAppend(SeqCQuene *Q,int x,Graph G)if(Q-count0 & Q-rear = Q-front)cout队列已满count=0 |G.Vx.value=G.VQ-queueQ-rear-1.value)/gai 队尾插入Q-queueQ-rear=x;Q-rear =(Q-rear +1)%MaxSize;Q-count +;return 1;elseif( G.Vx.valuequeueQ-front

24、.value)/队头插入Q-queueQ-front-1=x;Q-front =(Q-front-1+MaxSize)%MaxSize;Q-count +;return 1;else /排序找位置插入int position=Q-front;while(G.Vx.valueG.VQ-queueposition.value)position+;for(int i=Q-front;iqueue(i-1+MaxSize)%MaxSize=Q-queuei%MaxSize;Q-queue(i-1+MaxSize)%MaxSize=x;Q-front =(Q-front-1+MaxSize)%MaxSi

25、ze;Q-count +;/A*int Queue_A_OrderAppend(SeqCQuene *Q,int x,Graph G)if(Q-count0 & Q-rear = Q-front)cout队列已满count=0 |G.Vx.value+G.Vx.costG.VQ-queueQ-rear-1.value+G.VQ-queueQ-rear-1.cost)/队尾插入Q-queueQ-rear=x;Q-rear =(Q-rear +1)%MaxSize;Q-count +;return 1;elseif( G.Vx.value+G.Vx.costqueueQ-front.val

26、ue+G.VQ-queueQ-front.cost)/队头插入Q-queueQ-front-1=x;Q-front =(Q-front-1+MaxSize)%MaxSize;Q-count +;return 1;else /排序找位置插入int position=Q-front;while(G.Vx.value+G.Vx.cost G.VQ-queueposition%MaxSize.value+G.VQ-queueposition%MaxSize.cost)position+;for(int i=Q-front;iqueue(i-1+MaxSize)%MaxSize=Q-queuei%Max

27、Size;Q-queue(i-1+MaxSize)%MaxSize=x;Q-front =(Q-front-1+MaxSize)%MaxSize;Q-count +;/*main.cpp *#include Queue.htypedef structint father;int me;way; way *b=new way100;int i=0;int end=2;int count=0;int visitedCity20;void Visit(int v, int u)bi.father=u;bi.me=v;i=i+1;void PrintBW(Graph G,way *b,int end,

28、int start) int Bway=0;cout遍历路径为反序：;coutG.Vend.cityname ; while(1)for(int j=0;ji;j+) if(bj.me=end)coutG.Vbj.father.cityname ;Bway+=G.edgebj.mebj.father;end=bj.father; if(end=start)break; coutendl; cout路径长度为：Bwayendl生成节点数为：countweight=MaxWeight)w=-1;if(v=end&st-weight=MaxWeight)coutst-weight)MaxWe

29、ight=st-weight;cout路径长度为：weightendl生成节点数为：countendl; else w=GetFirstV(G,v); while(w!=-1)if(!visitedw)DepthFSearch(G,w,visited,st);w=GetNextV(G,v,w);visitedv=0;StackPop(st, G);void Greedy(Graph G,int v);void A(Graph *G,int v);void main()Graph G;Graph * p=&G;Read_V(G);Read_edge(G);/cout宽度优先：endl ;

30、BroadFSearch(G,0);/cout深度优先endl;int visited20=0;count=0;Stack *st;st=new Stack;InitiateStack( st);DepthFSearch( G, 0,visited,st);cout确定深度优先找到最优路径为：MaxWeightendl;cout确定深度优先找到最优解生成节点数为：countendl;/cout贪婪算法：endl ; Greedy( G,0);PrintBW( G, b,end,0); /coutA 星算法：endl ;A(p, 0);/贪婪算法void Greedy(Graph G,int v

31、) i=0;count=0; int visited20=0;int u,w;SeqCQuene queue; visitedv=1; if(v=end)return;QueueInitiate(&queue);QueueOrderAppend(&queue,v,G);count+;while(QueueNotEmpty(queue)QueueDelete(&queue,&u);if(u=end)count+;return;w=GetFirstV(G,u);while(w!=-1) if(!visitedw) Visit( w,u);if(w=end)count

32、+;return;QueueOrderAppend(&queue,w,G);count+;w=GetNextV(G,u,w);/A*算法void A(Graph *G,int v) i=0;count=0;int u,w;SeqCQuene queue;SeqCQuene *Q=&queue;if(v=end)return;QueueInitiate(&queue);Queue_A_OrderAppend(&queue,v,*G);count+;while(QueueNotEmpty(queue)QueueDelete(&queue,&u);if

33、(u=end)cout路径长度为：Vu.cost+ G-Vu.valueendl生成节点数为：countendl; /coutVu.cost+ G-Vu.valuecount+Vw.cost=G-Vu.cost+G-edgewu;Queue_A_OrderAppend(&queue,w,*G);count+;w=GetNextV(*G,u,w);N 皇后问题皇后问题/*N 皇后问题*递归算法递归算法/*递归算法#include#include#include#include#includeusing namespace std;bool Check(int rowCurrent,int

34、 *&NQueen); /判断函数voidPrint(ofstream &os,int n,int *&NQueen); /打印函数void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os); /判断函数，但凡横竖有冲突，或是斜线上有冲突，返回 FALSEbool Check(int rowCurrent,int *&NQueen) int i = 0; while(i rowCurrent) if(NQueeni=NQueenrowCurrent| (ab

35、s(NQueeni-NQueenrowCurrent) = abs(i-rowCurrent) ) return false; i+; return true;/将所有可能出现的结果输出文本文档void Print(ofstream &os,int n,int *&NQueen) osn皇后n; for (int i = 0;i n;i+) for(int j = 0 ; j n; j+) os(NQueeni=j?1:0); ossetw(2); osn; /核心函数。递归解决 N 皇后问题，触底那么进行打印void Solve(int rowCurrent,int *&am

36、p;NQueen,int n,int &count, ofstream &os)if(count=0) if(rowCurrent = n) /当前行数触底，即完成了一个矩阵，将它输出Print(os,n,NQueen);count+;return;for(int i = 0; i n; i+)NQueenrowCurrent = i; /row 行 i 列试一试if(Check(rowCurrent,NQueen)Solve(rowCurrent+1,NQueen,n,count,os); /移向下一行 int main()clock_t start, finish;whil

37、e(1)ofstream os;int n; /问题规模os.open(result.txt,ios_base:app); if(!os.is_open() /判断文件是否存在。 cerr找不到文件！endl; int count = 0; /解的计数cout请输入问题的规模 Nn;if(n4)cerr问题规模必须大于 4endl;return 0;int *NQueen = new intn;start = clock(); Solve(0,NQueen,n,count,os);finish = clock();osn皇后求解时间为：countfinish-startn;coutn皇后求解时

38、间为：countfinish-startendl;delete NQueen;os.close(); return 0;遗传算法遗传算法/*遗传算法*#include#include#include#include#include#include#includeusing namespace std;#define MaxGeneration 10000000#define zhongqun 50int MaxTime=2000*3600;/2hclock_t timeStart,timeNow ;int *arry =NULL;int *temp;int p;int generation;v

39、oid Initial(int genes ,int *p)/ genes lenth of gene;p zhongqun zhizheng;int i,j,k,t,sign,mod=genes;int *temp=new intgenes;for( i=0;igenes;i+)tempi=i;for(i=0;izhongqun;i+,mod=genes)pigenes=0; /冲突=0;for(j=0;jgenes;j+) sign=rand()%mod;pij=tempsign;t=tempmod-1;tempmod-1=tempsign;tempsign=t;mod-;if(mod=1

40、) pi+j=temp0; /计算冲突个数for(j=0;jgenes-1;j+)for(k=j+1;kgenes;k+)if(pij=pik|abs(pij-pik)=abs(j-k)pigenes+;delete temp;int position(int *tmp,int C) int j; for(j=0;j5;j+) if(*(tmp+j)=C)break; return(j);void invert(int pos_start,int pos_end,int xCity) int j,k,t;if(pos_startpos_end) j=pos_start+1; k=pos_end

41、; for(;j=k;j+,k-) t=tempj; tempj=tempk; tempk=t; else if(xCity-1-pos_start=pos_end+1) j=pos_end;k=pos_start+1; for(;kxCity;j-,k+) t=tempj;tempj=tempk;tempk=t; k=0; for(;k=0;j-,k+) t=tempj;tempj=tempk;tempk=t; j=xCity-1;for(;k=j;k+,j-) t=tempj;tempj=tempk; tempk=t; /计算冲突个数tempxCity=0;for(j=0;jxCity-1

42、;j+)for(k=j+1;kxCity;k+)if(tempj=tempk|abs(tempj-tempk)=abs(j-k)tempxCity+;void cross(int genes)int i,j,k,ind,mod=zhongqun,temp1;int*tmp; temp=new intgenes+1;for(i=0;izhongqun;i+)for(j=0;jtempgenes)for(j=0;jgenes+1;j+)arryij=tempj;void selfcross(int genes)int i,j,k,ind,mod=zhongqun,temp1;int*tmp; te

43、mp=new intgenes+1;for(i=0;izhongqun;i+)for(j=0;jtempgenes)for(j=0;jgenes+1;j+)arryij=tempj;int mutation(int genes)int i,j,k,l,temp;for(i=0;izhongqun;i+) if(rand()/32768.0)p0)j=rand()%genes; k=rand()%genes;if(j!=k)temp=arryij;arryij=arryik;arryik=temp;arryigenes=0; /计算冲突个数for(j=0;jgenes-1;j+)for(k=j+

44、1;kgenes;k+)if(arryij=arryik|abs(arryij-arryik)=abs(j-k)arryigenes+;return 0;bool check(int genes)for(int i=0;izhongqun;i+)if(arryigenes=0)p=i;return true; return false;int Loop(int genes)generation=0;for(generation=0;generation=MaxTime)return 0; return 0;void main()int n,i;coutGA 算法endl;ofstream os

45、;/osendl;while(1)docoutn;if(n=3)cout输入错误！请重新输入endl;while(n100);timeStart=clock();os.open(result.txt,ios_base:app); if(!os.is_open() /判断文件是否存在。 cerr找不到文件！endl; osn皇后n;arry=new int *zhongqun; for(i=0;izhongqun;i+ ) arryi=new int n+1;Initial(n,arry); if(Loop(n)timeNow=clock();coutn皇后求解时间为：;couttimeNow-

46、timeStart ;coutendl;for ( i = 0;i n;i+)for(int j = 0 ; j n; j+)os(arrypi=j?1:0);ossetw(2);osn;osn皇后求解时间为：;ostimeNow-timeStart ; ;osgeneration:generation; ;ostime:timeNow-timeStart; endl;elsecoutfailed;osfailed! ;osgeneration:generation; ;ostime:timeNow-timeStart; endl;os.close(); int j,k;for(j=0;jn-

47、1;j+)for(k=j+1;kn;k+)if(arrypj=arrypk|abs(arrypj-arrypk)=abs(j-k)coutno!;delete arry;csp 最小冲突法最小冲突法/*csp 最小冲突法#include#include#include#include#include#include#includeusing namespace std;#define MaxStep 2000clock_t timeStart,timeNow ;struct ddint csp;int position;dd *arry;int *NQueen;/ 皇后位置int q=0,step=0;/初始冲突数void Initial(int genes ,int *p)/ 初始化皇后位置/计算初始冲突个数int i,j,k,t,sign,mod=genes;int *temp=new intgenes;for( i=0;igenes;i+)tempi=i;for(j=0;jgenes;j+) sign=rand()%mod;pj=tempsign;t=tempmod-1;tempmod-1=tempsign;tempsign=t