高分求~页面置换算法OPT算法

opt算法是1966年由Belady在理论上提出的一种斗镇算法，其算法实质是：系统预测作业今后要访问的页面，置换页是将来不被访问的页面或者在最长时间后才被访问的页面，置换该页不会造成刚置换出去又立即要把它调入的现象。

这是一种理想化的置换算法，其优点是缺页中断率最低。它要求 *** 作系统能知道进程“将来”页面的使用情况，但这是不可能实现的，因为枝脊程序猛销渗的执行是不可预测的。不过通过该算法可用来模拟实验分析或理论分析其他算法的优劣性。

二分查找的核心就是在于逐渐逼近（有点或毕夹逼定理的感觉），从有序数组的两边，逐渐的向所要查找的元素盯答周围逼近，最终锁定元素。

二分衫则芹查找每一次的查找都会减少当前锁定范围的一半，因此时间复杂度为：

下一篇： 写给媳妇儿的算法（二）——2-opt算法解决商旅问题

在VRP问题中，假设有一个供求关系系统，车辆从仓库取货，配送到若干个顾客处。车辆受到载重量的约束，需要组织适当的行车路线，在顾客的需求得到满足的基础上，使代价函数最小。代价函数根据问题不同而不同，常见的有车辆总运行时间最小，车辆总运行路径最短等。

这个问题基于以下假设：

定义 为需要服务的两个顾客编号， 为配送中心的车辆编号， 为顾客和仓库的集合。

参数：

: 从顾客 到顾客 的行驶距离

：顾客 的需求量

：车辆的最大载重量

决策变量：

：当车辆 被分配从顾客 运行到顾客 时，取1；否则取0

在给定了参数和定义了决策变量之后，VRP问题可以用数学模型表示为：

给定车辆负载为400，各个节点的坐标和需求如下(节点0为配送中心)：

对于个体采用自然数编码，0代表配送中心，1--n代表顾客；不同车辆的配送路线之间用0分隔（即每辆车都从仓库出发）；对于灶碧有n个顾客，k辆车的VRP问题来说，染色体长度为n+k+1。

例如配送中心有3辆车为8个客户服务，一条可能的染色体如下：

0, 7, 0, 1, 2, 3, 5, 0, 8, 4, 6, 0

这条染色体表示的三辆车的行驶路线为:

第一辆兄让车：0-7-0

第二辆车：0-1-2-3-5-0

第三辆车：0-8-4-6-0

利用分割符0，还原各条子路径

参考了大连海事大学硕隐尘举士学位论文《基于电动汽车的带时间窗的路径优化问题研究》中的交叉 *** 作，生成新的个体，具体描述如下图：

用2-opt算法对各条子路径进行局部优化

输出计算结果：

迭代过程如下图所示：

总共使用了4辆车，各自的行驶路径如下：

---