The shortest path between multiple points using Manhattan distance

Question

This is one of the assignments I got in school. Any kind of advice will be greatly appreciated.

I have a map of streets, where each crossroads is represented with coordinates = tuple of whole numbers (x, y). The length between two coordinates is equal to Manhattan's distance between them. I am taxi driver and I have coordinates for each customer and coordinates where they want to go, starting coordinates and maximum number of customers I can have in the car. I need to find the shortest path to drive all my customers to their destination. The customer can exit the vehicle only at their end destination. The result is sequence of the customers, in which the taxist has to pick / drop them.

My current solution uses recursion to find all their paths, compare their length and return the shortest one. The problem is, that it's too slow. It needs to be done in under a sec.

Thank you for your help!

EDIT1: The function: taxi = current taxi coordinates, starti = pick up coordinates of all customers (starti[0] = pickup coordinates for customer 1), cilji = end destinations of all customers (cilji[0] = drop coordinates for customer 1), left = number of customers left to drive to their destinations, index = just to make the end result, n = max numbers of customers in the taxi, atm = the number of customers in the car at that moment

public static int abs(int n) {
    if (n < 0) {
        return -n;
    }
    return n;
}
public static int razdalja(int[] a, int[] b) {
    return abs(a[0] - b[0]) + abs(a[1] - b[1]);
}

public static int[] fun(int[] taxi, int[][] starti, int[][] cilji, int left, int m, int index, int n, int atm) {
    int[] temp1;
    int[] temp2;
    int[] tab = new int[m*2+1];
    int[] min = new int[m*2+1];
    min[m*2] = Integer.MAX_VALUE;

    if (left == 0) {
        return tab;
    }

    for (int i = 0; i < m; i++) {

        if (starti[i] != null && atm < n) { 
            temp1 = starti[i];
            starti[i] = null;

            tab = fun(temp1, starti, cilji, left, m, index+1, n, atm+1);
            tab[index] = i+1;
            tab[m*2] += razdalja(taxi, temp1);
            starti[i] = temp1;

            if (tab[m*2] < min[m*2]) {
                min = tab;
            }

        } 
        else if (cilji[i] != null && starti[i] == null) {
            temp2 = cilji[i];
            cilji[i] = null;

            tab = fun(temp2, starti, cilji, left-1, m, index+1, n, atm-1);
            tab[index] = i+1;
            tab[m*2] += razdalja(taxi, temp2);
            cilji[i] = temp2;

            if (tab[m*2] < min[m*2]) {
                min = tab;
            }

        }



    }

    return min;
}

Example of an input

6                      //max customers in car
148,128                //taxi starting coordinates
7                      //number of customers
1,45,199,178,69        //first customer startX,startY,endX,endY
2,54,87,26,83          //and so on...
3,197,147,135,93
4,12,49,61,66
5,91,8,55,73
6,88,42,15,9
7,184,144,31,34

And the correct output for the input above (my function return table of these numbers + last number in the table is the length of the path)

7,3,1,2,6,5,6,7,4,2,5,4,3,1

this means:
pick (customer) 7  (184,144)
pick 3             (197,147)
pick 1                ...
pick 2
pick 6
pick 5
drop 6
drop 7
pick 4
drop 2
drop 5
drop 4
drop 3
drop 1

EDIT2: Even more, I noticed something I could probably improve, but I'm not sure how. That for loop in the function, always iterates through all i-values, even though in a lot of cases it does nothing untill it reaches high enough "i", since starti[i] and cilji[i] both equal null for most of the i-values, once we get deep enough in recursion. For each already delivered customer there is one iteration that does nothing.

---

This is how the tree for two customers look: https://i.sstatic.net/P3irL.png The circled coordinates are where the taxi drops a customer (i forgot to circle one, it's obvious).

input:
2
5,5
2
1,3,7,5,7
2,9,2,9,7

output:
1,1,2,2

Answer 1

I've formulated a dynamic-programming based solution which runs under ~ 0.17s for your hardest test case: https://ideone.com/lKUql9

INF = 100000000000

pickup = {}
dest = {}
trace = {}
dp = {}

def calc(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve(curPos, completed, ongoing):
    if len(completed) == N and len(ongoing) == 0:
        return 0
    curState = (curPos, frozenset(completed), frozenset(ongoing))   

    if curState in dp.keys():
        return dp[curState]

    minVal = INF
    for i in pickup.keys():
        if i in completed: continue
        newOngoing = ongoing.copy()
        newCompleted = completed.copy()

        if i in ongoing:
            newOngoing.remove(i)
            newCompleted.add(i)
            val = calc(curPos, dest[i]) + solve(dest[i], newCompleted, newOngoing)
            if val < minVal:
                minVal = val
                trace[curState] = \
                    ("drop " + str(i), (dest[i], newCompleted, newOngoing))
        elif len(ongoing) < maxCustomers:
            newOngoing.add(i)
            val = calc(curPos, pickup[i]) + solve(pickup[i], newCompleted, newOngoing)
            if val < minVal:
                minVal = val
                trace[curState] = \
                    ("pickup " + str(i), (pickup[i], newCompleted, newOngoing))

    dp[curState] = minVal
    return minVal

def path(state):
    stateVar = (state[0], frozenset(state[1]), frozenset(state[2]))
    if stateVar not in trace.keys():
        return
    print (trace[stateVar][0])
    if trace[stateVar][1] != None: 
        return path(trace[stateVar][1])

maxCustomers = int(input())
rstr = input().split(",")
start = (int(rstr[0]), int(rstr[1]))
N = int(input())
for i in range(N):
    line = input().split(",")
    pickup[int(line[0])] = (int(line[1]), int(line[2]))
    dest[int(line[0])] = (int(line[3]), int(line[4]))

print("Total distance travelled: ", solve(start, set(), set()))
path((start, set(), set()))

The code in many terms is self-comprehendible but I'm willing to explain things more in detail if something isn't clear.

Edit:

We define our current state to be the current coordinates where we are (curPos), the set of trips which we have already completed (completed) and the set of trips which is still in progress i.e. we have the customers in the car (ongoing) - any trip out of these two sets haven't been started yet. I use a frozenset() because python dictionaries doesn't allow using set() as a part of the hash key for the dictionary (i.e. a Map, dp and trace in our case) and hence ordinary set() must be converted into an immutable set that is frozenset()

There are multiple over-lapping subproblems which are the main reason we use dp. You can add a print ("Dp Hit: ", curState) whenever curState exists in dp.keys(), like I've done: https://ideone.com/mKFsVH (produces runtime error due to too many output lines). As you can see memoization handles large many cases which we don't need to re-explore. To understand better consider reading about using dynamic-programming for traveling salesman problem: https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

if i in completed is ~ O(log(n)) lookup since set internally are implemented as self-balancing binary trees, and yes, the mere condition if len(completed) == N should be sufficient enough. Had just added the other half as a sanity check.