关于#送外卖#的问题，如何解决？

Question

一个送外卖的男孩有一系列的订单要送。这些订单的目的地用
坐标{𝑝1, 𝑝2, … , 𝑝𝑛}来表示，p𝑖 = (𝑥𝑖, 𝑦𝑖)。假设 x 坐标是严格递增的，即
𝑥1 < 𝑥2 < ⋯ 𝑥𝑛。外卖店的位置在𝑝1，并且送外卖的路线满足两个约束条
件：首先按照 x 坐标递增的顺序送外卖，然后按照 x 递减的顺序送外卖
并且最终回到外卖店。假设已有函数 dist(i,j)用来计算p𝑖和pj之间的距离，请给出计算最短外卖路线的算法。

Answer 1

假设订单目的地坐标按照x坐标递增的顺序组成列表（或数组）[p1, p2, p3, ...,pn-1, pn]，那计算路线距离就相当于从列表中挑出p1到pn的不同点，加上列表中剩下的点之间的距离之和。
举个例子，例子中输出的结果，相当于从上面的列表中挑出了p1, p2, p6, p7, p8, p10，则送买卖的距离之和为dist(p1,p2)+dist(p2,p6)+dist(p6,p7)+dist(p7+p8)+dist(p8,p10)，用distA表示。而剩下的点加上外卖店和最远点，为p1, p3, p4, p5, p9, p10，代表返回外卖店的距离是dist(p1,p3)+dist(p3,p4)+dist(p4,p5)+dist(p5+p9)+dist(p9,p10)，用distB表示。
所以，题目可以转化成，从列表中挑出哪些点，得到的distA+distB最短。所有的可能性是2的n-2次方，逐个比较即可。
下面是以python为例，找出所有可能路线的递归解法：

def findpath(loc,path):
    if len(loc)==0: return [path]
    all_path = []
    for i in range(len(loc)):
        all_path += findpath(loc[i+1:],path+[loc[i]])
    return all_path

p = [1,2,3,4,5,6,7,8,9,10]
all_path=findpath(p[1:],[1])