CodeCraft2024

• 福兮祸兮，祸兮福兮，严肃、严谨的心态才是面对关键时刻的能保证稳定输出的最佳心态。无论如何都不应该在关键时刻过于兴奋以至于失去冷静（这次比赛吃到的最大的教训）。
• 我们需要更加大胆和更富想象力的策略。
• 贪心策略不总能保证全局最优，因此需要对贪心策略做一些偏向全局最优的修正；贪心策略也不总是那么的糟糕，它容易被实现且下限有保证，同时拥有被优化的潜能。
• 复赛正式赛的地图泊位运输时间较长，没有对这一点做专门的优化。优化之后效果明显。线下图1：93380；图2：97021。

策略简介

• 买货策略（复赛）
  1. 基本就是先买8个机器人和1条船，然后在剩余时间，再买一定数量的船和机器人（这里的一定数量是超参数，需要调出来）。
  2. 如果在后续中，观察到船运货的效率大于机器人运货的效率，则再优先买机器人。
  3. 否则，则再优先买船。
• 机器人寻找货物的策略（初赛 + 复赛）
  1. 基本策略 对于每一个刚放下货物，或当前帧没有货物目标的机器人，用贪心策略选货，即通过搜索一定范围内的货物（超参数，设为extraSearchTime，意为第一次在BFS算法中找到货物后，再额外搜索的距离（与第一次搜索到的货物在BFS最短路径中的距离），计算它们的性价比（价值 / 机器人从出发运货，到把货物运到目泊位的距离），谁的性价比高，就选谁作为目标。
  2. 细节
     1. 地图上全体货物信息的维护 对货物信息的维护的要求是：
        • 能通过坐标(x, y)以O(1)的时间复杂度获得货物的价值和剩余存在时间，因此需要int goodsInMap[MAP_SIZE][MAP_SIZE]矩阵和int goodsLeftTime[MAP_SIZE][MAP_SIZE]矩阵；
        • 能以较短时间遍历地图上全体货物的信息，且能通过该信息，在每一帧维护货物的剩余存在时间，以便更新goodsInMap和goodsLeftTime。因此需要：
          

          vector<std::unordered_map<int, int>> goodsInfo; // 存储全体货物在地图中的位置和剩余时间信息，两个维度，第一个维度表示货物出现的时刻（对1000取模），第二个维度是一个```unordered_map```，键为货物的位置，值为货物的剩余存在时间
          

        因此，在每一帧，先清除掉当前时刻对应的在goodsInfo中的货物信息：

        int frameModIdx = (frameId - 1) % 1000;
        goodsInfo[frameModIdx].clear(); // 先把对应时刻的全部货物信息清空
        

        之后再根据判题器，把新的货物信息加入到goodsInfo中。进一步的维护细节见void updateGoodsInfo()。
     2. 分区策略 分区策略是让机器人选货物的时候，更加偏向于自己所在的泊位区域上的货物（这些货物到这个泊位的距离最近）。初见，完全依赖于性价比来决定运货目标就可能在每一步中的局部最优来逼近全局最优。但是，机器人在选货物的那一刻，往往会在泊位上，如果对于某一件货物，它距离某一泊位最近，那么此刻在对应泊位（本区）上的机器人，相对于该货物也最近，它来运这个货物是最高效的。而如果在当前时刻，机器人跨区选择了货物，就会多走了距离，而这个货物，也迟早会被它所在的区域的机器人运走。
     3. 动态更改选货目标策略 动态更改选货目标策略的出发点是，由于货物生成的时空和价值不确定性，有时候可能会出现无论机器人当前怎么选择，都只能选到低性价比的货物，之后在机器人在确定好并奔赴选货目标的期间，却有高性价比的货物生成的情况。这时候机器人应该放弃当前目标，转而奔赴高性价比的货物。
        $\qquad$然而，此时机器人很可能会多走一段路。如果使用动态更改选货目标策略，就需要抑制机器人动态更改目标。具体方法是，只有机器人预期要运送的货物的性价比过小，且机器人是跨区域来的，且新的货物的性价比要高出预期要运送的货物的性价比一定程度时，才会选择更改运货目标。
     4. 召唤策略 召唤策略是，如果某个泊位对应的最邻近区域上的货物总价值与在这个区域上服务的机器人数量的比值要远大于其邻近的泊位时，邻近泊位就会发出召唤，让邻区的机器人尽可能过来为自己服务。这个想法的出发点是，机器人总是来不及运完地图上所有的货物，甚至在一些高价值或高性价比的货物消失前，也不能把它们运走。因此，理想情况下，服务于某个区域的机器人数量应该尽可能与该区域的货物总量/总价值相匹配。然而，由于货物生成的时空和价值不确定性，各个区域的货物的价值分布、数量分布、性价比分布都是未知且难以被预测的。加上机器人从一个区域移动到另外一个区域需要一定的时间，因此很难将机器人与区域的货物总量/总价值完美匹配。
        $\qquad$因此，考虑到货物有1000帧的存在时间，与其通过各种手段预测各个区域内的货物价值、数量、性价比分布且使用慢半拍的机器人调度，不如绕开这一问题，而让各个原本服务于自己所在区域的机器人不轻易更改所要服务的区域（分区策略），然后让其它区域上的货物自由发育一段时间，等到这些区域的货物价值总量（也可以是性价比高于某个特定值的货物的价值总量，但实测下来只纯粹考虑货物价值总量的效果更好）是其相邻区域的某个倍数时，这些区域就会发出召唤，让邻区的机器人尽可能过来为自己服务。
     5. 依据船与机器人的运货效率的比较关系，调整extraSearchTime超参数 extraSearchTime超参数对整个策略的影响要远比想象中的大（复赛结束后才认识到这一点，十分可惜）。在初赛阶段和复赛训练赛阶段，都能观察到这个参数不是越大越好，相反，将其设置为较小的值，总效果反而比较好（如100，而地图是200 * 200的）。这样的原因很快被识别到：如果机器人选择去运一些距离较远的货物，那么它就有更高的概率，错过一些新生成的高性价比的货物，等到它把较远距离的货物运到泊位后，那些高性价比的货物的剩余存在时间可能就不多了。然而，把extraSearchTime参数调小的负面影响没有被强调（尽管对其有认识），就是机器人会倾向与选价值小的货物，然后这些货物会被船运走，导致船单趟的运货性价比不高。然而，在初赛阶段和复赛训练赛阶段，船的效率都远比机器人的效率高，因此，只要机器人的运货效率高，运到的货物总金额大，船总是几乎能把这些货物全都运走，这就掩盖了这一负面影响。然而，在复赛正式赛中，船运一趟货物要花很长的时间，这时就应该尽可能让船里装的货物都是高价值的货物，以提升船的单趟运货性价比（我们在正式赛中就是没有想到这一点）。
     6. 快要结束时船与机器人的策略 通过禁用某些低效泊位来实现。详见berth[i].isBlocked起作用的对应部分的代码。
• 船运货策略（初赛 + 复赛）
  1. 初赛策略 纯粹看性价比，让船倾向于到能运的货物数量（金额）大，且运输时间短的泊位运货。当船在某个泊位不能继续装货（泊位上的货物已经被船给装完），且货物数量没有达到船的容量，那么船会比较留在当前泊位且等新的货物被补充进来到船能满载的时间，和船到别的泊位装货且把货物装满的时间，哪个时间少，就做出哪种决策。由于在初赛中，泊位间的距离恒定，泊位到交货点的距离相对一致，这种策略还算够用。
  2. 复赛策略 在复赛中，船需要像机器人那样做路径规划，这就需要在运货策略上精细一点。如果船在连续recursionDepthInBerthSelect个泊位上装货后（这里要选择的泊位实际上是一个排列，由于泊位数量是个位数，因此完全可以遍历全部长度为recursionDepthInBerthSelect的排列），仍然装不完货物，则使用初赛的船运货策略。否则，则在可行的泊位排列中，挑选一个船运货时间最短的排列，来作为船的泊位选择。这部分实际上写成了递归的形式，使得代码更加精简和好维护。详见specialBerthSelect()。
• 机器人之间与船之间的避让策略（初赛 + 复赛） 机器人之间与船之间的避让策略几乎完全一样，只是由于船有较大面积，且移动迟缓，故对其的碰撞检测和避让要多花点精力来完成。以下仅简要介绍机器人之间的避让策略。
  1. refreshJamBuffer(robotID)$\quad$每个机器人在每一帧都实时维护一个长度为ROBOT_JAM_BUFFER_SIZE碰撞检测缓冲区，该碰撞检测缓冲区存放的是机器人当前位置和未来ROBOT_JAM_BUFFER_SIZE - 1个时刻的位置（对机器人快走完预定路径的情况会有相应的处理，但不影响碰撞检测与避免策略的一致性）。
  2. unJam()$\quad$每一帧，在机器人做出移动决策前，如果其状态是“正在避让中（AVOIDING）”，则会检测机器人是否已经走到避让点，如果是的话，则将其状态更改为AVOIDED，并重新寻路。如果机器人的状态是“避让完成（AVOIDED）”，则会检测是否能解除避让状态unJamDetect(int robotID, int avoidRobotID)。如果是的话，则将其状态更改为NO_AVOIDING，此时机器人才可以正常移动。
  3. setPriority()$\quad$计算每一个机器人的避让优先级（详见于该函数）
  4. jamDetect(int robotID1, int robotID2)$\quad$对于每一对机器人，都会检测其是否会发生碰撞（详见于该函数和赛题具体规则）。
  5. jamResolve(int robotID1, int robotID2, int jamPos)$\quad$如果某一对机器人之间检测到将会发生碰撞，则让低优先级的去避让高优先级的机器人（这个优先级除了在setPriority()中被计算，还需要考虑低优先级的机器人当前是否在避让某个机器人等因素，详见jamControl()），更具体地，让低优先级的机器人去寻找避让路径getAvoidPath(int robotID1, int robotID2)，该避让路径不能与受避让的机器人的未来路径有任何的冲突，详见于该函数。如果低优先级的机器人此时找不到合适的避让路径，则调转优先级，让原本高优先级的机器人寻找避让路径，如果还是失败，则两个机器人同时放弃目标，且同时重新找新的目标。
  6. jamControl()$\quad$unJam()，setPriority()，jamDetect(int robotID1, int robotID2)，jamResolve(int robotID1, int robotID2, int jamPos)构成了jamControl()，使得jamControl()能被模块化，且能在同一帧内被重复调用，以解决在同一帧内，前面的robot无法及时读取到后面的robot的可能已更新的堵塞检测缓冲区的信息，导致潜在的堵塞风险的问题。
• 其它
  1. 高效BFS 为了在BFS结束后回溯找到的路径，我们本来是对每一个父节点都new一个Node来保存其信息。然而这种方法的效率堪忧（勉强能在15000帧里都不超时），且容易诱发严重的内存泄露的问题。后面通过资料查询，了解到了一种高效的BFS实现方式：预先开辟一个足够长的Node数组，供所有的涉及到寻路的函数使用（dijkstra也可以用），然后将原本的new操作都更改为setNode操作，通过这样做，就不用每次寻路都多次开辟内存且删除指针。这个实现方式，配合上仅使用vector而不是queue来存储邻接顶点，要比此前的实现方式在时间上至少快3倍。
  2. 三维BFS 复赛阶段船的寻路需要一定的想象力。因为船每一步的移动可以是前进、顺时针旋转、逆时针旋转，核心点不再是一格一格地变动，而是有可能出现对角（跨多个格子）变动。然而，对于BFS，要确定的其实只是搜索空间和当前状态的下一个状态。后者实际上就是当前位置 + 前进\顺时针旋转\逆时针旋转，而前者，考虑到船在空间上，既有位置，又有方向，那么搜索空间其实就是坐标维度（2）+方向维度（1）。那么对于原本的二维BFS，在这一点的改变仅仅是将visited数组从两维扩展到三维（比如，我们的visited数组第一维度存放船的方向，第二维度和第三维度存放船的核心点坐标）。