N皇后C++源代码---回溯法、遗传算法、CSP最小冲突法

N皇后C++源代码（回溯法、遗传算法、CSP最小冲突法）采用面向对象的设计思想设计

#include “Genetic.h“

Genetic::Genetic（int numOfQueens int initialGroupNum）
{
	m_adaptive.resize（initialGroupNum 0）;
	m_accumuAdaptive.resize（initialGroupNum 0）;
	m_QueenNum = numOfQueens;
	m_BestAdaptive = 0;
	m_NotSuccess = true;

	for （int i = numOfQueens - 1; i >= 1; --i）
	{
		m_BestAdaptive += i;  // 计算最佳适应度
	}

	SetPopulation（）;
}

void Genetic::SetPopulation（）
{
	m_population.clear（）;
	vector tmpState（m_QueenNum 0）;
	for （size_t i = 0; i < m_adaptive.size（）; ++i）  // 初始种群
	{
		for （size_t j = 0; j < m_QueenNum; ++j）     // 随机生成状态
		{
			tmpState[j] = rand（） % m_QueenNum;
		}
		m_population.push_back（tmpState）;

		m_adaptive[i] = CalcuAdaptive（tmpState）;    // 计算新生成种群的适应值
	}
}

// 计算适应值
double Genetic::CalcuAdaptive（vector &state）
{
	size_t conflict = 0;
	for （size_t i = 0; i < m_QueenNum; ++i）
	{
		for （size_t j = i + 1; j < m_QueenNum; ++j）
		{
			if （state[i] == state[j] || abs（state[i] - state[j]） == j - i）
				conflict++;                 // 发现互相攻击的皇后对，conflict加一
		}
	}
	if （conflict == 0）  // 找到最优解
	{
		m_NotSuccess = false;
		m_BestOne = state;
	}
	return 1.0 / conflict;
}

// 物竞天择
void Genetic::Select（）
{
	vector> NewPopulation;   // 新的种群
	m_accumuAdaptive[0] = m_adaptive[0];
	for （size_t i = 1; i < m_accumuAdaptive.size（）; ++i）    // 累积适应值
	{
		m_accumuAdaptive[i] = m_accumuAdaptive[i - 1] + m_adaptive[i];
	}
	double totalAdaptive = m_accumuAdaptive[m_accumuAdaptive.size（） - 1];
	for （size_t i = 0; i < m_population.size（）; ++i）     // 进行选择
	{
		int    magnifyTotalAdaptive = totalAdaptive * 100000;  // 先乘以十万
		size_t random = rand（）*rand（） % magnifyTotalAdaptive;  // % 运算符要求整数
		double select = （double）random / 100000;               // 再除以十万

		vector::iterator low;
		low = lower_bound（m_accumuAdaptive.begin（） m_accumuAdaptive.end（） select）;  // 二分法查找
		size_t j = low - m_accumuAdaptive.begin（）;          // 被选中的种群的下标
		NewPopulation.push_back（m_population[j]）;
	}
	// 更新种群
	m_population.clear（）;
	m_population = NewPopulation;
}

void Genetic::Crossover（）
{
	for （size_t i = 0; i < m_population.size（）; ++i ++i）
	{
		//随机产生一个杂交单点，然后以单点为界，两个染色体呼唤单点两侧的
		//优质的基因片段无法长久遗传下去，随机性过强，很容易被切断
		/*size_t hybridSpot = rand（） % m_QueenNum;
		for （size_t j = 0; j < hybridSpot; ++j）
		{
		swap（m_population[i][j] m_population[i + 1][j]）;
		}
		for （size_t j = hybridSpot; j < m_QueenNum; ++j）
		{
		swap（m_population[i][j] m_population[i + 1][j]）;
		}*/

		//以下采用中间段交换，经过实验统计。在8皇后（16个初始种群）时候，此方法比上面一种方法优化了38%
		size_t midA = m_QueenNum / 3;
		size_t midB = m_QueenNum * 2 / 3;
		for （size_t j = midA; j < midB; ++j）
		{
			swap（m_population[i][j] m_population[i + 1][j]）;
		}

		//求解大于10的规模皇后的时候，把一个状态切割成一个小片段，交换
		/*bool change = true;
		size_t incre = 4;
		for （size_t i = 0; i < m_QueenNum; i += incre）
		{
		if （change）
		{
		for （size_t j = i; j < i + incre && j < m_QueenNum; ++j）
		{
		swap（m_population[i][

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        1174  2015-11-12 08:21  Genetic.h
     文件        3639  2015-11-28 19:09  MinConflict.cpp
     文件         741  2015-11-12 08:21  MinConflict.h
     文件        1038  2015-11-12 08:26  NQueensBacktrack.cpp
     文件         448  2015-11-28 19:09  NQueensBacktrack.h
     文件        1342  2015-11-14 23:28  main.cpp
     文件        4738  2015-11-28 19:09  Genetic.cpp