->Shortest path problem #For unweighted undirected graphs# -Uses:breadth-first search in a graph, the shortest path is the way that the minimum edges found between two vertices also, the solution to the shortest path problem for an unweighted graph is actually a breadth-first search and search for a certain vertex with a minimum number of edges to reach to that vertex #For weighted undirected graphs# -Dijkstra's (Greedy algorithm) can find the shortest path, in this case, a distance between two nodes can be calculated by setting all distance metric at each node to infinity and this value will be changed as we calculate the distance over the graph ---Algorithm- -we begin by giving all vertices a distance value which is the sum of edge weights on a path between our starting point and whatever vertex we are on. at the end of the algorithm, this distance will be the distance of the shortest path. -the distance value we start with is infinity which will update whenever we discover a node and have an actual distance to store. -the node we are starting with will have a distance of zero -we will implement dijkstras with the min-priority queue, where the element with a minimum priority, or minimum distance in our case, can be removed efficiently. -we store all of our nodes in the priority queue and use 'Extract min' to take out the minimum element, the only one with a distance of zero(the start node). -from our starting node, we have several options. we will follow each edge and update the node on the other side with a distance value, which is just the weight of the edge. -now we will choose the node with the smallest distance value to visit which means "Extract min on the queue". -Dijkstra's often called greedy algorithm because it depends on pick whatever option looks best at the moment. -we repeat the process visiting all adjacent nodes that are still in the queue and updating their distance values if we can decrease it at all. -keep going extracting the minimum from our queue and exploring adjacent elements, until the node we are looking for has been extracted from the queue or everything else has a distance of infinity. the basic runtime of Dijkstra is the number of vertices squared:: O(|v|^2) ->worst case but there are many implementations for Dijkstra's and if it implemented really efficiently the runtime looks more like this:: O(|E|+|V|*Log(|v|)) ->average case where V->Vertix and E->Edge ---------------------------------------------------------------------------------------- ->0-1 Knapsack Problem ----Take Or Leave suppose we have a knapsack and we have many items each with weight and value and we want to fill the knapsack with items with the highest value but without a hit the weight limit of the knapsack so have we had to try each combination and select the one with the highest value and appropriate weight or we have to follow an algorithm:)? ->Brute Force solution:: try each combination and pick the one that is best. the run time for this solution is O(2^n) where n is the number of objects, there are also 2^n possible combinations example suppose we have 2 elements the possible combinations are 01-10-11-00 which is 2^2=4 the run time O(2^n) is an exponential time algorithm (NP-problem) the p-problems are n^2 or 3n which is much faster than NP-problems for a big numbers -> a faster algorithm (Dynamic programming solution):: is depend on comparing the maximum weight to those of the objects that will maximize the available weight code will easily see it. this algorithm has an efficiency of O(nW) n-> number of elements and W->weight limit this is a Pseudo-Polynomial Time O(nW) also, a True-Polynomial Time wouldn't have a variable n besides n. Polynomial-Time algorithms are much faster than exponential Time algorithms for big numbers so the solution here is generally faster than brute force algorithm. -> the previous algorithm is much like a dynamic programming solution as it breaks the problem into subproblems and solves them then you solve the big problem this method has a technique in a video with this folder ->(knapsack problem) watch it know more about this technique --------------------------------------------------------------------------------------------- Traveling salesman problem -:(NP-hard) a traveling man want to travel between 32 cities across the USA and want to travel by the shortest path between the cities then come back home with the shortest distance between all 32 cities? here the solution needs to know more about P and NP-problems. NP-hard problems are problems that don't have known algorithm that can solve them in polynomial time since the problem is so difficult, there are two classes of algorithms considered solutions. ->exact algorithm -: give us the exact answer which doesn't happen in polynomial time but will get us the correct answer -->these solutions are such as ---Brute Force:: which is much like the one for knapsack problem find every possible combination and pick the best one but it takes significantly longer time O(n!) ---Dynamic programming solution:: for TSP the most famous one in the Held-Karp Algorithm-O((2^n)(n^2)) but also it is very slow cause it is in exponential time ->approximation Algorithms -: doesn't find the exact solution and find approximate one but happen in polynomial time ---christofides Algorithm -: works by turning a graph into a tree where the starting node is the root creating and traversing through it in a particular intelligent way. the algorithm guarantees that the path it produces will be at most 50% longer than the shortest route there have been some slight improvements on this first specific cases of TSP but generally, it is considered to be the best there is. ----------------------------------------------------------------------------------- P-problems -: problems in polynomial time which is the fastest problems and can be checked easily and solved easily NP-problems -: problem in a non-polynomial time that take much time to run O(N^2) or O(2^N) but can be solved and checked easily with much time to run NP-Complete -: problems that we can't solve easily but can be checked even it is very difficult to check such as finding longest common subset between two sets? NP-Hard -: problems that can't be checked and can't be solved easily such as TSP- problem
- Get link
- Other Apps
->Shortest path problem #For unweighted undirected graphs# -Uses:breadth-first search in a graph, the shortest path is the way that the minimum edges found between two vertices also, the solution to the shortest path problem for an unweighted graph is actually a breadth-first search and search for a certain vertex with a minimum number of edges to reach to that vertex #For weighted undirected graphs# -Dijkstra's (Greedy algorithm) can find the shortest path, in this case, a distance between two nodes can be calculated by setting all distance metric at each node to infinity and this value will be changed as we calculate the distance over the graph ---Algorithm- -we begin by giving all vertices a distance value which is the sum of edge weights on a path between our starting point and whatever vertex we are on. at the end of the algorithm, this distance will be the distance of the shortest path. -the distance value we start with is infinity which will update whenever we discover a node and have an actual distance to store. -the node we are starting with will have a distance of zero -we will implement dijkstras with the min-priority queue, where the element with a minimum priority, or minimum distance in our case, can be removed efficiently. -we store all of our nodes in the priority queue and use 'Extract min' to take out the minimum element, the only one with a distance of zero(the start node). -from our starting node, we have several options. we will follow each edge and update the node on the other side with a distance value, which is just the weight of the edge. -now we will choose the node with the smallest distance value to visit which means "Extract min on the queue". -Dijkstra's often called greedy algorithm because it depends on pick whatever option looks best at the moment. -we repeat the process visiting all adjacent nodes that are still in the queue and updating their distance values if we can decrease it at all. -keep going extracting the minimum from our queue and exploring adjacent elements, until the node we are looking for has been extracted from the queue or everything else has a distance of infinity. the basic runtime of Dijkstra is the number of vertices squared:: O(|v|^2) ->worst case but there are many implementations for Dijkstra's and if it implemented really efficiently the runtime looks more like this:: O(|E|+|V|*Log(|v|)) ->average case where V->Vertix and E->Edge ---------------------------------------------------------------------------------------- ->0-1 Knapsack Problem ----Take Or Leave suppose we have a knapsack and we have many items each with weight and value and we want to fill the knapsack with items with the highest value but without a hit the weight limit of the knapsack so have we had to try each combination and select the one with the highest value and appropriate weight or we have to follow an algorithm:)? ->Brute Force solution:: try each combination and pick the one that is best. the run time for this solution is O(2^n) where n is the number of objects, there are also 2^n possible combinations example suppose we have 2 elements the possible combinations are 01-10-11-00 which is 2^2=4 the run time O(2^n) is an exponential time algorithm (NP-problem) the p-problems are n^2 or 3n which is much faster than NP-problems for a big numbers -> a faster algorithm (Dynamic programming solution):: is depend on comparing the maximum weight to those of the objects that will maximize the available weight code will easily see it. this algorithm has an efficiency of O(nW) n-> number of elements and W->weight limit this is a Pseudo-Polynomial Time O(nW) also, a True-Polynomial Time wouldn't have a variable n besides n. Polynomial-Time algorithms are much faster than exponential Time algorithms for big numbers so the solution here is generally faster than brute force algorithm. -> the previous algorithm is much like a dynamic programming solution as it breaks the problem into subproblems and solves them then you solve the big problem this method has a technique in a video with this folder ->(knapsack problem) watch it know more about this technique --------------------------------------------------------------------------------------------- Traveling salesman problem -:(NP-hard) a traveling man want to travel between 32 cities across the USA and want to travel by the shortest path between the cities then come back home with the shortest distance between all 32 cities? here the solution needs to know more about P and NP-problems. NP-hard problems are problems that don't have known algorithm that can solve them in polynomial time since the problem is so difficult, there are two classes of algorithms considered solutions. ->exact algorithm -: give us the exact answer which doesn't happen in polynomial time but will get us the correct answer -->these solutions are such as ---Brute Force:: which is much like the one for knapsack problem find every possible combination and pick the best one but it takes significantly longer time O(n!) ---Dynamic programming solution:: for TSP the most famous one in the Held-Karp Algorithm-O((2^n)(n^2)) but also it is very slow cause it is in exponential time ->approximation Algorithms -: doesn't find the exact solution and find approximate one but happen in polynomial time ---christofides Algorithm -: works by turning a graph into a tree where the starting node is the root creating and traversing through it in a particular intelligent way. the algorithm guarantees that the path it produces will be at most 50% longer than the shortest route there have been some slight improvements on this first specific cases of TSP but generally, it is considered to be the best there is. ----------------------------------------------------------------------------------- P-problems -: problems in polynomial time which is the fastest problems and can be checked easily and solved easily NP-problems -: problem in a non-polynomial time that take much time to run O(N^2) or O(2^N) but can be solved and checked easily with much time to run NP-Complete -: problems that we can't solve easily but can be checked even it is very difficult to check such as finding longest common subset between two sets? NP-Hard -: problems that can't be checked and can't be solved easily such as TSP- problem
Comments