与前述的交货点到泊位一样？股票是什麼

　　与前述的交货点到泊位一样？股票是什麼日前，2024第十届华为软件精英寻事赛-“普朗克预备”环球总决赛及颁奖仪式完善落幕。西南赛区来自重庆大学的“CQU-42IsAllYouNeed”队获取环球总决赛亚军。来自重庆大学的优良选手刘怡鹏和蒋佳宏撰文分享其赛队参赛体验，网罗参赛初志、解题思道及计划、竞赛总结与成就等。

　　软挑每年的赛题都很无意思，也很有代价，有许众同砚加入。本年，是咱们第三年加入软挑，此次咱们都大四保研了，相对压力小极少，时刻对照充分，是以生气能正在本科阶段不留缺憾，冲个不错的名次。

　　本年的标题是合于智能口岸的，涉及到对机械人和汽船的采办和限定，以最大化收益。下面咱们以赛段递次回头赛题和咱们的解题思道及计划。咱们将代码开源到了，达成细节可能参考咱们的代码，念议论的地方迎接提issue，也迎接对咱们处分计划感风趣的同伙给个star。

　　正在200×200的二维网格舆图上，有陆地(空位和繁难)、海洋和泊位。机械人(10个)捡取并运输物品，船(5艘)将泊位上的物品运至虚拟点发生代价。机械人必要琢磨捡哪个物品、送到哪个泊位以及其途径计划;船必要琢磨去哪个泊位，借使没装尽是去其他泊位照旧直接回虚拟点。

　　咱们机械人的基础逻辑是起首回到泊位(主假使轻易行使预管造出来的泊位到其他点途径获得去物品途径)，然后找物品，再找回到的泊位，以此往来。咱们琢磨以下几个局限：

　　1.物品决议(当本身身上没有物品时要琢磨去捡哪个物品)

　　3.途径计划(去物品和泊位的途径或要践诺的操作序列是什么)

　　物品决议。之前咱们是正在机械人抵达泊位时再实行查找，但觉察如许生存一个题目：因为机械人抵达泊位时刻有区别，机械人会去一个隔绝现时泊位很远的物品，而这个物品实质可能被分派给另一个隔绝他很近的机械人。是以，咱们琢磨正在机械人选定泊位开首返回的道上就从来对每个泊位动态分派物品，机械人抵达泊位放下物品后立时选定仍然分派的物品前去即可。这里泊位与物品的二分图般配咱们从来计算行使匈牙利算法，但算了算时刻庞大度感到过错劲，是以用了浅易的贪婪格式：咱们盘算推算每个泊位到物品的决议因子(即物品代价除以预估抵达隔绝)，然后对实在行从大到小排序，顺次选定每个泊位与物品的般配相合。防备预估抵达隔绝中不蕴涵拿到物品后的回泊位隔绝，测试觉察加上这个效率会变差。必要防备的是，咱们为每个泊位分派与前去它的机械人数目相称的物品，以避免两机械人同时抵达形成的无分派物品题目。实新颖码如下。

　　泊位决议。拿到物品去迩来的泊位即可。咱们会正在后期禁用极少泊位，使得机械人不前去它们，从而使物品凑集正在几个固定泊位，降低汽船运输服从。

　　途径计划。咱们行使BFS预管造泊位到其他点的隔绝，正在机械人寻道时由于都是以泊位动作方向或者起点，于是可能沿隔绝降低从而找到途径(以泊位为起点时，必要反向做，然后翻转途径转移操作)。

　　防撞避让。因为途径计划中没有琢磨碰撞，咱们必要正在速产生碰撞时实行避让。咱们使去泊位和从泊位开赴的机械人的途径偏好区别，例如一种优先足下运动，一种优先上下运动，以低重碰撞可以。机械人相撞有两种情状，一种是去的对象一致，一种是去的对象区别。合于前者，只需让此中一个机械人原地不动即可。合于后者，践诺随机避让。因为去物品的机械人的途径是固定的，它避让后会原道返回，可以发生时刻浪掷，咱们优先让去泊位的机械人避让。众个机械人相遇时为此中一个设定最高优先级，其他机械人都为它让道，借使无可行让道格式，则让渡优先级再次计划。

　　正在初赛中，汽船无需琢磨途径计划，是以对汽船的调理至合紧急。整体来说，咱们必要处分以下题目：

　　2.正在泊位时，要不要切换泊位？切换到哪个泊位？是否该去往虚拟点了？

　　针对第一个题目，咱们会统计泊位服从(每帧泊位发生的物品代价)，然后用运输时刻乘以服从加上现时代价来预估抵达时的泊位代价，选取预估泊位代价最大的前去即可。

　　针对第二个题目，咱们直接正在装满或结果时刻脱离泊位，前去虚拟点。

　　咱们正在行使以上计谋时，会导致结果的时刻被浪掷，泊位节余较众物品，大大低重分数。是以咱们通过已知服从手动调理，每只船可能正在两个或者一个泊位间往返运货，切换泊位的时刻点由结果时辰实行逆推。结果泊位会慢慢被禁用(机械人不再去放货)，由于船不再有时机去那。必要防备的是，除非船的容量很小，否则泊位间汽船的调理是必要的。这一局限是咱们初赛提分的枢纽局限，大幅低重了泊位节余代价。实新颖码如下。

　　1.汽船与机械人不再直接天生正在舆图上，必要选手支拨资金正在特定的位置实行采办。

　　3.引入了新的地块，例如航行速率更慢的主航道等。

　　咱们没有对机械人计谋做太众点窜，只是点窜了代码达成式样。重要点窜点正在机械人和船的采办、船的调理上。

　　咱们针对每张舆图手动确定机械人和汽船的数目，然后优先采办汽船，借使采办后又有钱可能买机械人则采办机械人。由于有许众采办点，是以咱们必要确定从哪个采办点采办，咱们对海和陆地都从采办点开赴实行了分块，然后凭据每个块中的采办比例(即块中机械人/船的数目除以预期采办数目)决议正在哪个采办点采办。没有自愿采办机造，由于咱们觉察机械人的数目对结果影响很小，不如把它动作超参数。

　　正在复赛正式赛中，新增了一种代价为5000的可能载两件货的机械人。咱们通过数值盘算推算觉察，买这个机械人不如买两个平时机械人，买这个反而会亏1000。是以，咱们直接不琢磨这种机械人。

　　针对第一个题目，咱们琢磨每个泊位预期代价与估计时刻的比值，取最大的动作方向泊位。预期代价由已有物品代价和预期来日代价构成，来日代价通过过去的时刻加权代价预估。估计时刻由前去时刻、装载时刻和交货时刻构成。

　　针对第二个题目，正在前期，咱们念尽速早的采办机械人，是以当去到的泊位装好货(泊位没货了)而且船上代价仍然够买机械人时就会返回交货点交货，以尽速获取代价。借使船装满了明确是必要回到交货点的。正在后期，借使泊位没货了则必要琢磨实行泊位间变化，与前述的交货点到泊位相似，咱们依旧通过琢磨泊位预期代价与估计时刻的比值以选取去往的泊位。

　　针对第三个题目，由于汽船只会从采办点或泊位开赴，于是咱们行使Dijkstra算法预管造扫数采办点和泊位到其他点的隔绝和途径，然后正在后续直接回溯即可。必要防备的是，因为船具有对象，抵达每个点时(重点点与该点重合)的对象可以有所区别，于是践诺Dijkstra算法时每个点都是点坐标+对象构成的。实新颖码睹下图。合于众船避让题目，咱们会对每艘船后一个时辰的位子实行预测。检测到即将碰撞时会随机选取一个对象实行避让，避让后回到素来的点陆续行驶。

　　因为之前咱们从来琢磨单船，简直没有琢磨众船的调理题目，新写的汽船调理和避让欠佳，正在复赛正式赛平分数没上30万，对照缺憾。

　　决赛相对复赛有很大的转折，许众前述的算法都市生存超时的情状。决赛重要转折点如下：

　　1.众队PK，送至交货点的物品代价由机械人方、船方均分。

　　众队PK和舆图巨细转折是使得前述算法失效的重要出处。因为舆图变大，圭臬运转时刻不再够用，算法基础上重写了。而机械人和汽船的调理也由于33队同场强抢有很大转折。

　　咱们正在操练赛中从来研习排名第一赛队的计谋，基础上由众船计谋转为宝贵物品送本身计谋。众船或全船计谋被称为“海贼王”，选手会采办巨额汽船来强抢泊位上的物品。众机械人或全机械人计谋被称为“机甲王”，选手会巨额采办机械人以强抢陆地上的物品。宝贵物品送本身计谋是机械人正在场上浪荡守候宝贵物品发生，并力求第偶尔刻抢到宝贵物品，然后运送给有本身船的泊位。

　　为了担保统计的确实性，咱们安排算法时条件不行产生任何跳帧。

　　咱们针对每张舆图手动确定机械人和汽船的数目，然后遵守比例采办。整体来说，咱们盘算推算现时船数目与预期船采办数目的比值、现时机械人数目与预期采办机械人数目的比值。正在钱数足够的情状下，借使前一个比值大于后一个比值则采办船，否则采办机械人。假使买船后又有时机买机械人也实行采办。

　　咱们测试了动态确定机械人与汽船的采办数目，但达成出来效率从来不是很好，是以放弃了这种式样。

　　由于咱们采用的是抢占宝贵物品的计谋，于是必要找到最有可以发生宝贵物品且能被咱们抢到的点。咱们通过网格匀称选点然后从点开首BFS扩散的式样将舆图划分为数百个块(patch)。合于每个块，咱们会正在每一帧盘算推算它的潜正在代价(通过块巨细、块中我方机械人数目、对方机械人数目等实行估算)，然后机械人会选取潜正在代价最高(也可能说是最疏落)的块前去。当觉察高代价物品时则尽速前去即可。正在前去疏落块的进程中，可以身边会发生高代价物品，是以咱们引入了一个信号机造：当高代价物品发生时，咱们会通告左近的机械人前去。如许避免了错过物品的题目。

　　分块之后，咱们会预管造出扫数块的连结图。当机械人选取前去疏落块时，会实行从现时点到下一块中央的途径探求。必要防备的是，咱们无须探求从现时点到方向块中央的途径，由于最优途径正在宝贵物品匮乏的决赛中并不是须要的，反而会增添时刻庞大度。况且，因为只必要前去下一块中央，而现时块和下一块是相邻的，于是获得这个途径是极端神速的。由于物品离机械人相对都是很近的，于是机械人到物品的途径也可能很速获得。

　　机械人会正在每帧检测碰撞，检测到碰撞后，会随机选取原地停息、从头计划途径、随机避让或反复原夂箢。从头计划途径会将其他机械人视为繁难，然后从现时点探求到方向点的途径。随机避让便是随机选取一个对象前去，并纷歧定能避免碰撞。

　　因为场上船过众，为尽可以抢占泊位，汽船平常装满才走。同时借使咱们的船不是迩来的非装载状况船只，则泊位上节余的物品不被琢磨。咱们照旧琢磨预期代价与估计时刻的比值，取最大的计划。预期代价蕴涵自家机械人所带来的代价。估计时刻由前去时刻、守候时刻、装载时刻和交货时刻构成。守候时刻是指泊位上已有其他船而发生的守候时刻。船只不会去靠泊区有更小ID船的泊位;己方不会展现两艘船都正在一个泊位守候的情状。

　　船只决议可分为非及时决议和及时决议。非及时决议是咱们初赛、复赛从来行使的，船仅正在开赴时辰决议，半途不会改道。而及时决议则会实行每帧的决议，船装满才走的条目也不会创立。决赛操练时咱们发实际时决议的效率并欠好，但正式赛时巡视到第一名行使了及时决议，于是咱们也正在机械人和船未采办竣事时行使及时决议以加快前期堆集速率(实践觉察全程及时决议分数依旧不高，可以达成细节有题目)。

　　因为预管造的时刻不敷以对扫数泊位跑Dijkstra、汽船可以会半途改道，于是咱们安排了一种时刻上高效的截断A*算法，大幅晋升了寻道速率。咱们先对扫数采办点和泊位做BFS(防备这里无须琢磨对象)，用它的结果动作之后实行A*的价钱函数。当船没有途径时，会做一个带步数断绝的A*，再掐掉A*获得的途径的尾巴(避免船的卡顿题目，由于结果几步会琢磨抵达点的汽船对象)，如许就获得船接下来十几步的途径了。如许顺次做下去就能将船的寻道分派正在区别的帧数，避免了跳帧。

　　船正在每帧都市检测碰撞，当碰撞产生时，会随机选取原地停息或从头计划途径。从头计划途径会将其他船视为繁难，然后移用A*算法，避免后续陆续碰撞。

　　这局限咱们做的不是很好，巡视觉察咱们应当是扫数队中答复速率较慢(操练赛答复时刻20帧足下)、精度较低(操练赛准确率92%)的步队。赛后咱们反思主假使没有筑设top_k和没有坚持连结形成的。同时，咱们正在response中解析不出谜底选项时会从头哀求，这也会导致作答时刻过长。咱们的prompt是“[题目]。谜底是：”，测试觉察效率还行。

　　操练赛后期分数随机性较强，前几计谋基础一致。正式赛“元梦之星”队另辟门道，采用协作式的计谋，反而博得了更好的劳绩。虽然舆图生存堵人收益，但没有人短时刻达成。可以因为第一的误导用意(仿效超越其计谋的时刻不足)，加上咱们算法具有必定泛用性，正在正式赛中有幸拿到了第二名。

　　咱们汲取了旧年参赛的体会，正在一开首就没有念达成论文级的最优算法，而是选取校正根基算法，一步步优化。咱们正在安排算法时筑设了超等众的参数，可能调整的东西实正在是太众，这使得咱们算法的上限相对较高(正式赛不至于会很无聊)，但泛化性上会有所短缺。

　　2.大模子确实必要众去调度参数和prompt，好的参数和prompt真的能大幅降低速率和精度。

　　3.团队成员之间的代码气魄得团结，否则彼此看不懂，很难debug。

　　4.尽量将算法封装好，反复写同样的东西之后不太好改。

　　5.与赛题组和其他步队的调换能使得本身对赛题有更好的明白。

　　结果，没念到此次能拿下总决赛亚军。感动赛题组先生们的标题安排，感动西南赛区和决赛赛事组先生们的细心构造，参赛体验极端不错!