纸上谈兵: 拓扑排序强攻“科技树” 谁借莪1个温暖的怀抱¢ 2021-11-22 06:32 226阅读 0赞 作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 《文明》是一款风靡20多年的回合制策略游戏,由Sid Meier开发。《文明》结构宏大,内容丰富,玩法多样,游戏性强,称得上是历史上最伟大的游戏。在文明中,你可以选择某个文明的,从部落开始发展,在接下来的几千年的历史中,发展科技、开荒拓野、发动战争等等。游戏在保持自由度的前提下,对各个社会文明的发展顺序有很好的仿真性,让玩家仿佛置身于历史长河,坐观文明的起落。美国的一些大学的历史系甚至于使用该游戏作为教学工具。 (作为《文明》的忠实爱好者,多少个昼夜耗费在一张张地图上啊。好吧,是为了学习历史。) ### “科技树” ### ![SouthEast][] 《文明》中的科技树 游戏有一个“科技树”系统,即你可以按照该图所示的顺序来发展科技。“科技树”是这样一个概念: 为了研发某个科技,我们必须已经掌握了该科技的所有前提科技(prerequisite)。科技树中有一些箭头,从A科技指向B科技,那么A就是B的前提科技。比如,根据上面的科技树,为了研发物理(Physics),我们必须已经掌握了化学(Chemistry)和天文学(Astronomy)。而为了研发化学(Chemistry),我们又必须掌握了火药(Gunpowder)。如果一个科技没有其它科技指向,那么就不需要任何前提科技就可以研发,比如图中的封建主义(Feudalism)。如果同一时间只能研发一项科技,那么玩家的科技研发就是一个序列,比如封建主义,工程(Engineering),发明(Invention),火药,一神教(monotheism),骑士制度(Chivalry)…… 有些序列是不合法的,比如工程,发明,火药……,在研发的“发明”时,并没有满足“封建主义”的前提条件。 一个有趣的问题是,如何找到合法的序列呢?当我们在设计计算机玩家时,很可能需要解决这样一个问题。 图(graph)中的拓扑排序算法(Topological Sort)可以给出一个合法序列。虽然在游戏中被称为“科技树”,但“科技树”并不符合数据结构中的树结构。在数据结构中,树的每个节点只能由一个父节点,整个树只有一个根节点。因此,“科技树”是一个不折不扣的图结构。此外,该树是一个有向的无环(acyclic)图。图中不存在环 (cycle, 环是一个长度大于0的路径,其两端为同一节点)。 ### 拓扑排序 ### 拓扑排序利用了一个事实,即在一个无环网络中,有一些节点是没有箭头指入的,比如科技树中的一神教、封建主义、工程。 * 选择没有箭头指入的节点中的任一个,可以作为合法序列的起点,放入序列。 * 当我们将某个节点放入序列后,去掉该节点以及从该节点指出的所有箭头。在新的图中,选择没有箭头指向的节点,作为序列中的下一个点。 * 重复上面的过程,直到所有的节点都被放入序列。 对于每个节点,我们可以使用一个量入度(indegree),用来表示有多少个箭头指入该节点。当某个节点被删除时,图发生变化,我们需要更新图中节点的入度。 为了方便,我将“科技树”中的节点编号,为了符合C语言中的传统,编号从0开始。下面是对应关系: <table style="width:663px; height:228px"> <tbody> <tr> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">0</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">1</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">2</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">3</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">4</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">5</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">6</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">7</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">8</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">9</span></td> </tr> <tr> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">一神教 </span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">神学</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">印刷术</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">民主</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">自由艺术</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">骑士制度</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">音乐理论</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">银行 </span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">经济学 </span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">封建主义</span></td> </tr> <tr> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">10</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">11</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">12</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">13</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">14</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">15</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">16</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">17</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">18</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">19</span></td> </tr> <tr> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">教育</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">天文学</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">航海术</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">物理 </span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">重力理论</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">发明</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">火药</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">化学</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">磁学</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">工程</span></td> </tr> <tr> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">20</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">21</span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> </tr> <tr> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">冶金</span></td> <td style="text-align:left"><span style="font-family:courier new,courier; font-size:14px">军事传统</span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> <td style="text-align:left"><span style="font-family:courier new,courier"> </span></td> </tr> </tbody> </table> 我们根据编号,绘制上述图(graph)。我同时用三种颜色,来表示不同点的入度(indegree): ![SouthEast 1][] 我们使用邻接表的数据结构(参考[纸上谈兵: 图][Link 1]),来实现图。构建代码如下: /* By Vamei */ #include <stdio.h> #include <stdlib.h> #define NUM_V 22 typedef struct node *position; /* node */ struct node { int element; position next; }; /* * operations (stereotype) */ void insert_edge(position, int, int); void print_graph(position graph, int nv); /* for testing purpose */ void main() { struct node graph[NUM_V]; int i; // initialize the vertices for(i=0; i<NUM_V; i++) { (graph+i)->element = i; (graph+i)->next = NULL; } // insert edges insert_edge(graph,0,1); insert_edge(graph,0,5); insert_edge(graph,1,2); insert_edge(graph,1,10); insert_edge(graph,2,3); insert_edge(graph,3,4); insert_edge(graph,7,8); insert_edge(graph,9,5); insert_edge(graph,9,15); insert_edge(graph,10,6); insert_edge(graph,10,7); insert_edge(graph,10,11); insert_edge(graph,11,12); insert_edge(graph,11,13); insert_edge(graph,13,14); insert_edge(graph,13,18); insert_edge(graph,15,16); insert_edge(graph,16,17); insert_edge(graph,17,13); insert_edge(graph,17,20); insert_edge(graph,19,15); insert_edge(graph,20,21); print_graph(graph,NUM_V); } /* print the graph */ void print_graph(position graph, int nv) { int i; position p; for(i=0; i<nv; i++) { p = (graph + i)->next; printf("From %3d: ", i); while(p != NULL) { printf("%d->%d; ", i, p->element); p = p->next; } printf("\n"); } } /* * insert an edge */ void insert_edge(position graph,int from, int to) { position np; position nodeAddr; np = graph + from; nodeAddr = (position) malloc(sizeof(struct node)); nodeAddr->element = to; nodeAddr->next = np->next; np->next = nodeAddr; } 我们可以根据上面建立的图,来获得各个节点的入度。使用一个数组indeg来储存各个节点的入度,即indeg\[i\] = indgree of ith node。下面的init\_indeg()用于初始化各节点的入度: // according to the graph, initialize the indegree at each vertice void init_indeg(position graph, int nv, int indeg[]) { int i; position p; // initialize for(i=0; i<nv; i++) { indeg[i] = 0; } // assimilate the graph for(i=0; i<nv; i++) { p = (graph + i)->next; while(p != NULL) { (indeg[p->element])++; p = p->next; } } } 正如我们之前叙述的,我们需要找到入度为0的节点,并将这些节点放入序列。find\_next()就是用于寻找下一个入度为0的节点。找到对应节点后,返回该节点,并将该节点的入度更新为-1: /* find the vertice with 0 indegree*/ int find_next(int indeg[], int nv) { int next; int i; for(i=0; i<nv; i++) { if(indeg[i] == 0) break; } indeg[i] = -1; return i; } 当我们取出一个节点放入序列时,从该节点出发,指向的节点的入度会减1,我们用update\_indeg()表示该操作: // update indeg when ver is removed void update_indeg(position graph, int nv, int indeg[], int ver) { position p; p = (graph + ver)->next; while(p != NULL) { (indeg[p->element])--; p = p->next; } } 有了上面的准备,我们可以寻找序列。使用数组seq来记录序列中的节点。下面的get\_seq()用于获得拓扑排序序列: // return the sequence void get_seq(position graph, int nv, int indeg[], int seq[]){ int i; int ver; for(i = 0; i<nv; i++) { ver = find_next(indeg, nv); seq[i] = ver; update_indeg(graph, nv, indeg, ver); } } 综合上面的叙述,我们可以使用下面代码,来实现拓扑排序: ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] /* By Vamei */ #include <stdio.h> #include <stdlib.h> #define NUM_V 22 typedef struct node *position; /* node */ struct node { int element; position next; }; /* * operations (stereotype) */ void insert_edge(position, int, int); void print_graph(position, int); void init_indeg(position, int , int *); void update_indeg(position, int, int *, int); void get_seq(position, int, int *, int *); int find_next(int *, int); /* for testing purpose */ void main() { struct node graph[NUM_V]; int indeg[NUM_V]; int seq[NUM_V]; int i; // initialize the graph for(i=0; i<NUM_V; i++) { (graph+i)->element = i; (graph+i)->next = NULL; } insert_edge(graph,0,1); insert_edge(graph,0,5); insert_edge(graph,1,2); insert_edge(graph,1,10); insert_edge(graph,2,3); insert_edge(graph,3,4); insert_edge(graph,7,8); insert_edge(graph,9,5); insert_edge(graph,9,15); insert_edge(graph,10,6); insert_edge(graph,10,7); insert_edge(graph,10,11); insert_edge(graph,11,12); insert_edge(graph,11,13); insert_edge(graph,13,14); insert_edge(graph,13,18); insert_edge(graph,15,16); insert_edge(graph,16,17); insert_edge(graph,17,13); insert_edge(graph,17,20); insert_edge(graph,19,15); insert_edge(graph,20,21); print_graph(graph,NUM_V); init_indeg(graph,NUM_V,indeg); get_seq(graph, NUM_V, indeg, seq); for (i=0; i<NUM_V; i++) { printf("%d,", seq[i]); } } void print_graph(position graph, int nv) { int i; position p; for(i=0; i<nv; i++) { p = (graph + i)->next; printf("From %3d: ", i); while(p != NULL) { printf("%d->%d; ", i, p->element); p = p->next; } printf("\n"); } } /* * insert an edge */ void insert_edge(position graph,int from, int to) { position np; position nodeAddr; np = graph + from; nodeAddr = (position) malloc(sizeof(struct node)); nodeAddr->element = to; nodeAddr->next = np->next; np->next = nodeAddr; } void init_indeg(position graph, int nv, int indeg[]) { int i; position p; // initialize for(i=0; i<nv; i++) { indeg[i] = 0; } // update for(i=0; i<nv; i++) { p = (graph + i)->next; while(p != NULL) { (indeg[p->element])++; p = p->next; } } } // update indeg when ver is removed void update_indeg(position graph, int nv, int indeg[], int ver) { position p; p = (graph + ver)->next; while(p != NULL) { (indeg[p->element])--; p = p->next; } } /* find the vertice with 0 indegree*/ int find_next(int indeg[], int nv) { int next; int i; for(i=0; i<nv; i++) { if(indeg[i] == 0) break; } indeg[i] = -1; return i; } // return the sequence void get_seq(position graph, int nv, int indeg[], int seq[]){ int i; int ver; for(i = 0; i<nv; i++) { ver = find_next(indeg, nv); seq[i] = ver; update_indeg(graph, nv, indeg, ver); } } 上面算法中有一个遍历所有节点的for循环,而循环中的find\_next()函数也会遍历所有的节点。因此,算法复杂度为\[$O(|V|^2)$\]。但实际上,有些节点已经记为-1,已经没有必要遍历。为了改善算法复杂度,我们可以使用一个队列(或者栈)来记录入度为0的元素。我们每次从队列中取出一个元素放入拓扑序列,并更新相邻元素的入度。如果该元素的相邻元素的入度变为0,那么将它们放入队列中。 ### 问题拓展 ### 通过上面的算法,我们可以获得一个合法的科技发展序列。我随后想到一个问题,如何输出所有的科技发展序列呢? 这个问题的关键在于,某个时刻,可能同时有多个节点的入度同时为0。它们中的任何一个都可以成为下一个元素。为此,我们需要记录所有的可能性。 (我想到的,是复制入度数组和序列数组,以储存不同的可能性。不知道大家有什么更好的想法呢?) ### 总结 ### 图,拓扑排序 欢迎继续阅读[“纸上谈兵: 算法与数据结构”][Link 2]系列。 [SouthEast]: /images/20211122/e22e74fdd58b461891cec8b8de8bca8c.png [SouthEast 1]: /images/20211122/0827ac818e51497ba5079ce382dafb6f.png [Link 1]: http://www.cnblogs.com/vamei/p/3113912.html [ContractedBlock.gif]: http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif [ExpandedBlockStart.gif]: /images/20211122/e826bc4e39f74d14b605c31b362ce1ae.png [Link 2]: http://www.cnblogs.com/vamei/archive/2013/03/22/2974052.html
相关 WUST 1949 家谱树(拓扑排序+dfs) 1949: 家谱树 Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld Submitted: 7 港控/mmm°/ 2022年06月12日 04:22/ 0 赞/ 104 阅读
相关 拓扑排序 在这里我们引入AOV(Activity-On-Vertex)网,图的顶点代表活动,其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。 对于一个工程,我们首先将这 野性酷女/ 2022年06月10日 13:28/ 0 赞/ 197 阅读
相关 拓扑排序 C++版本实现 /以邻接矩阵Edge[A][B]=N存放图信息:A指向B,权值为N/ /假设不相连的边的Edge==INT_MAX/ void 淡淡的烟草味﹌/ 2022年06月09日 05:58/ 0 赞/ 326 阅读
相关 拓扑排序 什么是拓扑排序? 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序 冷不防/ 2022年06月09日 05:57/ 0 赞/ 185 阅读
相关 拓扑排序 拓 扑 排 序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就 小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 211 阅读
相关 拓扑排序 拓扑排序: 拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的 反 淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 295 阅读
相关 纸上谈兵: 拓扑排序强攻“科技树” 作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 《文明》是一款风靡20多年的回合制策略游戏,由Si 谁借莪1个温暖的怀抱¢/ 2021年11月22日 06:32/ 0 赞/ 227 阅读
相关 拓扑排序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程 野性酷女/ 2021年09月19日 05:04/ 0 赞/ 403 阅读
相关 拓扑排序 作用:判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst 喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 477 阅读
还没有评论,来说两句吧...