Optimization Problems
I think you guys are aware of what really an Optimization Problem. But if you are not, then I will explain to you what really these Optimization problem is, and what could be the possible solutions for that.
Optimization Problem:- It is a problem of finding the best possible solution from all the feasible solutions.
Now we will understand this with the help of an example. Let’s say there is a weighted graph
on the left side. In this A, B..E are the nodes and AC is an Edge whose weight is 5. Similarly, the graph consists of other edges with corresponding weights. So what if we have to find the shortest path from node A to node E.
Question:- What is the shortest path from node A to E ?.
Answer:- The simplest way to solve this is Exhaustive Approach. Here exhaustive approach means first to find out all the possible path from node A to node E, and then among all those possible outcomes, find the one path with the least value.
So if there are n edges, then in a path an edge might be present or might not be present, in that case for every edge we have two chances. Therefore we have to examine total 2^n paths. So by this kind of approach, we might end up with exponential time i.e O(2^n).
Now we have to see if we could find something better than O(2^n).To solve these kinds of Optimization problems, there are two programming paradigms…
- Greedy Method Approach
- Dynamic Programming
Greedy Approach:- With the greedy approach we can solve optimization problems but not all of them. A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.
Dynamic Programming(DP):- With the help of DP we will be able to solve any optimization problem, but some problem even after applying dynamic programming might go to exponential time. So with dynamic programming, we could get O(n^k) solutions.
So instead of talking about the theory, and what are the characteristics that a problem should contain, I would pick up some problems and we shall see how these methods would be applied. So after seeing examples, above theory will be very much clear to you. So in the next post, we will talk about Greedy method.
If you like the my hard work and effort, you can do one clap, two clap or may be fourty…
You can also find me on..
