Computer programming refers to a technological process for instructing computers to perform specific tasks or to solve problems. We can think of programming as a form of collaboration between humans and computers, in which humans create instructions for computers to follow (code) in a language they understand.
Solving a problem starts with a problem statement. If we look at the Traveling Salesman Problem (TSP), the problem statement that we have is to find the shortest path from known cities with their distances, where each city must be visited exactly once and return back to the same point. This is an example problem we are using here. And, the goal is said to be met when we have a workable code that solves the problem.
From a problem statement to a workable solution, it’s a big leap and requires lots of work. It may be required to break down and process it. In some cases, as you become more skilled, you’ll be able to just do this in your mind and it will happen naturally.
However, the seven-step approach mentioned below is a good way to approach any problem where you cannot see the answer right away.
Steps:
- Work Example By Hand
- Write Down What You Did
- Find Patterns
- Check By Hand
- Translate To Code
- Run Test Cases
- Debug Failed Test Cases
Step 1: Work Example By Hand
The first approach that we are going to do is to take a small instance. In the TSP problem, what we are going to do is to take a small instance, that is visit a couple of cities and sum up their distance to calculate the route.
If you have trouble in this step, maybe the problem is unclear. Problem statements don’t actually tell you how to solve them. Therefore, you need to determine what to do next. Therefore, it’s always good to ask for help for clarification or consult with a domain knowledge expert.
Step 2: Write Down What You Did
After completing the first step, we are going to write down the steps that we did in step 1. That is, you are going to give directions to someone to solve that instance of the problem. The main idea behind writing this is to reflect the reasoning behind the answer that we came up with for the particular instance of the problem.
As humans, there are a lot of things that we do without consciously thinking about them and it’s kind of natural too. We have to be very precise with our steps here, if not, it’s going to make things difficult later as there might be a chance of missing crucial parts.
Step 3: Find Patterns
Step 3 is about finding patterns. As, we want to write an algorithm for any instance of a problem, not just a particular instance that we worked on. Here, we are going to think about repetition. The things that we did over and over, for various times, and on various conditions will lead us to loop and conditional constructs. These conditions or looping may be the rise of particle input and we have to think of it too.
If we have difficulties in this step, we have to revisit Step 1 and Step 2 with different inputs. By revisiting it again and again, we’ll come up with more information to look for patterns from and will have different sets of steps. This will tell us how to work with multiple instances of a problem and also helps to find patterns easily.
Step 4: Check By Hand
Once we are done with step 3, we want to check the algorithm by hand. The algorithm that we came up with might contains mistakes. We may have realized that something happened in a particular case or left a value that was particular to the parameters that we chose. If there are any mistakes, we would like to find them before we start translating our algorithm into code. For this reason, we are going to check with one or more inputs with a manageable size that can be done by our hand.
1) Consider city 1 as the starting and ending point.2) Generate all (n-1)! Permutations of cities.
3) Calculate the cost of every permutation and keep track of the minimum cost permutation.
4) Return the permutation with minimum cost.
Step 5: Translate To Code
When we are confident with our algorithm, we start translating it into code. Here, the actual coding happens. The implementation of our algorithm is shown here with JavaScript.
/*
Code taken from https://www.geeksforgeeks.org/
travelling-salesman-problem-using-dynamic-programming/
*/ const n = 4; // four nodes in example graph
let MAX = 1000000; // give appropriate maximum to avoid overflow
// dist[i][j] represents shortest distance to go from i to j
// this matrix can be calculated for any given graph using
// all-pair shortest path algorithms
let dist = [
[0, 0, 0, 0, 0], [0, 0, 10, 15, 20],
[0, 10, 0, 25, 25], [0, 15, 25, 0, 30],
[0, 20, 25, 30, 0],
];
// memoization for top down recursion
let memo = new Array(n + 1);
for (let i = 0; i < memo.length; i++) {
memo[i] = new Array(1 << (n + 1)).fill(0)
}
function fun(i, mask)
{
// base case
// if only ith bit and 1st bit is set in our mask,
// it implies we have visited all other nodes already
if (mask == ((1 << i) | 3))
return dist[1][i];
// memoization
if (memo[i][mask] != 0)
return memo[i][mask];
let res = MAX; // result of this sub-problem
// we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all nodes in
// mask except i and then travel back from node j to
// node i taking the shortest path take the minimum of
// all possible j nodes
for (let j = 1; j <= n; j++)
if ((mask & (1 << j)) && j != i && j != 1)
res = Math.min(res, fun(j, mask & (~(1 << i)))
+ dist[j][i]);
return memo[i][mask] = res;
}
// Driver program to test above logic
let ans = MAX;
for (let i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i][1]);
console.log("The cost of most efficient tour " + ans);
Step 6: Run Test Cases
Once we write our code, we want to run test cases to make sure that the program that we wrote gets the answer based on what we expect the right answer to be, knowing what problem we’re trying to solve. Every time when we run a test case, the right answer that we get will give us more confidence in our program. If it fails we move to step 7, debugging the failed cases.
Step 7: Debug Failed Test Cases
In debugging, we can use various tools to find out the exact point where we made a programming mistake. By revisiting the point and understanding the logic that triggered the mistake we can revisit the steps to fix those mistakes
Ultimately, if we encounter an algorithmic problem, we’ll go back to Step 3 and fix it. In the event that our algorithm can’t be translated into code (implementation problem), we will go back to Step 5 and correct our translation of our algorithm to code.
Note: To learn about JavaScript visit https://github.com/sumn2u/learn-javascript.
Conclusion
From our program implementation, we found that the 1–2–4–3–1 path is cost-effective and the cost for the tour is 80 which is true. Using the seven-step approach shown above, we solve the TSP problem and can use it as a guide to solve other programming problems.
