0
$\begingroup$

I coded a solution for the famous Travelling Salesman Problem but my code does not work properly, although it seems okay.

In a grid of size m x n, you are allowed to move only down/right, and you need to go from the top-left corner to the bottom-right corner. Each sell has a reward value. How much is the maximum reward you can collect?

def travellingSalesman(m, n, rewards, memo={}):

  if m == 0 or n == 0:    return 0
  if (m, n) in memo:      return memo[(m, n)]
  if (n, m) in memo:      return memo[(n, m)]

  # Base case
  if m == 1 and n == 1:   return rewards[0][0]
  
  # maximum rewarding one of the grids m-1 x n - m x n-1 plus reward of the current cell
  memo[(m, n)] = max(travellingSalesman(m-1, n, rewards, memo), travellingSalesman(m, n-1, rewards, memo)) + rewards[m-1][n-1]

  return memo[(m, n)]

if __name__ == '__main__':
  print(travellingSalesman(m=3, n=3, rewards=[[0,4,2], 
                                              [3,2,0], 
                                              [4,1,0]]))

The function below returns 6, but it should return 8 with the path: 0-> 3 -> 4 -> 1 -> 0

Can you enlighten me about the problematic/missing part of this code? Thanks!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ We typically don't debug code here, unfortunately. $\endgroup$
    – Yuval Filmus
    Commented Mar 23, 2021 at 21:03
  • $\begingroup$ @YuvalFilmus I don't ask anyone to debug my code Sir, I just cannot find any mistake in this code snippet and thought maybe someone can see the logical mistake that I cannot see. $\endgroup$
    – bbasaran
    Commented Mar 23, 2021 at 21:20
  • $\begingroup$ @Steven sorry, my bad. "profits" was the former name of "rewards". I have just edited my question. 3rd if case stands for the base case: If you go inside 1x1 grid, the return value is the reward of that cell. $\endgroup$
    – bbasaran
    Commented Mar 23, 2021 at 21:21
  • $\begingroup$ @bbasaran. I still don't understand the logic behind the 3rd if statement. I suspect that's where the error lies. $\endgroup$
    – Steven
    Commented Mar 23, 2021 at 21:24
  • $\begingroup$ @Steven the maximum reward of 1x1 grid is the reward of that cell itself, which is rewards[0][0]. This is the last node of the recursion. $\endgroup$
    – bbasaran
    Commented Mar 23, 2021 at 21:26

1 Answer 1

Reset to default
0
$\begingroup$

In the 3rd if statement your code assumes that the optimal solution when starting from coordinates $(m, n)$ is equal to the optimal solution when starting from coordinates $(n, m)$. This is clearly false in general.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, you are right. It is a false assumption. Thanks! $\endgroup$
    – bbasaran
    Commented Mar 23, 2021 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.