如何实现通用本地搜索求解器？接口设计遇递归类型难题

DevOps 小满

2026-7-23

本地搜索求解器通用接口设计优化方案

问题分析

你当前的接口设计存在循环类型依赖：ISolution需要引用TSolutionChecker，而TSolutionChecker又需要引用TSolution，导致编译器无法解析类型参数。同时，现有约束无法严格保证变更与解的匹配（比如形状变更误用于调色板解），影响类型安全。

优化后的接口设计

我们可以通过调整接口间的依赖关系，打破循环约束，同时强化类型匹配的安全性。以下是修正后的代码：

核心接口定义

// 变更接口：明确绑定到特定的解类型，in关键字表示逆变（后文解释）
public interface IChange<in TSolution> where TSolution : class
{
    void Apply(TSolution solution);
}

// 解接口：用TSelf递归约束确保返回具体的解类型，关联自身对应的变更类型
public interface ISolution<TSelf, TChange>
    where TSelf : ISolution<TSelf, TChange>
    where TChange : IChange<TSelf>
{
    TChange GenerateChange();
    void ApplyChange(TChange change);
    TSelf Clone();
}

// 检查器接口：关联对应的解和变更类型，确保三者匹配
public interface ISolutionChecker<in TSolution, in TChange>
    where TSolution : ISolution<TSolution, TChange>
    where TChange : IChange<TSolution>
{
    bool IsFeasible(TSolution solution);
    long ScoreDiff(TSolution solution, TChange change);
}

// 求解器接口：通过约束确保解、变更、检查器三者类型完全匹配
public interface ISolver<TSolution, TChange, TSolutionChecker>
    where TSolution : ISolution<TSolution, TChange>
    where TChange : IChange<TSolution>
    where TSolutionChecker : ISolutionChecker<TSolution, TChange>
{
    TSolution Solve(TSolutionChecker checker, TSolution initialSolution);
}

关键设计说明

打破循环依赖：
原设计中ISolution直接依赖TSolutionChecker，现在改为ISolution仅关联自身的变更类型TChange，TSolutionChecker则同时关联解和变更类型，求解器通过泛型约束将三者绑定，彻底消除循环依赖。
强类型安全：
TChange必须实现IChange<TSelf>，确保每个解类型的变更只能应用于该解类型。例如ShapeChange（绑定ShapeSolution）无法应用到PaletteSolution，编译器会直接报错，从根源避免错误配对。
递归类型参数（TSelf）：
用TSelf约束ISolution，保证Clone()方法返回具体的解类型（如ShapeSolution）而非抽象接口，避免后续使用时的强制类型转换，提升代码易用性。
协变/逆变（in关键字）：
对于IChange<in TSolution>和ISolutionChecker<in TSolution, in TChange>，in表示逆变：允许接口接受更宽泛的类型参数。例如，如果有BaseSolution和继承它的DerivedSolution，那么IChange<BaseSolution>可以用于DerivedSolution，因为DerivedSolution是BaseSolution的子类，逆变允许输入参数类型更通用，提升接口的复用性。如果你暂时不需要这种灵活性，可以去掉in关键字，不影响核心功能。

示例实现（形状绘画场景）

// 具体解类型：形状画布
public class ShapeSolution : ISolution<ShapeSolution, ShapeChange>
{
    // 画布数据（像素、形状列表等）
    private List<Shape> _shapes = new List<Shape>();

    public ShapeChange GenerateChange()
    {
        // 生成随机形状变更（添加/修改/删除形状）
        return new ShapeChange(new Shape(Random.Shared.Next(0, 100), Random.Shared.Next(0, 100)));
    }

    public void ApplyChange(ShapeChange change)
    {
        change.Apply(this);
    }

    public ShapeSolution Clone()
    {
        // 深复制画布数据
        return new ShapeSolution { _shapes = new List<Shape>(_shapes) };
    }

    // 内部形状类
    public class Shape
    {
        public int X { get; set; }
        public int Y { get; set; }
        public Shape(int x, int y) { X = x; Y = y; }
    }
}

// 具体变更类型：添加形状
public class ShapeChange : IChange<ShapeSolution>
{
    private readonly ShapeSolution.Shape _newShape;

    public ShapeChange(ShapeSolution.Shape newShape)
    {
        _newShape = newShape;
    }

    public void Apply(ShapeSolution solution)
    {
        solution._shapes.Add(_newShape);
    }
}

// 具体检查器：评估形状画布与目标图像的相似度
public class ShapeChecker : ISolutionChecker<ShapeSolution, ShapeChange>
{
    private readonly Bitmap _targetImage; // 蒙娜丽莎目标图像

    public ShapeChecker(Bitmap targetImage)
    {
        _targetImage = targetImage;
    }

    public bool IsFeasible(ShapeSolution solution)
    {
        // 简单判断：画布尺寸与目标一致则可行
        return true;
    }

    public long ScoreDiff(ShapeSolution solution, ShapeChange change)
    {
        // 模拟计算：应用变更后与目标图像的相似度提升值
        // 实际实现中需对比像素差异
        return Random.Shared.Next(0, 100);
    }
}

// 通用本地搜索求解器实现
public class LocalSearchSolver<TSolution, TChange, TSolutionChecker> : ISolver<TSolution, TChange, TSolutionChecker>
    where TSolution : ISolution<TSolution, TChange>
    where TChange : IChange<TSolution>
    where TSolutionChecker : ISolutionChecker<TSolution, TChange>
{
    private readonly int _maxIterations;

    public LocalSearchSolver(int maxIterations)
    {
        _maxIterations = maxIterations;
    }

    public TSolution Solve(TSolutionChecker checker, TSolution initialSolution)
    {
        TSolution current = initialSolution.Clone();
        for (int i = 0; i < _maxIterations; i++)
        {
            if (!checker.IsFeasible(current))
                continue;

            TChange change = current.GenerateChange();
            long diff = checker.ScoreDiff(current, change);

            // 假设得分越高越优，接受正向变更
            if (diff > 0)
            {
                current.ApplyChange(change);
            }
        }
        return current;
    }
}

方案优势

完全通用：可无缝适配形状绘画、调色板优化、平面细分等多种场景，只需实现对应场景的ISolution、IChange和ISolutionChecker。
类型安全：编译器强制检查变更与解的匹配关系，避免运行时错误。
可扩展：通过协变逆变支持更灵活的类型复用，同时递归类型参数提升代码易用性。

内容的提问来源于stack exchange，提问作者Alex Janse

如何实现通用本地搜索求解器？接口设计遇递归类型难题

问题分析 #

优化后的接口设计 #

核心接口定义 #

关键设计说明 #

示例实现（形状绘画场景） #