# 代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析

01 总体概述

• 关于solution的定义：ISolution抽象类
• 关于bestSolution的管理： IBestSolutionManager(抽象类)、SimpleBestSolutionManager(派生类)

02 ISolution抽象类

``` 1
2class ISolution
3{
4public:
5    virtual ~ISolution(){};
6    //! A getter for the value of the objective function.
7    //! \return the value of the objective function of this solution.
8    virtual double getObjectiveValue()=0;
9    //! \return a penalized version of the objective value if the solution
10    //! is infeasible.
11    virtual double getPenalizedObjectiveValue()=0;
12    //! A getter for the feasibility of the current solution.
13    //! \return true if the solution is feasible, false otherwise.
14    virtual bool isFeasible()=0;
15    //! A comparator.
16    //! \return true if this solution is "better" than the solution it is compared to.
17    virtual bool operator<(ISolution&)=0;
18    //! Compute the "distance" between solution.
19    //! This feature can be used as part of the ALNS to favor the
20    //! diversification process. If you do not plan to use this feature
21    //! just implement a method returning 0.
22    virtual int distance(ISolution&)=0;
23    //! This method create a copy of the solution.
24    virtual ISolution* getCopy()=0;
25    //! Compute a hash key of the solution.
26    virtual long long getHash()=0;
27};```

03 bestSolution的管理

3.1 IBestSolutionManager

IBestSolutionManager其实也是一个抽象类，它也只是起到提供接口的作用。其中：

isNewBestSolution(ISolution& sol)是判断sol是不是新的最优解。

``` 1class IBestSolutionManager
2{
3public:
4    //! This method evaluate if a solution is a new best solution, and adds it to the
5    //! best solution pool in this case.
6    //! \param sol the solution to be tested.
7    //! \return true if the solution is a new best solution, false otherwise.
8    virtual bool isNewBestSolution(ISolution& sol)=0;
9
10    //! Return a pointer to a best solution.
11    virtual std::list<ISolution*>::iterator begin()=0;
12
13    //! Return a pointer to a best solution.
14    virtual std::list<ISolution*>::iterator end()=0;
15
17    //! solution, as the current solution, if needed.
18    //! \param currSol a pointer to the current solution.
19    //! \param status the status of the current iteration.
20    //! \return a pointer to the current solution.
21    virtual ISolution* reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status)=0;
22};```

3.2 SimpleBestSolutionManager

SimpleBestSolutionManager是继承于IBestSolutionManager的。

``` 1class SimpleBestSolutionManager: public IBestSolutionManager {
2public:
3    SimpleBestSolutionManager(ALNS_Parameters& param);
4
5    virtual ~SimpleBestSolutionManager();
6
7    virtual bool isNewBestSolution(ISolution& sol);
8
9    //! Return a pointer to a best solution.
10    std::list<ISolution*>::iterator begin(){return bestSols.begin();};
11
12    //! Return a pointer to a best solution.
13    std::list<ISolution*>::iterator end(){return bestSols.end();};
14
16    //! solution, as the current solution, if needed.
17    //! \param currSol a pointer to the current solution.
18    //! \param status the status of the current iteration.
19    //! \return a pointer to the current solution.
20    virtual ISolution* reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status);
21
22    //! Simple getter.
23    std::list<ISolution*>& getBestSols(){return bestSols;};
24private:
25    std::list<ISolution*> bestSols;
26
27    ALNS_Parameters* parameters;
28
29};```

isNewBestSolution(ISolution& sol)做的可不只是简单判断这么简单：

``` 1bool SimpleBestSolutionManager::isNewBestSolution(ISolution& sol)
2{
3    for(list<ISolution*>::iterator it = bestSols.begin(); it != bestSols.end(); it++)
4    {
5        ISolution& currentSol = *(*it);
6        if(currentSol<sol)
7        {
8            return false;
9        }
10        else if(sol<currentSol)
11        {
12            delete *it;
13            it = bestSols.erase(it);
14            if(it == bestSols.end())
15            {
16                break;
17            }
18        }
19        else if(currentSol.getHash() == sol.getHash())
20        {
21            return false;
22        }
23    }
24    ISolution* copy = sol.getCopy();
25    bestSols.push_back(copy);
26    return true;
27}
28
30{
33    {
35        delete currSol;
36        return bestSols.back()->getCopy();
37    }
38    else
39    {
40        return currSol;
41    }
42}```

04 小结

---The End---

0 条评论

• ### 干货|变邻域搜索(VNS)算法求解Max-Mean Dispersion Problem（附代码及详细注释）

要讨论Max-Mean Dispersion Problem,就要首先了解Maximum Diversity Problem (MDP) 。

• ### 干货|自适应大邻域搜索（ALNS）算法求解带时间窗的车辆路径规划问题（附JAVA代码）

有关ALNS概念的介绍，公众号内已经有相关内容了，这里稍提一下，有疑惑的同学可以参考往期内容：

• ### 代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析

上一篇讲解了destroy和repair方法的具体实现代码，好多读者都在喊酸爽和得劲儿……今天这篇就讲点简单的，关于solution的定义和管理的代码实现，让大...

• ### HDU 2586 How far away ？

Problem Description There are n houses in the village and some bidirectional r...

• ### CodeFores 665D Simple Subset(贪心)

D. Simple Subset time limit per test 1 second memory limit per test 256 me...

• ### BZOJ4364: [IOI2014]wall砖墙(线段树)

但实际上因为这题只需要输出最后的操作序列，那么我们只维护最大最小值的覆盖标记即可。

• ### (int),Int32.Parse,Convert.ToInt3…

(int)是一种被称为强制转换的显示转换。源变量和目标变量必须是兼容的（必须都是int类型的）。并且有丢失数据的风险。因为目标变量的类型大小小于源变量。

• ### BZOJ3083: 遥远的国度(树链剖分)

以下图片来自(https://blog.csdn.net/lcomyn/article/details/45718295)

• ### BZOJ2683: 简单题(cdq分治 树状数组)

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：