pythonpython-3.xlistpropagation

Is there a more efficient an robust way to create a minimum proximity algorithm for a distance matrix?


I am trying to make an algorithm that propagates from point to point in a distance matrix using the smallest distance in the proximity. The code has two conditions: the minimum distance must be no less than 0 and each point must be visited once and return to the starting position.

This is my code in its entirety:

def totalDistance(aList):
    path = []
    for j in range(0,len(aList)):                  
        k=j
        order = []
        for l in range(0,len(aList)):
                order.append(k)
                initval= min(x for x in aList[k] if x > 0 )
                k = aList[k].index(initval)
                for s in range(0,len(aList)):
                    for t in range(0,len(aList[s])):
                        aList[s][k] = 0
        path.append(order)
    return path  

The code is meant to return the indexes of the points in within the closes proximity of the evaluated point.

aList = [[0,3,4,6],[3,0,7,3],[4,7,0,9],[6,3,9,0]] and represents the distance matrix.

When running the code, I get the following error:

initval= min(x for x in aList[k] if x > 0 )

ValueError: min() arg is an empty sequence

I presume that when I make the columns in my distance matrix zero with the following function:

            for s in range(0,len(aList)):
                for t in range(0,len(aList[s])):
                    aList[s][k] = 0

the min() function is unable to find a value with the given conditions. Is there a better way to format my code such that this does not occur or a better approach to this problem all together?


Solution

  • One technique and a pointer on the rest that you say is working...

    For preventing re-visiting / backtracking. One of the common design patterns for this is to keep a separate data structure to "mark" the places you've been. Because your points are numerically indexed, you could use a list of booleans, but I think it is much easier to just keep a set of the places you've been. Something like this...

    visited = set()  # places already seen
    
    # If I decide to visit point/index "3"...
    visited.add(3)
    

    Not really a great practice to modify your input data as you are doing, and especially so if you are looping over it, which you are...leads to headaches.

    So then... Your current error is occurring because when you screen the rows for x>0 you eventually get an empty list because you are changing values and then min() chokes. So part of above can fix that, and you don't need to zero-ize, just mark them.

    Then, the obvious question...how to use the marks? You can just use it as a part of your search. And it can work well with the enumerate command which can return index values and the value by enumeration.

    Try something like this, which will make a list of "eligible" tuples with the distance and index location.

        pts_to_consider = [(dist, idx) for idx, dist in enumerate(aList[k])
                            if dist > 0
                            and idx not in visited]
    

    There are other ways to do this with numpy and other things, but this is a reasonable approach and close to what you have in code now. Comment back if stuck. I don't want to give away the whole farm because this is probably H/W. Perhaps you can use some of the hints here.