遥想 2021 级问题求解(三)期末理论测试时,Bardisk 对图论志在必得,用五分钟切了某作业原题后,将目光投向第二题。在看完第二题题目的一瞬间,他此前还在挥斥方遒的手僵硬了。
「请写出中国邮递员问题的定义。」
「淦,旅行商问题听过,邮递员问题是什么鬼?」
正当 Bardisk 后悔不该从不出席理论课时,马老师的声音传来:
「大家想一想邮递员的任务是什么?」
Bardisk 恍然大悟,体会到了马老师的良苦用心:
「没错,邮递员的任务是送信啊!一定是要访问每个点至少一次!」
*以下省去不堪回忆若干*
考完考试,Bardisk 沾沾自喜,用某 IM 软件向 Barisore 吹捧了一番自己的机智。然而 Barisore 早就考过了《离散数学》,不屑地甩出了维基百科上中国邮递员问题的定义,然后揶揄道:
「得了吧,送件上门,你以为是外卖员啊!」
以下是题目正文。
「凭什么谁都可以随便定义一个问题还要别人都知道啊kora!」
抱着这样的叛逆想法,Bardisk 决定定义一个「臼邦外卖员问题」来造(恶)福(心)后人,这个问题的设定是这样的:
某外卖员需要从城市出发给一条河沿岸的 个村庄送外卖,然后再返回城市。而由于连日高温天气,外卖员在从一地前往另一地的途中都需要去河边装一次水。请你根据城市、村庄、河流的位置为外卖员规划一条最短的送外卖路径。
形式化地,村庄和城市等居民点可抽象为二维平面上的几何定点,外卖员是一个几何动点,河流则是一条几何定直线。外卖员将从城市所在点出发,依次访问 号村庄所在点,然后返回城市所在点。特别地,外卖员每次从一个点前往一个点的轨迹都必须和河流所在直线至少有一个交点。可以证明,外卖员的最短轨迹是一条折线,而我们需要你给出这条最短折线的总长度、折点个数(除居民点)、以及按访问顺序的这些折点的坐标。