python - 增加大小/参数的递归循环(哈密尔顿路径？)Python

Question

我有一个代码，它接受 n 输入并计算它们之间的最短距离，而无需两次重新访问同一点。我认为这与哈密顿路径问题相同。

我的代码将 n 个地址作为输入并迭代所有可能的组合而不重复。现在我有“蛮力”方法，每个循环获取开始/结束位置、计算距离、排除重复位置，然后将只访问每个点的路径添加到我的 Df。由于有5个位置，第5个嵌套for循环 block 将序列和距离写入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