#include "solver.h"
#include "algorithm"
#include <assert.h>
#include <iostream>
#include <map>
#include <queue>
#include "chainnode.h"
using namespace std;
void Solver::exhaustSolve(const StarMap &smap)
{
clear();
Split sp(smap);
vector<int>vValidNos = sp.getValidChainNos();
if(vValidNos.size() == 0)
{
score.getRewardScore(sp.allChainSize()); // 没有可点击链意味着所有链均只有一个星星。
return;
}
vector<int> vChainSize(vValidNos.size());
for(int k = 0; k < vValidNos.size(); k++)
{
vChainSize[k] = sp.getChainSize(vValidNos[k]);
}
Score tmpScore;
StarMap tmpMap;
Split tmpSp;
Solver tmpSolver;
for(int k = 0; k < vValidNos.size(); k++)
{
tmpScore.clear();
tmpScore.getEliminatScore(vChainSize[k]);
tmpMap = smap;
tmpSp = sp;
tmpSp.delChain(tmpMap,vValidNos[k]);
tmpSp.getChains(tmpMap);
tmpSolver.exhaustSolve(tmpMap);
tmpScore = tmpScore + tmpSolver.score;
if(score < tmpScore)
{
score = tmpScore;
tmpSolver.vSteps.push_back(vValidNos[k]);
vSteps = tmpSolver.vSteps;
}
}
}
void Solver::randomSolve(const StarMap &smap)
{
clear();
vector<int> vValidChainNos;
int ChainNo;
StarMap tmpMap(smap);
Split sp(tmpMap);
while(sp.validChainSize() > 0)
{
vValidChainNos = sp.getValidChainNos();
ChainNo = vValidChainNos.at(rand()%vValidChainNos.size());
score.getEliminatScore(sp.getChainSize(ChainNo));
vSteps.push_back(ChainNo);
sp.delChain(tmpMap,ChainNo);
sp.getChains(tmpMap);
}
score.getRewardScore(sp.allChainSize());
}
void Solver::monteSolve(const StarMap &smap,const int &tryNums)
{
clear();
Solver solver;
for(int k = 0; k < tryNums; k++)
{
solver.clear();
solver.randomSolve(smap);
if(score < solver.score)
{
score = solver.score;
vSteps = solver.vSteps;
}
}
}
void Solver::OptMonteSolve(const StarMap &smap,const int &tryNums)
{
clear();
Solver solver;
priority_queue<ChainNode, vector<ChainNode>, CmpNode >pqNode; // 5个元素
for(int k = 0; k < tryNums; k++)
{
solver.clear();
solver.randomSolve(smap);
if(score < solver.score)
{
score = solver.score;
vSteps = solver.vSteps;
}
pqNode.push(ChainNode(solver.vSteps.at(0),solver.score));
if(k > 4)
{
pqNode.pop();
}
}
//重点探索前五个得分较高的分支,增加了二倍搜索量
StarMap mapCopy;
for(int k = 0; k < 5; k++)
{
mapCopy = smap;
Split sp(mapCopy);
ChainNode chNode = pqNode.top();
int ChainNo = chNode.getChainNo();
sp.delChain(mapCopy,ChainNo);
for(int k = 0; k <(int)(2 * tryNums/5); k++)
{
solver.randomSolve(mapCopy);
solver.score.getEliminatScore(sp.getChainSize(ChainNo));
if(score < solver.score)
{
score = solver.score;
solver.vSteps.insert(solver.vSteps.begin(),ChainNo);
vSteps = solver.vSteps;
}
}
pqNode.pop();
}
}
void Solver::compMaxSolve(const StarMap &smap,const int &tryNums)
{
clear();
int ChainNo;
StarMap tmpMap(smap);
Split sp(tmpMap);
Solver solver;
Solver solverB;
Score tmpScore;
string strOut = "BGPRY ";
while(sp.validChainSize() > 0)
{
//solver.monteSolve(tmpMap,tryNums);
//使用优化的蒙特卡洛
solver.OptMonteSolve(tmpMap,tryNums);
if(solver.score < solverB.score)
{
ChainNo = solverB.vSteps.at(0);
solverB.vSteps.erase(solverB.vSteps.begin());
tmpScore.clear();
tmpScore.getEliminatScore(sp.getChainSize(ChainNo));
solverB.score = solverB.score - tmpScore;
}
else
{
ChainNo = solver.vSteps.at(0);
solver.vSteps.erase(solver.vSteps.begin());
tmpScore.clear();
tmpScore.getEliminatScore(sp.getChainSize(ChainNo));
solver.score = solver.score - tmpScore;
solverB = solver;
}
score.getEliminatScore(sp.getChainSize(ChainNo));
// vector<pair<int,int> > vallpos = sp.getAllPos(ChainNo);
// for(int k = 0;k < vallpos.size(); k++)
// {
// cout << vallpos[k].first << "," << vallpos[k].second << "\t";
// }
// cout << endl;
pair<int,int> pos = sp.getFirstPos(ChainNo);
cout <<"ChainNo = "<< ChainNo << "\t"
<<"("<<pos.first+1 << "," << pos.second+1 << "): "
<< strOut.at(tmpMap.getStar(pos.first,pos.second))
<<"\tEliminate: " << sp.getChainSize(ChainNo)
<<"\tgetScore: " << score.CalEliminatScore(sp.getChainSize(ChainNo))
<< "\tNowScore: " << getScore() << "\tExpect Score: "
<< solverB.getScore() + score.getValue()<< endl;
vSteps.push_back(ChainNo);
sp.delChain(tmpMap,ChainNo);
sp.getChains(tmpMap);
}
score.getRewardScore(sp.allChainSize());
cout <<"RemindStars: " << sp.allChainSize() << "\tgetScore:"
<< score.CalRewardScore(sp.allChainSize()) << "\t"
<< "End: TotalScore = " << score.getValue() << endl;
cout << "SolveSteps:" << endl;
for(int k = 0;k < vSteps.size(); k++)
{
cout << vSteps.at(k) << ",";
}
cout << endl;
}
void Solver::OptSolver(const StarMap &smap,const Solver &solve,const int &depth)
{
clear();
StarMap tmpMap(smap);
Split sp(tmpMap);
int k = 0;
int ChainNo;
while(sp.validChainSize() > depth)
{
ChainNo = solve.vSteps[k];
++k;
score.getEliminatScore(sp.getChainSize(ChainNo));
vSteps.push_back(ChainNo);
sp.delChain(tmpMap,ChainNo);
sp.getChains(tmpMap);
}
Solver tmpSolve;
tmpSolve.exhaustSolve(tmpMap);
score.addValue(tmpSolve.getScore());
reverse(tmpSolve.vSteps.begin(),tmpSolve.vSteps.end());
vSteps.insert(vSteps.end(),tmpSolve.vSteps.begin(),tmpSolve.vSteps.end());
}
void Solver::clear()
{
score = 0;
vSteps.clear();
}
int Solver::getScore()const
{
return score.getValue();
}
vector<int> Solver::getSteps()const
{
return vSteps;
}
void Solver::showSolveProcess(const StarMap &smap,const vector<int> &steps)const
{
//演示过程
Score TotalScore;
int ChainNo;
StarMap mapCopy = smap;
Split sp(mapCopy);
string strOut = "BGPRY ";
for(int k = 0; k < steps.size(); k++)
{
sp.getChains(mapCopy);
ChainNo = steps[k];
TotalScore.getEliminatScore(sp.getChainSize(ChainNo));
//显示坐标
// vector<pair<int,int> > vallpos = getAllPos(ChainNo);
// for(int k = 0;k < vallpos.size(); k++)
// {
// cout << vallpos[k].first << "," << vallpos[k].second << "\t";
// }
// cout << endl;
pair<int,int> pos = sp.getFirstPos(ChainNo);
cout <<"ChainNo = "<< ChainNo << "\t"
<<"("<<pos.first+1 << "," << pos.second+1 << "): "
<< strOut.at(mapCopy.getStar(pos.first,pos.second))
<<"\tEliminate: " << sp.getChainSize(ChainNo)
<<"\tgetScore: " << score.CalEliminatScore(sp.getChainSize(ChainNo))
<< "\tNowScore: " << getScore() << endl;
sp.delChain(mapCopy,ChainNo);
}
sp.getChains(mapCopy);
TotalScore.getRewardScore(sp.allChainSize());
cout
自动消灭星星程序
3星 · 超过75%的资源 需积分: 32 78 浏览量
2016-04-05
20:13:59
上传
评论 1
收藏 1.44MB RAR 举报
creasson
- 粉丝: 2
- 资源: 10
最新资源
- 2011-2020各省全体居民人均消费支出-元
- CPA税法 - 60分救心丸
- 1713338783935.jpg
- gd32f4xx_adc.c
- 海尔智能电视刷机数据 32H5R3D 机编DH1RA000101 务必确认机编一致 强制刷机 整机USB升级主程序.zip
- 海尔智能电视刷机数据 LE39A900P 机编DH1R6000702 务必确认机编一致 强制刷机 整机USB升级主程序.zip
- 基于Java的建木DevOps无代码/低代码工具设计源码
- groovy将JDBC中oracle存储过程游标转换为多层json
- qt TableView显示数据库表中的数据
- 基于Flask的Web程序插件开发工具包设计源码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
评论1