纸上谈兵: 拓扑排序强攻“科技树”

谁借莪１个温暖的怀抱￠ 2021-11-22 06:32 273阅读 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开始。下面是对应关系:

我们根据编号，绘制上述图(graph)。我同时用三种颜色，来表示不同点的入度(indegree):

![SouthEast 1][]

我们使用邻接表的数据结构(参考[纸上谈兵: 图][Link 1])，来实现图。构建代码如下:

我们可以根据上面建立的图，来获得各个节点的入度。使用一个数组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