DYNAMIC PROGRAMMING

Information about DYNAMIC PROGRAMMING

Published on March 6, 2009

Author: ankush85

Source: authorstream.com

Content

DYNAMIC PROGRAMMING : DYNAMIC PROGRAMMING Problems like knapsack problem, shortest path can be solved by greedy method in which optimal decisions can be made one at a time. For many problems, it is not possible to make stepwise decision in such a manner that the sequence of decisions made is optimal. DYNAMIC PROGRAMMING (Contd..) : DYNAMIC PROGRAMMING (Contd..) Example: Suppose a shortest path from vertex i to vertex j is to be found. Let Ai be vertices adjacent from vertex i. which of the vertices of Ai should be the second vertex on the path? One way to solve the problem is to enumerate all decision sequences and pick out the best. In dynamic programming the principle of optimality is used to reduce the decision sequences. DYNAMIC PROGRAMMING (Contd..) : 3 DYNAMIC PROGRAMMING (Contd..) Principle of optimality: An optimal sequence of decisions has the property that whatever the initial state and decisions are, the remaining decisions must constitute an optional decision sequence with regard to the state resulting from the first decision. In the greedy method only one decision sequence is generated. In dynamic programming many decision sequences may be generated. DYNAMIC PROGRAMMING (Contd..) : DYNAMIC PROGRAMMING (Contd..) Example: [0/1 knapsack problem]:the xi’s in 0/1 knapsack problem is restricted to either 0 or 1. Using KNAP(l,j,y) to represent the problem Maximize ?pixi l=i=j subject to ?wixi = y, ………………..(1) l=i=j xi = 0 or 1 l=i=j The 0/1 knapsack problem is KNAP(l,n,M). DYNAMIC PROGRAMMING (Contd..) : DYNAMIC PROGRAMMING (Contd..) Let y1 ,y2 , …… ,yn be an optimal sequence of 0/l values for x1 ,x2 …..,xn respectively. If y1 = 0 then y2,y3,……,yn must constitute an optimal sequence for KNAP (2,n,M). If it does not, then y1 ,y2 , …… ,yn is not an optimal sequence for KNAP (1, n, M). If y1=1, then y1 ,y2 , …… ,yn is an optimal sequence for KNAP(2,n,M-wi ). If it is not there is another 0/l sequence z1,z2,….,zn such that ?pizi has greater value. Thus the principal of optimality holds. DYNAMIC PROGRAMMING (Contd..) : 6 DYNAMIC PROGRAMMING (Contd..) Let gj(y) be the value of an optimal solution to KNAP (j+1,n,y). Then g0(M) is the value of an optimal solution to KNAP(l,n,M). From the principal of optimality g0(M) = max{g1(M), g1(M-W1) + P1)} g0(M) is the maximum profit which is the value of the optimal solution . DYNAMIC PROGRAMMING (Contd..) : DYNAMIC PROGRAMMING (Contd..) The principal of optimality can be equally applied to intermediate states and decisions as has been applied to initial states and decisions. Let y1,y2,…..yn be an optimal solution to KNAP(l,n,M). Then for each j l=j=n , yi,..,yj and yj+1,….,yn must be optimal solutions to the problems KNAP(1,j,?wiyi) l=i=j and KNAP(j+1,n,M-?wiyi) respectively. l=i=j DYNAMIC PROGRAMMING (Contd..) : 8 DYNAMIC PROGRAMMING (Contd..) Then gi(y) = max{gi+1(y) (xi +1= 0 case), gi+1(y-wi +1) + pi+1}…(1) (xi +1= 1case), Equation (1) is known as recurrence relation. Dynamic programming algorithms solve the relation to obtain a solution to the given problems. To solve 0/1 knapsack problem , we use the knowledge gn(y) = 0 for all y, because gn(y) is on optimal solution (profit) to the problem KNAP(n+1, n, y) which is obviously zero for any y. DYNAMIC PROGRAMMING (Contd..) : 9 DYNAMIC PROGRAMMING (Contd..) Substituting i = n -1 and using gn(y)= 0 in the above relation(1), we obtain gn-1(y). Then using gn-1(y), we obtain gn-2(y) and so on till we get g0(M) (with i=0) which is the solution of the knapsack problem. There are two approaches to solving the recurrence relation 1 (1) Forward approach and (2) Backward approach DYNAMIC PROGRAMMING (Contd..) : 10 DYNAMIC PROGRAMMING (Contd..) In the forward approach ,decision xi is made in terms of optimal decision Sequences for xi+1……..xn (i.e we look ahead). In the backward approach, decision xi is in terms of optimal decision sequences for x1……xi-1(i.e we look backward). DYNAMIC PROGRAMMING (Contd..) : 11 DYNAMIC PROGRAMMING (Contd..) For the 0/l knapsack problems Gi(y)=max{gi+1(y),gi+1(y-wi+1)+Pi+1}………(1) Is the forward approach as gn-1(y) is obtained using gn(y). fi(y) = max{fj-1(y), fj-1(y-wi) + pj} …………..(2) is the backward approach, fj(y) is the value of optimal solution to Knap(i,j,Y). (2) may be solved by beginning with fi(y) = 0 for all y = 0 and fi(y) = -infinity for y < 0. FEATURES OF DYNAMIC PROGRAMMING SOLUTIONS : 12 FEATURES OF DYNAMIC PROGRAMMING SOLUTIONS It is easier to obtain the recurrence relation using backward approach. Dynamic programming algorithms often have polynomial complexity. Optimal solution to sub problems are retained so as to avoid recomputing their values. OPTIMAL BINARY SEARCH TREES : 13 OPTIMAL BINARY SEARCH TREES Definition: binary search tree (BST) A binary search tree is a binary tree; either it is empty or each node contains an identifier and all identifiers in the left sub tree of T are less than the identifiers in the root node T. (ii) all the identifiers the right sub tree are greater than the identifier in the root node T. (iii) the right and left sub tree are also BSTs. ALGORITHM TO SEARCH FOR AN IDENTIFIER IN THE TREE ‘T’. : 14 ALGORITHM TO SEARCH FOR AN IDENTIFIER IN THE TREE ‘T’. Procedure SEARCH (T X I) // Search T for X, each node had fields LCHILD, IDENT, RCHILD// // Return address i pointing to the identifier X// //Initially T is pointing to tree. //ident(i)=X or i=0 // i ? T Algorithm to search for an identifier in the tree ‘T’(Contd..) : 15 Algorithm to search for an identifier in the tree ‘T’(Contd..) While i ? 0 do case : X < Ident(i) : i ?LCHILD(i) : X = IDENT(i) : RETURN i : X > IDENT(i) : I ? RCHILD(i) endcase repeat end SEARCH Optimal Binary Search trees - Example : 16 Optimal Binary Search trees - Example If For while repeat loop if each identifier is searched with equal probability the average number of comparisons for the above tree are 1+2+2+3+4 = 12/5. 5 OPTIMAL BINARY SEARCH TREES (Contd..) : 17 OPTIMAL BINARY SEARCH TREES (Contd..) Let us assume that the given set of identifiers are {a1,a2,……..an} with a1<a2<…….<an. Let Pi be the probability with which we are searching for ai. Let Qi be the probability that identifier x being searched for is such that ai<x<ai+1 0=i=n, and a0=-8 and an+1=+8. OPTIMAL BINARY SEARCH TREES (Contd..) : 18 OPTIMAL BINARY SEARCH TREES (Contd..) Then ?Qi is the probability of an unsuccessful search. 0=i= n ?P(i) + ?Q(i) = 1. Given the data, 1=i=n 0=i=n let us construct one optimal binary search tree for (a1……….an). In place of empty sub tree, we add external nodes denoted with squares. Internet nodes are denoted as circles. OPTIMAL BINARY SEARCH TREES (Contd..) : 19 OPTIMAL BINARY SEARCH TREES (Contd..) If For while repeat loop Construction of optimal binary search trees : 20 Construction of optimal binary search trees A BST with n identifiers will have n internal nodes and n+1 external nodes. Successful search terminates at internal nodes unsuccessful search terminates at external nodes. If a successful search terminates at an internal node at level L, then L iterations of the loop in the algorithm are needed. Hence the expected cost contribution from the internal nodes for ai is P(i) * level(ai). OPTIMAL BINARY SEARCH TREES (Contd..) : 21 OPTIMAL BINARY SEARCH TREES (Contd..) Unsuccessful searche terminates at external nodes i.e. at i = 0. The identifiers not in the binary search tree may be partitioned into n+1 equivalent classes Ei 0=i=n. Eo contains all X such that X=ai Ei contains all X such that a<X<=ai+1 1=i=n En contains all X such that X > an OPTIMAL BINARY SEARCH TREES (Contd..) : 22 OPTIMAL BINARY SEARCH TREES (Contd..) For identifiers in the same class Ei, the search terminate at the same external node. If the failure node for Ei is at level L, then only L-1 iterations of the while loop are made ?The cost contribution of the failure node for Ei is Q(i) * level (Ei ) -1) OPTIMAL BINARY SEARCH TREES (Contd..) : 23 OPTIMAL BINARY SEARCH TREES (Contd..) Thus the expected cost of a binary search tree is: ?P(i) * level (ai) + ?Q(i) * level(Ei) – 1) ……(2) 1=i=n 0=i=n An optimal binary search tree for {a1…….,an} is a BST for which (2) is minimum . Example: Let {a1,a2, a3}={do, if, stop} OPTIMAL BINARY SEARCH TREES (Contd..) : 24 OPTIMAL BINARY SEARCH TREES (Contd..) Level 1 stop if do Level 2 if Q(3) do stop if Q(2) Level 3 do stop Q(0) Q(1) (a) (b) (c) {a1,a2,a3}={do,if,stop} OPTIMAL BINARY SEARCH TREES (Contd..) : 25 OPTIMAL BINARY SEARCH TREES (Contd..) stop do do stop if if (d) (c) OPTIMAL BINARY SEARCH TREES (Contd..) : 26 OPTIMAL BINARY SEARCH TREES (Contd..) With equal probability P(i)=Q(i)=1/7. Let us find an OBST out of these. Cost(tree a)=?P(i)*level a(i) +?Q(i)*level (Ei) -1 1=i=n 0=i=n (2-1) (3-1) (4-1) (4-1) =1/7[1+2+3 + 1 + 2 + 3 + 3 ] = 15/7 Cost (tree b) =17[1+2+2+2+2+2+2] =13/7 Cost (tree c) =cost (tree d) =cost (tree e) =15/7 ? tree b is optimal. OPTIMAL BINARY SEARCH TREES (Contd..) : 27 OPTIMAL BINARY SEARCH TREES (Contd..) If P(1) =0.5 ,P(2) =0.1, P(3) =0.005 , Q(0) =.15 , Q(1) =.1, Q(2) =.05 and Q(3) =.05 find the OBST. Cost (tree a) = .5 x 3 +.1 x 2 +.05 x 3 +.15x3 +.1x3 +.05x2 +.05x1 = 2.65 Cost (tree b) =1.9 , Cost (tree c) =1.5 ,Cost (tree d) =2.05 , Cost (tree e) =1.6 Hence tree C is optimal. OPTIMAL BINARY SEARCH TREES (Contd..) : 28 OPTIMAL BINARY SEARCH TREES (Contd..) To obtain a OBST using Dynamic programming we need to take a sequence of decisions regard. The construction of tree. First decision is which of ai is be as root. Let us choose ak as the root . Then the internal nodes for a1,…….,ak-1 and the external nodes for classes Eo,E1,……,Ek-1 will lie in the left subtree L of the root. The remaining nodes will be in the right subtree R. OPTIMAL BINARY SEARCH TREES (Contd..) : 29 OPTIMAL BINARY SEARCH TREES (Contd..) Define Cost(L) =?P(i)* level(ai) + ?Q(i)*(level(Ei )-1) 1=i=k 0=i=k Cost(R) =?P(i)*level(ai) + ?Q(i)*(level(Ei )-1) k=i=n k=i=n Tij be the tree with nodes ai+1,…..,aj and nodes corresponding to Ei,Ei+1,…..,Ej. Let W(i,j) represents the weight of tree Tij. OPTIMAL BINARY SEARCH TREES (Contd..) : 30 OPTIMAL BINARY SEARCH TREES (Contd..) W(i,j)=P(i+1) +…+P(j)+Q(i)+Q(i+1)…Q(j)=Q(i) +?j [Q(l)+P(l)] l=i+1 The expected cost of the search tree in (a) is (let us call it T) is   P(k)+cost(l)+cost(r)+W(0,k-1)+W(k,n) W(0,k-1) is the sum of probabilities corresponding to nodes and nodes belonging to equivalent classes to the left of ak. W(k,n) is the sum of the probabilities corresponding to those on the right of ak. ak L R (a) OBST with root ak

Related presentations


Other presentations created by ankush85

Nanotechnology
03. 04. 2009
0 views

Nanotechnology

Human Resource Management System
06. 03. 2009
0 views

Human Resource Management System

Nanotechnology
27. 03. 2009
0 views

Nanotechnology

INTRODUCTION TO NANOTECHNOLOGY
20. 11. 2009
0 views

INTRODUCTION TO NANOTECHNOLOGY

Nanotechnology in Sports
22. 11. 2009
0 views

Nanotechnology in Sports

Computer Architecture
14. 07. 2009
0 views

Computer Architecture

HR
18. 03. 2009
0 views

HR

Hospital Management System
08. 04. 2009
0 views

Hospital Management System

Welcome to Visual Basic
06. 03. 2009
0 views

Welcome to Visual Basic

HTML
20. 04. 2009
0 views

HTML

Computer Languages
03. 06. 2013
0 views

Computer Languages

Taking Care of Computer
03. 06. 2013
0 views

Taking Care of Computer

Understanding Camera
16. 10. 2012
0 views

Understanding Camera

Photography Technical Terms
25. 09. 2012
0 views

Photography Technical Terms

Basics of Photography
25. 09. 2012
0 views

Basics of Photography

AIR MUSCLES
03. 01. 2012
0 views

AIR MUSCLES

Molecular Nanotechnology
24. 11. 2009
0 views

Molecular Nanotechnology

Nanotech Innovation
22. 11. 2009
0 views

Nanotech Innovation

FINANCIAL  MARKET
16. 05. 2009
0 views

FINANCIAL MARKET

Operating System
19. 04. 2009
0 views

Operating System

Management Control
10. 07. 2009
0 views

Management Control

Accounting Principles
01. 07. 2009
0 views

Accounting Principles

Balance Sheet
21. 07. 2009
0 views

Balance Sheet

Balance Sheet Auditing
01. 07. 2009
0 views

Balance Sheet Auditing

BRANCH AND BOUND
05. 03. 2009
0 views

BRANCH AND BOUND

THE  THREE  BRANCHES  OF GOVERNMENT
13. 06. 2009
0 views

THE THREE BRANCHES OF GOVERNMENT

Structure of Atom
11. 05. 2009
0 views

Structure of Atom

Compression Techniques
05. 03. 2009
0 views

Compression Techniques

Quantum Mechanics
25. 08. 2009
0 views

Quantum Mechanics

Marketing Plan
19. 06. 2009
0 views

Marketing Plan

Book Keeping
24. 06. 2009
0 views

Book Keeping

DFDS
02. 10. 2008
0 views

DFDS

Semiconductors
25. 04. 2009
0 views

Semiconductors

Organic  Chemistry
28. 04. 2009
0 views

Organic Chemistry

Atoms Molecules and Ions
17. 06. 2009
0 views

Atoms Molecules and Ions

Covalent Bond
25. 04. 2009
0 views

Covalent Bond

Cost Accounting Standards
25. 06. 2009
0 views

Cost Accounting Standards

Crisis Management
19. 06. 2009
0 views

Crisis Management

Marketing
18. 03. 2009
0 views

Marketing

Business Strategy
27. 04. 2009
0 views

Business Strategy

Time Management
23. 03. 2009
0 views

Time Management

Networking Protocols
23. 05. 2009
0 views

Networking Protocols

Network Layer
23. 05. 2009
0 views

Network Layer

Final Accounts
24. 06. 2009
0 views

Final Accounts

ARTIFICIAL  INTELLIGENCE
03. 04. 2009
0 views

ARTIFICIAL INTELLIGENCE

Play with C
08. 04. 2009
0 views

Play with C

Software Development Cycle
23. 03. 2009
0 views

Software Development Cycle

THE GREEDY METHOD
06. 03. 2009
0 views

THE GREEDY METHOD

JOB SEQUENCING
06. 03. 2009
0 views

JOB SEQUENCING

Electricity and Magnetism
29. 04. 2009
0 views

Electricity and Magnetism

Optical Fiber
24. 05. 2009
0 views

Optical Fiber

Quality Assurance
06. 03. 2009
0 views

Quality Assurance

Object-oriented Design
11. 04. 2009
0 views

Object-oriented Design

A.R. Rahman
08. 03. 2009
0 views

A.R. Rahman

Hollywood Female Celebrities
13. 03. 2009
0 views

Hollywood Female Celebrities

Flow nets
04. 09. 2009
0 views

Flow nets

Energy and Nanotechnology
22. 11. 2009
0 views

Energy and Nanotechnology

LOGIC  DESIGN
06. 03. 2009
0 views

LOGIC DESIGN

VB-IDE
06. 03. 2009
0 views

VB-IDE

DLF IPL FINAL
25. 05. 2009
0 views

DLF IPL FINAL

MINIMUM SPANNING TREES
06. 03. 2009
0 views

MINIMUM SPANNING TREES

CPU Scheduling
05. 03. 2009
0 views

CPU Scheduling

Virtual Memory
05. 03. 2009
0 views

Virtual Memory

POK
09. 05. 2009
0 views

POK

2D Transformations
05. 03. 2009
0 views

2D Transformations

Greedy Algorithms
05. 03. 2009
0 views

Greedy Algorithms

BACKTRACKING
05. 03. 2009
0 views

BACKTRACKING

DIVIDE And CONQUER
06. 03. 2009
0 views

DIVIDE And CONQUER

ELEMENTARY DATA STRUCTURES
06. 03. 2009
0 views

ELEMENTARY DATA STRUCTURES

JPEG Compression
06. 03. 2009
0 views

JPEG Compression

Mpeg-compression
06. 03. 2009
0 views

Mpeg-compression

NP - HARD
06. 03. 2009
0 views

NP - HARD

TRAVELLING SALESPERSON PROBLEM
06. 03. 2009
0 views

TRAVELLING SALESPERSON PROBLEM

VBA Introduction
06. 03. 2009
0 views

VBA Introduction

Introduction to Java
09. 03. 2009
0 views

Introduction to Java

Java  Basics
09. 03. 2009
0 views

Java Basics

Heuristic Search
13. 03. 2009
0 views

Heuristic Search

HSM
19. 03. 2009
0 views

HSM

Tata's  Nano  Car
25. 03. 2009
0 views

Tata's Nano Car

Air Cranes
08. 04. 2009
0 views

Air Cranes

Newborn Care
10. 04. 2009
0 views

Newborn Care

Photosynthesis Process
10. 04. 2009
0 views

Photosynthesis Process

ActionScript
13. 04. 2009
0 views

ActionScript

Xml
15. 04. 2009
0 views

Xml

Snakes mis use
17. 04. 2009
0 views

Snakes mis use

Php Web Development
21. 04. 2009
0 views

Php Web Development

Cricket Intro
21. 04. 2009
0 views

Cricket Intro

Cricket Umpiring and Rules
21. 04. 2009
0 views

Cricket Umpiring and Rules

Arm and Forearm
23. 04. 2009
0 views

Arm and Forearm

Elements Ions Isotopes
25. 04. 2009
0 views

Elements Ions Isotopes

Chemical Bond
25. 04. 2009
0 views

Chemical Bond

Discovering Newtons Laws
29. 04. 2009
0 views

Discovering Newtons Laws

FreeFall
29. 04. 2009
0 views

FreeFall

Digital photography
26. 04. 2009
0 views

Digital photography

Health Effects of Alcohol
26. 04. 2009
0 views

Health Effects of Alcohol

Poetry Terminology
27. 04. 2009
0 views

Poetry Terminology

Indian Force
05. 05. 2009
0 views

Indian Force

Machine Intelligence
14. 05. 2009
0 views

Machine Intelligence

Data Link Layer
16. 05. 2009
0 views

Data Link Layer

Database Development Cycle
15. 05. 2009
0 views

Database Development Cycle

Queue
15. 05. 2009
0 views

Queue

Presentaion Skills
23. 04. 2009
0 views

Presentaion Skills

Network Layers
23. 05. 2009
0 views

Network Layers

Narmada Dam, India
23. 05. 2009
0 views

Narmada Dam, India

User Datagram Protocol
24. 05. 2009
0 views

User Datagram Protocol

Linear Momentum
28. 05. 2009
0 views

Linear Momentum

Stack and Queue
04. 06. 2009
0 views

Stack and Queue

Information Management
19. 06. 2009
0 views

Information Management

Role of Senior Management
19. 06. 2009
0 views

Role of Senior Management

Wake Up India
07. 06. 2009
0 views

Wake Up India

Adobe Flex 3.0
13. 06. 2009
0 views

Adobe Flex 3.0

Adobe Flex Presentation
13. 06. 2009
0 views

Adobe Flex Presentation

Introduction to Adobe Flex
13. 06. 2009
0 views

Introduction to Adobe Flex

Adobe Flash Media Server
13. 06. 2009
0 views

Adobe Flash Media Server

Dreamweaver
13. 06. 2009
0 views

Dreamweaver

Adobe Flash
13. 06. 2009
0 views

Adobe Flash

Flash CS4 Professional
13. 06. 2009
0 views

Flash CS4 Professional

Adobe Flash Lite
13. 06. 2009
0 views

Adobe Flash Lite

Digital Camera
13. 06. 2009
0 views

Digital Camera

Mozilla_Firefox
15. 06. 2009
0 views

Mozilla_Firefox

Managerial Accounting
27. 06. 2009
0 views

Managerial Accounting

Accounting  Information  System
01. 07. 2009
0 views

Accounting Information System

RETAILING AND MARKETING
06. 07. 2009
0 views

RETAILING AND MARKETING

ACCOUNTING IN BUSINESS
05. 07. 2009
0 views

ACCOUNTING IN BUSINESS

STRATEGIC RETAIL MANAGEMENT
05. 07. 2009
0 views

STRATEGIC RETAIL MANAGEMENT

Reiki
01. 08. 2009
0 views

Reiki

Using Buttons in PowerPoint
26. 04. 2009
0 views

Using Buttons in PowerPoint

Nanotechnology  for  Students
21. 08. 2009
0 views

Nanotechnology for Students

NANOSCIENCE
25. 08. 2009
0 views

NANOSCIENCE

Fundamentals of Nanoscience
27. 08. 2009
0 views

Fundamentals of Nanoscience

Nanoscience in Nature
27. 08. 2009
0 views

Nanoscience in Nature

Applied Mechanics
04. 09. 2009
0 views

Applied Mechanics

Accounts Payable Training
27. 06. 2009
0 views

Accounts Payable Training