这是prufer编码的代码：
#include <stdio.h>
#define END 0 // 结束
#define L_BRACKET 1 // 左括号
#define R_BRACKET 2 // 右括号
#define NUMBER 4 // 数
typedef struct _node
{
int value// 节点值
int childs// 子节点数
struct _node *parent// 父节点
struct _node *first_child// 第一个孩子节点
struct _node *sibling// 下一个兄弟节点
}NODE
typedef struct _token
{
int type// 标记类型(左、右括号，数)
int value// 值(仅当类型为数时有效)
}TOKEN
typedef void (*FUNC)(NODE *)
static NODE *pSmallest = 0// 指向最小的叶子节点
/* 取下一个标记
input 输入串
pToken 用于返回取得的标记
返回值 取走下一个标记后的输入串
*/
char *GetNextToken(char *input,TOKEN *pToken)
{
char *p,ch
int value
pToken->type = END
/* 跳过空白 */
p = input
while ((ch = *p) &&ch != '(' &&ch != ')' &&!isdigit(ch))
p++
switch(ch)
{
case '(': pToken->type = L_BRACKETp++break
case ')': pToken->type = R_BRACKETp++break
default:
/* 识别数 */
if (isdigit(ch))
{
value = 0
while ((ch = *p) &&isdigit(ch))
{
value = 10 * value + (ch - '0')
p++
}
pToken->type = NUMBER
pToken->value = value
}
break
}
/* 根据是否到达串尾返回不同的值*/
return (*p == '\0' ? 0 : p)
}
/* 根据输入内容构造树
input 输入串
返回值 构造的树的根节点指针
*/
NODE *BuildTree(char *input)
{
char *p
TOKEN token
NODE *pCur,*pNew,*pRoot,*pLast
p = inputpCur = pLast = pRoot = 0
do
{
p = GetNextToken(p,&token)
switch(token.type)
{
case L_BRACKET:
break
case R_BRACKET:
/* 回到上一级 */
pLast = pCur
if (0 != pCur)
pCur = pCur->parent
break
case NUMBER:
pNew = (NODE *)malloc(sizeof(NODE))
memset(pNew,0,sizeof(NODE))
pNew->value = token.value
/*设定父兄节点 */
pNew->parent = pCur
if (0 != pLast)
{
pLast->sibling = pNew
pLast = pNew
}
if (0 != pCur)
{
if (0 == pCur->childs++)
pCur->first_child = pNew
}
else pRoot = pNew
p = GetNextToken(p,&token)
if (token.type == L_BRACKET)
{
pCur = pNew/*下一个符号是 (,表示此子树有孩子节点*/
pLast = 0
}
else if (token.type == R_BRACKET)
pLast = pNew/*下一个符号是 ),表示某子树结束了*/
break
}
}while (0 != p)
return pRoot
}
/* 先序遍历树,并调用指定函数对遍历到的节点进行处理
pRoot 树的根节点指针
func 用于对访问到的节点进行处理的函数
*/
void TravelTree(NODE *pRoot,FUNC func)
{
NODE *pCur
if (0 == pRoot) return
(*func)(pRoot)
pCur = pRoot->first_child
while (pCur)
{
TravelTree(pCur,func)
pCur = pCur->sibling
}
}
/* 判断指定节点是否是叶子节点(只有一条边相连的节点) */
int IsLeafNode(NODE *pNode)
{
return (0 != pNode &&(0 == pNode->childs &&0 != pNode->parent)
|| (1 == pNode->childs &&0 == pNode->parent))
}
/* 比较叶子节点值 */
void LeafValueCompare(NODE *pNode)
{
if (IsLeafNode(pNode))
if (0 == pSmallest) pSmallest = pNode
else if (pNode->value <pSmallest->value)
pSmallest = pNode
}
/* 从树中删除指定的叶子节点
pRoot 指向树根的指针
pNode 要删除的节点指针
返回值 新的根节点指针
*/
NODE *ReleaseLeafNode(NODE *pRoot,NODE *pNode)
{
NODE *pParent,*pSibling
if (0 == pNode->childs)
{
pParent = pNode->parent
if (pParent)
{
pSibling = pParent->first_child
if (pNode == pSibling)/*要删除的是父节点的第一个孩子*/
pParent->first_child = pNode->sibling
else
{
while (pSibling &&pSibling->sibling != pNode)
pSibling = pSibling->sibling
if (pSibling)
pSibling->sibling = pNode->sibling
}
pParent->childs--
}
free(pNode)
}
else/*根节点被删除*/
{
pRoot = pNode->first_child
pRoot->parent = 0
free(pNode)
}
return pRoot
}
void ReleaseTree(NODE *pRoot)
{
NODE *pCur,*pNext
if (pRoot)
{
pCur = pRoot->first_child
while (pCur)
{
pNext = pCur->sibling
ReleaseTree(pCur)
pCur = pNext
}
free(pRoot)
}
}
int main(int argc,char *argv[])
{
NODE *pRoot
char line[250]
int n
while (!feof(stdin))
{
line[0] = '\0'
gets(line)
pRoot = BuildTree(line)
n = 0
while (pRoot &&pRoot->childs != 0)
{
pSmallest = 0
TravelTree(pRoot,LeafValueCompare)// 遍历树
if (0 == pSmallest->childs)
printf(n++ ? " %d" : "%d",pSmallest->parent->value)
else
printf(n++ ? " %d" : "%d",pSmallest->first_child->value)
pRoot = ReleaseLeafNode(pRoot,pSmallest)
}
if (0 != pRoot)
{
printf("\n")
ReleaseTree(pRoot)
}
}
return 0
}
然后是遗传算法的实现：
/**************************************************************************/
/* This is a simple genetic algorithm implementation where the */
/* evaluation function takes positive values only and the */
/* fitness of an individual is the same as the value of the */
/* objective function */
/**************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* Change any of these parameters to match your needs */
#define POPSIZE 50 /* population size */
#define MAXGENS 1000 /* max. number of generations */
#define NVARS 3 /* no. of problem variables */
#define PXOVER 0.8 /* probability of crossover */
#define PMUTATION 0.15 /* probability of mutation */
#define TRUE 1
#define FALSE 0
int generation/* current generation no. */
int cur_best/* best individual */
FILE *galog/* an output file */
struct genotype /* genotype (GT), a member of the population */
{
double gene[NVARS]/* a string of variables */
double fitness/* GT's fitness */
double upper[NVARS]/* GT's variables upper bound */
double lower[NVARS]/* GT's variables lower bound */
double rfitness/* relative fitness */
double cfitness/* cumulative fitness */
}
struct genotype population[POPSIZE+1]/* population */
struct genotype newpopulation[POPSIZE+1]/* new population*/
/* replaces the */
/* old generation */
/* Declaration of procedures used by this genetic algorithm */
void initialize(void)
double randval(double, double)
void evaluate(void)
void keep_the_best(void)
void elitist(void)
void select(void)
void crossover(void)
void Xover(int,int)
void swap(double *, double *)
void mutate(void)
void report(void)
/***************************************************************/
/* Initialization function: Initializes the values of genes */
/* within the variables bounds. It also initializes (to zero) */
/* all fitness values for each member of the population. It */
/* reads upper and lower bounds of each variable from the */
/* input file `gadata.txt'. It randomly generates values */
/* between these bounds for each gene of each genotype in the */
/* population. The format of the input file `gadata.txt' is */
/* var1_lower_bound var1_upper bound */
/* var2_lower_bound var2_upper bound ... */
/***************************************************************/
void initialize(void)
{
FILE *infile
int i, j
double lbound, ubound
if ((infile = fopen("gadata.txt","r"))==NULL)
{
fprintf(galog,"\nCannot open input file!\n")
exit(1)
}
/* initialize variables within the bounds */
for (i = 0i <NVARSi++)
{
fscanf(infile, "%lf",&lbound)
fscanf(infile, "%lf",&ubound)
for (j = 0j <POPSIZEj++)
{
population[j].fitness = 0
population[j].rfitness = 0
population[j].cfitness = 0
population[j].lower[i] = lbound
population[j].upper[i]= ubound
population[j].gene[i] = randval(population[j].lower[i],
population[j].upper[i])
}
}
fclose(infile)
}
/***********************************************************/
/* Random value generator: Generates a value within bounds */
/***********************************************************/
double randval(double low, double high)
{
double val
val = ((double)(rand()%1000)/1000.0)*(high - low) + low
return(val)
}
/*************************************************************/
/* Evaluation function: This takes a user defined function. */
/* Each time this is changed, the code has to be recompiled. */
/* The current function is: x[1]^2-x[1]*x[2]+x[3] */
/*************************************************************/
void evaluate(void)
{
int mem
int i
double x[NVARS+1]
for (mem = 0mem <POPSIZEmem++)
{
for (i = 0i <NVARSi++)
x[i+1] = population[mem].gene[i]
population[mem].fitness = (x[1]*x[1]) - (x[1]*x[2]) + x[3]
}
}
/***************************************************************/
/* Keep_the_best function: This function keeps track of the */
/* best member of the population. Note that the last entry in */
/* the array Population holds a copy of the best individual */
/***************************************************************/
void keep_the_best()
{
int mem
int i
cur_best = 0/* stores the index of the best individual */
for (mem = 0mem <POPSIZEmem++)
{
if (population[mem].fitness >population[POPSIZE].fitness)
{
cur_best = mem
population[POPSIZE].fitness = population[mem].fitness
}
}
/* once the best member in the population is found, copy the genes */
for (i = 0i <NVARSi++)
population[POPSIZE].gene[i] = population[cur_best].gene[i]
}
/****************************************************************/
/* Elitist function: The best member of the previous generation */
/* is stored as the last in the array. If the best member of */
/* the current generation is worse then the best member of the */
/* previous generation, the latter one would replace the worst */
/* member of the current population */
/****************************************************************/
void elitist()
{
int i
double best, worst/* best and worst fitness values */
int best_mem, worst_mem/* indexes of the best and worst member */
best = population[0].fitness
worst = population[0].fitness
for (i = 0i <POPSIZE - 1++i)
{
if(population[i].fitness >population[i+1].fitness)
{
if (population[i].fitness >= best)
{
best = population[i].fitness
best_mem = i
}
if (population[i+1].fitness <= worst)
{
worst = population[i+1].fitness
worst_mem = i + 1
}
}
else
{
if (population[i].fitness <= worst)
{
worst = population[i].fitness
worst_mem = i
}
if (population[i+1].fitness >= best)
{
best = population[i+1].fitness
best_mem = i + 1
}
}
}
/* if best individual from the new population is better than */
/* the best individual from the previous population, then */
/* copy the best from the new populationelse replace the */
/* worst individual from the current population with the */
/* best one from the previous generation */
if (best >= population[POPSIZE].fitness)
{
for (i = 0i <NVARSi++)
population[POPSIZE].gene[i] = population[best_mem].gene[i]
population[POPSIZE].fitness = population[best_mem].fitness
}
else
{
for (i = 0i <NVARSi++)
population[worst_mem].gene[i] = population[POPSIZE].gene[i]
population[worst_mem].fitness = population[POPSIZE].fitness
}
}
/**************************************************************/
/* Selection function: Standard proportional selection for */
/* maximization problems incorporating elitist model - makes */
/* sure that the best member survives */
/**************************************************************/
void select(void)
{
int mem, i, j, k
double sum = 0
double p
/* find total fitness of the population */
for (mem = 0mem <POPSIZEmem++)
{
sum += population[mem].fitness
}
/* calculate relative fitness */
for (mem = 0mem <POPSIZEmem++)
{
population[mem].rfitness = population[mem].fitness/sum
}
population[0].cfitness = population[0].rfitness
/* calculate cumulative fitness */
for (mem = 1mem <POPSIZEmem++)
{
population[mem].cfitness = population[mem-1].cfitness +
population[mem].rfitness
}
/* finally select survivors using cumulative fitness. */
for (i = 0i <POPSIZEi++)
{
p = rand()%1000/1000.0
if (p <population[0].cfitness)
newpopulation[i] = population[0]
else
{
for (j = 0j <POPSIZEj++)
if (p >= population[j].cfitness &&
p<population[j+1].cfitness)
newpopulation[i] = population[j+1]
}
}
/* once a new population is created, copy it back */
for (i = 0i <POPSIZEi++)
population[i] = newpopulation[i]
}
/***************************************************************/
/* Crossover selection: selects two parents that take part in */
/* the crossover. Implements a single point crossover */
/***************************************************************/
void crossover(void)
{
int i, mem, one
int first = 0/* count of the number of members chosen */
double x
for (mem = 0mem <POPSIZE++mem)
{
x = rand()%1000/1000.0
if (x <PXOVER)
{
++first
if (first % 2 == 0)
Xover(one, mem)
else
one = mem
}
}
}
/**************************************************************/
/* Crossover: performs crossover of the two selected parents. */
/**************************************************************/
void Xover(int one, int two)
{
int i
int point/* crossover point */
/* select crossover point */
if(NVARS >1)
{
if(NVARS == 2)
point = 1
else
point = (rand() % (NVARS - 1)) + 1
for (i = 0i <pointi++)
swap(&population[one].gene[i], &population[two].gene[i])
}
}
/*************************************************************/
/* Swap: A swap procedure that helps in swapping 2 variables */
/*************************************************************/
void swap(double *x, double *y)
{
double temp
temp = *x
*x = *y
*y = temp
}
/**************************************************************/
/* Mutation: Random uniform mutation. A variable selected for */
/* mutation is replaced by a random value between lower and */
/* upper bounds of this variable */
/**************************************************************/
void mutate(void)
{
int i, j
double lbound, hbound
double x
for (i = 0i <POPSIZEi++)
for (j = 0j <NVARSj++)
{
x = rand()%1000/1000.0
if (x <PMUTATION)
{
/* find the bounds on the variable to be mutated */
lbound = population[i].lower[j]
hbound = population[i].upper[j]
population[i].gene[j] = randval(lbound, hbound)
}
}
}
/***************************************************************/
/* Report function: Reports progress of the simulation. Data */
/* dumped into the output file are separated by commas */
/***************************************************************/
void report(void)
{
int i
double best_val/* best population fitness */
double avg/* avg population fitness */
double stddev/* std. deviation of population fitness */
double sum_square/* sum of square for std. calc */
double square_sum/* square of sum for std. calc */
double sum/* total population fitness */
sum = 0.0
sum_square = 0.0
for (i = 0i <POPSIZEi++)
{
sum += population[i].fitness
sum_square += population[i].fitness * population[i].fitness
}
avg = sum/(double)POPSIZE
square_sum = avg * avg * POPSIZE
stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1))
best_val = population[POPSIZE].fitness
fprintf(galog, "\n%5d, %6.3f, %6.3f, %6.3f \n\n", generation,
best_val, avg, stddev)
}
/**************************************************************/
/* Main function: Each generation involves selecting the best */
/* members, performing crossover &mutation and then */
/* evaluating the resulting population, until the terminating */
/* condition is satisfied */
/**************************************************************/
void main(void)
{
int i
if ((galog = fopen("galog.txt","w"))==NULL)
{
exit(1)
}
generation = 0
fprintf(galog, "\n generation best average standard \n")
fprintf(galog, " number value fitness deviation \n")
initialize()
evaluate()
keep_the_best()
while(generation<MAXGENS)
{
generation++
select()
crossover()
mutate()
report()
evaluate()
elitist()
}
fprintf(galog,"\n\n Simulation completed\n")
fprintf(galog,"\n Best member: \n")
for (i = 0i <NVARSi++)
{
fprintf (galog,"\n var(%d) = %3.3f",i,population[POPSIZE].gene[i])
}
fprintf(galog,"\n\n Best fitness = %3.3f",population[POPSIZE].fitness)
fclose(galog)
printf("Success\n")
}
/***************************************************************/
如何用此遗传算法解决最小生成树的问题呢，要求先随机初始化一个图，然后生成对应的最小生成树。
欢迎推荐小组话题，请先登录或注册
快速注册
你的email地址:
请填写email 用于确认你的身份, 豆瓣绝不会公开你的email。
给自己设一个密码:
请填写长度大于3的密码 你需要用它登录, 请使用英文字母、符号或数字。
给自己起一个名号:
起个名号吧 中、英文均可。
进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法。与普通的搜索方法一样，进化计算也是一种迭代算法，不同的是进化计算在最优解的搜索过程中，一般是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。而且在进化问题中，要求当原问题的优化模型建立后，还必须对原问题的解进行编码。进化计算在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可能，是一种概率型的算法。
一般来说，进化计算的求解包括以下几个步骤：给定一组初始解；评价当前这组解的性能；从当前这组解中选择一定数量的解作为迭代后的解的基础；再对其进行操作，得到迭代后的解；若这些解满足要求则停止，否则将这些迭代得到的解作为当前解重新操作。
以遗传算法为例，其工作步骤可概括为：
（1） 对工作对象——字符串用二进制的0/1或其它进制字符编码 。
（2） 根据字符串的长度L，随即产生L个字符组成初始个体。
（3） 计算适应度。适应度是衡量个体优劣的标志，通常是所研究问题的目标函数。
（4） 通过复制，将优良个体插入下一代新群体中，体现“优胜劣汰”的原则。
（5） 交换字符，产生新个体。交换点的位置是随机决定的
（6） 对某个字符进行补运算，将字符1变为0，或将0变为1，这是产生新个体的另一种方法，突变字符的位置也是随机决定的。
（7） 遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算、复制、交换、突变等操作，直至满足终止条件。
将其用形式化语言表达，则为：假设α∈I记为个体，I记为个体空间。适应度函数记为Φ：I→R。在第t代，群体P(t)={a1(t),a2(t)，…，an(t)}经过复制r(reproduction)、交换c(crossover)及突变m(mutation)转换成下一代群体。这里r、c、m均指宏算子，把旧群体变换为新群体。L：I→{True, Flase}记为终止准则。利用上述符号，遗传算法可描述为：
t=0
initialize P(0):={ a1(0),a2(0)，…，an(0)}
while(l(P(t))≠True) do
evaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))}
reproduction: P′(t):=r(P(t))
crossover: P″(t):=c(P′(t))
mutation: P(t+1):= m(P″(t))
t=t+1
end
