dynamic programmingABLess.pptx

Dynamic Programming Floyd–Warshall algorithm Traveling Salesman Problem 0/1 Knapsack problem | Dynamic Programming https://www.youtube.com/watch?v=SIvjuz91hgU https://www.youtube.com/watch?v=33k8EPNriTM  Backtracking Th...

Dynamic Programming Floyd–Warshall algorithm Traveling Salesman Problem 0/1 Knapsack problem | Dynamic Programming https://www.youtube.com/watch?v=SIvjuz91hgU https://www.youtube.com/watch?v=33k8EPNriTM  Backtracking The General method, the n-Queens problem, Subset-sum Problem.  What is Backtracking? Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end. It is commonly used in situations where you need to explore multiple possibilities to solve a problem, like searching for a path in a maze or solving puzzles like Sudoku. When a dead end is reached, the algorithm backtracks to the previous decision point and explores a different path until a solution is found or all possibilities have been exhausted. Types of Backtracking Problems Problems associated with backtracking can be categorized into 3 categories: Decision Problems: Here, we search for a feasible solution. Optimization Problems: For this type, we search for the best solution. Enumeration Problems: We find set of all possible feasible solutions to the problems of this type. ocode: IND_SOLUTIONS( parameters): (valid solution): store the solution Return r (all choice): if (valid choice): APPLY (choice) FIND_SOLUTIONS (parameters) BACKTRACK (remove choice) eturn Complexity Analysis of Backtracking Since backtracking algorithm is purely brute force therefore in terms of time complexity, it performs very poorly. Generally backtracking can be seen having below mentioned time complexities: Exponential (O(K^N)) Factorial (O(N!)) These complexities are due to the fact that at each state we have multiple choices due to which the number of paths increases and sub-trees expand rapidly. Applications of Backtracking Creating smart bots to play Board Games such as Chess. Solving mazes and puzzles such as N-Queen problem. Network Routing and Congestion Control. Decryption Text Justification