大小/参数增加的递归循环（哈密顿路径？）Python

Question

我有一个代码，它接受n输入并计算它们之间的最短距离，而不必再次访问同一点两次。我认为这和哈密顿路径问题是一样的。你知道吗

我的代码将n地址作为输入，并迭代所有可能的组合而不重复。现在我有了“暴力”方法，每个循环获取开始/结束位置，计算距离，排除复制位置，然后将只访问每个点的路径添加到Df。因为有5个位置，第5个嵌套for循环块将序列和距离写入DF。你知道吗

带值的DF：

Index   Type    start_point
0       Start   (38.9028613352942, -121.339977998194)
1       A       (38.8882610961556, -121.297759)
2       B       (38.9017768701178, -121.328815149117)
3       C       (38.902337877551, -121.273244306122)
4       D       (38.8627754142291, -121.313577618114)
5       E       (38.882338375, -121.277366625)

我的代码是这样的：

from geopy.distance import vincenty
import pandas as pd
master=pd.DataFrame()
master['locations']=''
master['distance']=''
n=0

df1a=source[source.Type != source.loc[0,'Type']]
df1a=df1a.reset_index(drop=True)
for i1a in df1a.index:
    i1_master=vincenty(source.loc[0,'start_point'],df1a.loc[i1a,'start_point']).mile    s

for i2 in df1a.index:
    df2a=df1a[df1a.Type != df1a.loc[i2,'Type']]
    df2a=df2a.reset_index(drop=True)            
    for i2a in df2a.index:
        if df1a.loc[i1a,'Type']==df2a.loc[i2a,'Type']:
            break
        else:
            i2_master=i1_master+vincenty(df1a.loc[i1a,'start_point'],df2a.loc[i2a,'start_point']).miles

        for i3 in df2a.index:
            df3a=df2a[df2a.Type != df2a.loc[i3,'Type']]
            df3a=df3a.reset_index(drop=True)
            for i3a in df3a.index:
                if df1a.loc[i1a,'Type']==df3a.loc[i3a,'Type']:
                    break
                if df2a.loc[i2a,'Type']==df3a.loc[i3a,'Type']:
                    break
                else:
                    i3_master=i2_master+vincenty(df2a.loc[i2a,'start_point'],df3a.loc[i3a,'start_point']).miles

                for i4 in df3a.index:
                    df4a=df3a[df3a.Type != df3a.loc[i4,'Type']]
                    df4a=df4a.reset_index(drop=True)                            
                    for i4a in df4a.index:
                        if df1a.loc[i1a,'Type']==df4a.loc[i4a,'Type']:
                            break
                        if df2a.loc[i2a,'Type']==df4a.loc[i4a,'Type']:
                            break
                        if df3a.loc[i3a,'Type']==df4a.loc[i4a,'Type']:
                            break
                        else:
                            i4_master=i3_master+vincenty(df3a.loc[i3a,'start_point'],df4a.loc[i4a,'start_point']).miles

                            for i5 in df4a.index:
                            df5a=df4a[df4a.Type != df4a.loc[i5,'Type']]
                            df5a=df5a.reset_index(drop=True)                                    
                            for i5a in df5a.index:
                                if df1a.loc[i1a,'Type']==df5a.loc[i5a,'Type']:
                                    break
                                if df2a.loc[i2a,'Type']==df5a.loc[i5a,'Type']:
                                    break
                                if df3a.loc[i3a,'Type']==df5a.loc[i5a,'Type']:
                                    break
                                if df4a.loc[i4a,'Type']==df5a.loc[i5a,'Type']:
                                    break
                                if df4a.loc[i4a,'Type']==df5a.loc[i5a,'Type']:
                                    break
                                else:
                                    i5_master=i4_master+vincenty(df4a.loc[i4a,'start_point'],df5a.loc[i5a,'start_point']).miles

                                #This loop is special, it calculates distance back to the start.
                                    for i5 in df4a.index:
                                    df5a=df4a[df4a.Type != df4a.loc[i5,'Type']]
                                    df5a=df5a.reset_index(drop=True)                                    
                                    for i5a in df5a.index:
                                        master.loc[n,'locations']=source.loc[0,'Type']+'_'+df1a.loc[i1a,'Type']+'_'+df2a.loc[i2a,'Type']+'_'+df3a.loc[i3a,'Type']+'_'+df4a.loc[i4a,'Type']+'_'+df5a.loc[i5a,'Type']+'_'+source.loc[0,'Type']
                                        master.loc[n,'distance']=i5_master+vincenty(df5a.loc[i5a,'start_point'],df1a.loc[0,'start_point']).miles
                                        n=n+1

有没有一种方法可以使用递归代码来构建这个结构？作为一名化学工程师，我不适合当；）

例如：if语句的数量（用于检查连续重复的start_points）在每个部分中都会增加，并且在参数方面会发生变化。你知道吗

如有任何其他指示，我们将不胜感激。你知道吗

Answer 1

这是旅行推销员问题的一个特例，这也许是最著名的难处理的问题的例子，对于任何大的输入都不能在合理的时间内得到解决。对此使用递归需要O（N！）内存和时间，这只能用于少量输入（可能是10个），即使在现代系统中也是如此。你知道吗

如果您愿意为了资源而牺牲完美的解决方案，请查看下面的一些次优启发式解决方案：http://www.math.tamu.edu/~mpilant/math167/Notes/Chapter2.pdf