高效启发式算法与图像分割方法研究

### 高效启发式算法与图像分割方法研究 在解决实际问题时，我们常常会遇到各种各样的挑战，比如如何在考虑时间依赖的情况下规划最优路线，以及怎样对图像进行更精准的分割。下面将为大家详细介绍时间依赖团队定向问题的高效启发式算法，以及基于中性集和非下采样轮廓波变换的彩色纹理图像分割方法。 #### 时间依赖团队定向问题的高效启发式算法 在时间依赖团队定向问题中，插入新的兴趣点（POI）会影响后续到达其他POI的时间。具体来说，插入 $p_k$ 可能会进一步改变 $p_j$ 的到达时间（$arrive_j$），其中 $j = i + 1, \cdots, n$，这取决于每个POI访问前的等待时间以及路线上连续节点之间的时间依赖旅行时间。 设 $arrive_k^j$ 为插入 $p_k$ 后到达POI $p_j$ 的新到达时间，$j = i + 1, \cdots, n$。上述插入操作可能会使 $p_j$ 访问的最大开始时间（$maxStart_j$）提前，其中 $j = 1, \cdots, i$。设 $maxStart_k^j$ 为插入 $p_k$ 后 $p_j$ 访问的新的最晚开始时间，$j = 1, \cdots, i$。 我们还定义了“松弛”变量： - 对于 $j = i + 1, \cdots, n$，$slack_k^j = maxStart_j - arrive_k^j$。 - 对于 $j = 1, \cdots, i$，$slack_k^j = maxStart_k^j - arrive_j$。 然后，我们定义了一个量 $A_i^k$： \[A_i^k = \frac{\sum_{j = 1}^{i} slack_k^j + slack_k + \sum_{j = i + 1}^{n} slack_k^j}{n + 1}\] $A_i^k$ 值较大意味着插入 $p_k$ 后，在行程的每个路段（即访问 $p_k$ 之前和之后）仍有很多插入新POI的可能性。 对于每个POI $p_k$，我们确定其最大可能的 $A_i^k$ 值，即最佳插入位置。设所有可能插入位置上的最大 $A_i^k$ 值为 $A_k$。为了确定要插入的POI，我们计算每个POI $p_k$ 的松弛权重（$slackWeight$）： \[slackWeight_k = \frac{profit_k}{2 * A_k}\] 并插入松弛权重最高的POI。 然而，上述推导的主要问题在于，对于每个POI $p_k$ 和路线 $r$ 内的每个可能插入位置 $i$，我们都需要计算 $A_i^k$，这涉及到更新路线中所有POI的 $maxStart$ 和 $arrive$ 变量的值，是一个全局而非局部的决策视角。为了开发快速启发式算法，需要快速计算 $A_i^k$。我们可以通过假设POI的时间窗口相当长，涵盖一天的大部分时间，从而每个POI前的等待时间通常为零，来快速计算 $A_i^k$ 的良好近似值。 ##### 实验结果 - **测试实例**：在测试时间依赖的团队定向问题时，缺乏相关数据集，因此我们使用了希腊雅典大都市区的GTFS数据。该网络包括3条地铁线、3条有轨电车线和287条公交线路，共有7825个公交站点。我们使用Dibbelt等人的算法预先计算了所有POI之间的24小时多模式旅行时间，并将其存储在一个 $N × N × 1440$ 的三维数组中，其中 $N$ 是指定位置/POI的数量，1440是一天中的时间步数/分钟数。 我们使用了一个包含113个景点的POI数据集，这些景点主要位于雅典市中心和比雷埃夫斯地区。利润设置在1 - 100的范围内，访问时间从1分钟到2小时不等。POI被分为11个不相交的集群。我们使用这个数据集创建了三种不同的“拓扑结构”，并对每种拓扑结构应用了100种不同的“用户偏好”输入。每天的观光总时间预算设置为5小时（10:00 - 15:00）。 - **实验结果**：我们实现了四种算法：TDCSCRoutes、SlackCSCRoutes、AvgCSCRoutes和Average ILS（AvgILS）。 | # Routes | Profit | Time | Visits | Public Transport | | --- | --- | --- | --- | --- | | 1 | TDCSCRoutes: 100<br>SlackCSCRoutes: 99.99<br>AvgCSCRoutes: 98.38<br>AvgILS: 96.68 | TDCSCRoutes: 89.88<br>SlackCSCRoutes: 100<br>AvgCSCRoutes: 55.98<br>AvgILS: 79.64 | TDCSCRoutes: 97.57<br>SlackCSCRoutes: 100<br>AvgCSCRoutes: 96.41<br>AvgILS: 92.72 | TDCSCRoutes: 100<br>SlackCSCRoutes: 92.92<br>AvgCSCRoutes: 88.78<br>AvgILS: 85.84 | | 2 | TDCSCRoutes: 100<br>SlackCSCRoutes: 99.18<br>AvgCSCRoutes: 98.82<br>AvgILS: 97.64 | TDCSCRoutes: 87.21<br>SlackCSCRoutes: 93.75<br>AvgCSCRoutes: 51.07<br>AvgILS: 100 | TDCSCRoutes: 98.09<br>SlackCSCRoutes: 100<br>AvgCSCRoutes: 97.73<br>AvgILS: 95.14 | TDCSCRoutes: 100<br>SlackCSCRoutes: 95.42<br>AvgCSCRoutes: 88.13<br>AvgILS: 85 | | 3 | TDCSCRoutes: 100<br>SlackCSCRoutes: 98.15<br>AvgCSCRoutes: 99.05<br>AvgILS: 98.05 | T