Fractional knapsack problem

Video is also available : https://youtu.be/BXxKPB-58l4

1. Advanced Artificial Intelligence MSCS 1 Lecture 5

2. Greedy search Greedy search is a variation of the A* algorithm, where g(node) is set to zero , so that only h(node) is used to evaluate suitable paths. In this way, the algorithm always selects the path that has the lowest heuristic value or estimated distance (or cost) to the goal. Greedy search is an example of a best-first strategy. Greedy-search methods tend to be reasonably efficient, although in the worst case , like depth-first search, it may never find a solution at all.

3. Knapsack problem The knapsack problem is an interesting illustration of the use of greedy search algorithms and their pitfalls. The fractional knapsack problem can be expressed as follows : A man is packing items into his knapsack. He wants to take the most valuable items he can, but there is a limit on how much weight he can fit in his knapsack . Each item has a weight wi and is profit p i . He can only fit a total weight of W in his knapsack.

4. Knapsack problem The items that he wants to take are things that can be broken up and still retain their value (like flour or milk), and he is The items that he wants to take are things that can be broken up and still retain their value (like flour or milk), and he is able to take fractions of items. Hence, the problem is called the fractional knapsack problem. In solving this problem, a greedy-search algorithm provides the best solution. The problem is solved by calculating the value per unit weight of each item: p i / wi , and then taking as much as he can carry of the item with the greatest value per unit weight. If he still has room, he moves on to the item with the next highest value per unit weight, and so on .

5. Fractional Knapsack problem Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Items N = 7 Bag capacity M = 15

6. Fractional Knapsack problem Now we have a bag with capacity of 15. lets suppose 15 kg. Now we want to transfer this bag from one location to another. We are facing this problem in daily life. Now problem is to filling of the objects in a container. If you put all the objects in the bag with the capacity, there is no problem. But the objects weight is more than the bag capacity, here the problem start.

7. Fractional Knapsack problem W e should maximize the profit. So this problem is optimization problem. Can we apply the greedy method to solve this problem? Yes, if it is suitable. So what are the constraints here? The bag capacity is 15, so all the objects which we want to transfer should be <= 15.

8. Fractional Knapsack problem For this problem we have many solutions. The optimal result is to gain a maximum profit. X = {x1, x2, x3, x4, x5, x6, x7} We can say this problem is a fractional problem 0 ≤ X ≤ 1

9. Fractional Knapsack problem Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3 Items n = 7 Bag capacity m = 15

10. Fractional Knapsack problem Profit of each item per kg is X1 = 5, x2=1.3, x3=3, x4=1, x5=6, x6=4.5, x7=3 Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3 Items n = 7 Bag capacity m = 15

11. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3 Items n = 7 Bag capacity m = 15

12. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

13. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

14. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

15. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

16. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

17. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

18. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

19. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

20. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

21. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

22. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

23. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3

24. Fractional Knapsack problem Now we select the items on the basis of their profit Objects 1 2 3 4 5 6 7 Profits p 10 5 15 7 6 18 3 Weights w 2 3 5 7 1 4 1 Max profit p/w 5 1.3 3 1 6 4.5 3 Items n = 7 Bag capacity m = 15

25. A* algorithm for searching Informed searching algorithm A* Search algorithm is one of the best and popular technique used in path-finding and graph traversals. Informally speaking, A* Search algorithms, unlike other traversal techniques, it has “brains”. What it means is that it is really a smart algorithm which separates it from the other conventional algorithms. And it is also worth mentioning that many games and web-based maps use this algorithm to find the shortest path very efficiently (approximation).

26. A* algorithm for searching A* algorithms are similar to best-first search but use a somewhat more complex heuristic to select a path through the tree. The best-first algorithm always extends paths that involve moving to the node that appears to be closest to the goal, but it does not take into account the cost of the path to that node so far. The A* algorithm operates in the same manner as best-first search but uses the following function to evaluate nodes: f(n) = g(n) + h(n)

27. A* algorithm for searching g (n)--- actual cost from start node to n. h (n)--- estimation cost from n to goal node.

28. A* algorithm for searching S is start node and G is goal node. A* is an admissible algorithm which mean that it will give an optimal solution.

29. A* algorithm for searching We are taking a directed graph in this example. We also can take a tree to solve this problem. From S to B, 4 is actual value and in red color 12 is heuristic value.

30. A* algorithm for searching Explore S, SB, SC.

31. A* algorithm for searching We explore SCE, SCD, SBF, SBE

32. A* algorithm for searching We explore SCE, SCD, SBF, SBE

33. A* algorithm for searching We explore SCDEG

34. A* algorithm for searching Time complexity T(C) = O( v+E ) In artificial intelligence point of view O( b^d ) Where b is the branch factor, d is the depth.