engine.search
=============

.. py:module:: engine.search

.. autoapi-nested-parse::

   双模式分发：CA 全参数搜索建议 + 指定天数求解。



Functions
---------

.. autoapisummary::

   engine.search.balance_groups
   engine.search.solve_groups
   engine.search._deduplicate
   engine.search.ca_suggest
   engine.search.cluster_and_solve


Module Contents
---------------

.. py:function:: balance_groups(groups: list, spots: dict[int, backend.typedefs.SpotDict], depot: int = 0) -> list

   强制均衡分组，确保每天的总停留时间接近。

   将景点按停留时间贪心分配到当前负荷最小的天，
   尽可能让每天的停留时间均匀分布。

   Args:
       groups: 原始分组（不含 depot），每组为景点索引列表。
       spots: 景点字典，键为索引，值为含 stay 字段的属性。
       depot: depot 索引，默认 0。

   Returns:
       均衡后的分组列表，每组含首尾 depot。


.. py:function:: solve_groups(groups: list, spots: dict[int, backend.typedefs.SpotDict], cost_mat: numpy.ndarray, solver_type: str = 'CA', travel_speed: float = 1.0, penalty_weight: float = 100.0, early_wait_weight: float = 0.1, late_return_weight: float = 50.0, use_real_time_matrix: bool = False) -> backend.typedefs.RouteResult

   对已分组的路径逐一求解。

   遍历各组，为每组创建对应类型的求解器并执行求解。
   最后汇总所有组的成本、距离、等待、迟到等指标。

   Args:
       groups: 分组列表，每组为景点索引列表。
       spots: 景点字典，键为索引，值为景点属性。
       cost_mat: 距离/成本矩阵。
       solver_type: "CA" 或 "VNS"。
       travel_speed: 行驶速度（标准数据集），默认 1.0。
       penalty_weight: 违规惩罚权重。
       early_wait_weight: 早到等待惩罚权重。
       late_return_weight: 晚归惩罚权重。
       use_real_time_matrix: 是否使用高德真实旅行时间矩阵。

   Returns:
       dict: 包含 routes（路径列表）、histories（收敛历史）、
           total_cost、total_dist、wait、late、valid（是否覆盖所有景点）。


.. py:function:: _deduplicate(results: list) -> list

   用 frozenset 对 results 按分组结构去重，保留顺序中首次出现的唯一解。

   Args:
       results: 含 groups 字段的方案列表。

   Returns:
       list: 去重后的方案列表，保留首次出现的顺序。


.. py:function:: ca_suggest(spots: dict[int, backend.typedefs.SpotDict], depot: int, cost_mat: numpy.ndarray, min_days: int | None = None, early_stop_gain_threshold: float | None = None, stop_consecutive_worse: int | None = None, travel_speed: float = 1.0, penalty_weight: float = 100.0, early_wait_weight: float = 0.1, late_return_weight: float = 50.0, use_real_time_matrix: bool = False) -> dict

   全参数搜索，输出全部可行方案建议（去重后）。

   遍历 6 种聚类方法 × min_days 向上递增，使用 CA 快速求解各组，
   按成本排序去重后返回全部方案。支持增益阈值式早退。

   Args:
       spots: 景点字典。
       depot: depot 索引。
       cost_mat: 距离/成本矩阵。
       min_days: 最小天数（默认 n_spots//8+1）。
       early_stop_gain_threshold: 增益阈值百分比（默认 1.0%），低于此视为无效改善。
       stop_consecutive_worse: 连续无效改善次数上限（默认 3）。
       travel_speed: 行驶速度。
       penalty_weight: 违规惩罚权重。
       early_wait_weight: 早到等待惩罚权重。
       late_return_weight: 晚归惩罚权重。
       use_real_time_matrix: 是否使用高德真实旅行时间矩阵。

   Returns:
       dict: type="suggestion"；顶层含 algo_time（引擎求解耗时秒数）、
       suggestions 为全部可行方案的列表（含 n_days、method、cost、routes 等）。


.. py:function:: cluster_and_solve(spots: dict[int, backend.typedefs.SpotDict], depot: int, cost_mat: numpy.ndarray, mode: str = 'fast', n_days: int | None = None, min_days: int | None = None, travel_speed: float = 1.0, penalty_weight: float = 100.0, early_wait_weight: float = 0.1, late_return_weight: float = 50.0, use_real_time_matrix: bool = False) -> dict

   双阶段路由入口。

   - 指定 n_days：遍历 6 种聚类方法，对每组调用对应求解器（CA/VNS）求最优解。
   - 未指定 n_days + mode="fast"：回退到 ca_suggest() 输出建议。
   - 未指定 n_days + mode="deep"：报错（VNS 无自动分群能力）。

   Args:
       spots: 景点字典。
       depot: depot 索引。
       cost_mat: 距离/成本矩阵。
       mode: "fast"（CA，秒级）或 "deep"（VNS，分钟级）。
       n_days: 行程天数。deep 模式必填。
       min_days: 建议模式最小搜索天数（默认由引擎自动推断）。
       travel_speed: 行驶速度。
       penalty_weight: 违规惩罚权重。
       early_wait_weight: 早到等待惩罚权重。
       late_return_weight: 晚归惩罚权重。
       use_real_time_matrix: 是否使用高德真实旅行时间矩阵。

   Returns:
       dict: type="suggestion"（未指定天数时）或 type="solution"（已指定天数时）。

   Raises:
       ValueError: mode="deep" 且未指定 n_days 时。