Scribd
Upload
11 views7 pages

CSC 411 Dynamic Programming Exam Questions

Uploaded by

Collins Ifeanyi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
11 views7 pages

CSC 411 Dynamic Programming Exam Questions

Uploaded by

Collins Ifeanyi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

EXAMINATION QUESTIONS FOR CSC 411

EXCEPT QUESTION 2 WHICH IS FOR TEST


1a. Explain the concept of (not exceeding three sentences for each).
(10mrks)
 Recursive Relationship
 State
 Stage
 Alternative
 Optimal Policy
1b. State Bellman’s Principle of Optimality in Dynamic Programming and
give a mathematical formulation of a Dynamic Programming problem.
(5mks)

TEST QUESTIONS
2. Define the term Dynamic Programming? (21/2marks)
b. State the Principle of Dynamic Programming and Describe the basic
features which characterize a dynamic programming. (5marks)
c. Give a mathematical formulation of a Dynamic Programming problem
(21/2marks)

3a. A market executive located in a City A decided to travel to City B. He/she


knew the distances of alternative routes from City A to B, and then
he/she tabulated all the data as given below.
The city of origin A is city 1 and the destination city, B, is city 10. Other
cities through which the salesperson will have to pass are numbered
from 2 – 9. Construct the Network map for the Salesperson given the
following data below whose distance is in kilometer and the cities
labelled City 1 to City 10.
(10 marks)

A 2 3 4 8 9
FROM 1 4 6 3 5 4 8
6 3 7
5 6 7 7 8 4
2 7 10 5 10 B
3 3 8 4 8 7
4 6 10 5 9 9
3b. Clearly distinguish between Forward and Backward Computational
Procedure in Dynamic Programming. 5marks
4a. A sales Manager is planning to a business tour from Wukari to Jalingo.
He intends to cover one town from each of the Company’s different
marketing zones on the route. The network below shows the three
intermediate stages and three possible choices of route at all but the last
cities. The travel time between the two cities inclusive of working time is
given below the arrows between cities. Which intermediate cities should
he visit to minimize the time required to go from A to H.
Find the shortest route. (15marks)
Q1. STAGE:
Stage can be defined as the point at which decisions are called
for. Each stage can be thought of having beginning and an end.
Dynamic Programming is broken into sub – problems and each
problem is called Stage.
The point at which decisions called for, are referred to as
stages.

STATE:
State can be define as the information available at each stage
indicates the, value of state variables, which link up two stages.
State can be define as the variable that links up two stages is
called State Variables.

ALTERNATIVE:
At every stage, there may be more than one choice to take
decision, which is known as alternative.

OPTIMAL POLICY:
A policy, which optimize the value of a criterion objective or
return function is called Optimal Policy. Decision at any stage is
not dependent on the previous history of the system.

RECURSIVE RELATIONSHIP:
It represents mathematical expression connecting the optimal
solution of the earlier stage and the return function from the
current stage.
Q2A DYNAMIC PROGRAMMING
Dynamic Programming is a mathematical technique that deals
with the optimization of multistage decision tree.
Richard Bellman developed this technique. The technique is
called Recursive Function.

Q2B THE CHARACTERISTICS OF DYNAMIC PROGRAMMING


 The problem can be divided into stages with a policy
decision required at each stage.
 Every stage consists of number of states.
 Decision at each stage converts the current state with
state associated with the next stage
 Each stage has set of variables known as state variables.
 The decision of one stage is independent of another
stage.
 To find optimum policy recursive equation is developed.
 The backward recursive approach is used for taking
decision from the last stage to next previous stage. This is
followed till final solution is obtained.

Q2C BELLMAN’S PRINCIPLE OF OPTIMALITY


States that;
“An optimal policy (set of decisions) has the
property that, whenever the initial state and initial
decisions are, the remaining decision must
constitute Optimal Policy with respect to the state
resulting from the first decision.”

MATHEMATICAL REPRESENTATION
Here:

( V(s_t)) is the value function, representing the


maximum
value that can be achieved starting from state
( s_t ).

( a_t ) is the action taken at time ( t ).

( R(s_t, a_t) ) is the immediate reward received after taking


action ( a_t ) in state ( s_t ).

( gamma ) is the discount factor, with


( 0 \leq \gamma \leq 1 ), which accounts for
the difference in importance between present
and future rewards.

( s_{t+1} ) is the state resulting from taking action ( a_t )


in state ( s_t ).

Q3A. The Constructed Network map for the Salesperson

7 4
10
8
5

3
4 3
6 8
4 7
3

6 8
10
5 4
Q3B. Clearly distinguish between Forward and Backward Computational
Procedure in Dynamic Programming.

Forward Computational Procedure in Dynamic Programming occurs


when the Dynamic Programming is solved using the recursive equation
starting from the first stage to last stage the computation involved is
called the Forward Computational Procedure.
While
Backward Computational Procedure in Dynamic Programming occurs
when the Dynamic Programming is solved using the recursive equation
starting from the last stage to first stage the computation involved is
called the Backward Computational Procedure.

Q4. SOLUTION TO QUESTION (4A).

STAGE 1
The Possible Alternatively is H.
The possible State Variables are nodes E F and G.
The recursive function is f1(x1) = d(x1, m1)

State Variable Alternative f1(x1) m1


x1 H
E 3 3 H
F 4 4 H
G 3 3 H
STAGE 2
The Possible Alternatives are E F G OUTPUT OF TABLE 1
The Possible State Variables are nodes B, C, and D. State Variable f1(x1)
The Recursive Function is x1
f2(x2) = d(x2, m2) + E 3
f1(x1=m2) F 4
G 3

State Variable Alternative m2 f2(x2) m2


x2 E F G
B 5+3=8 7 + 4 = 11 7 + 3 = 10 8 E
C 6+3=9 7 + 4 = 11 10 + 3 = 13 9 E
D 6+3=9 8 + 4 = 12 9 + 3 = 12 9 E

STAGE 3
The Possible Alternatives are B, C, D OUTPUT OF TABLE 2
The Possible State Variables is A. State Variable f2(x2)
The Recursive Function is x3
f3(x3) = d(x3, m3) + f2(x2=m3) B 8
C 9
D 9

State Variable Alternative m2 f3(x3) m3


x3 B C D
A 5 + 8 = 13 5 + 9 = 14 3 + 9 = 12 12 D

Therefore, the shortest path for this problem is 12

CONCLUSIVELY

3 6 3
A D E H = 12km, which is the shortest path.

the shortest path is from Node A – D – E – H

Common questions

Powered by AI

The principle of dynamic programming involves structuring a multistage decision process where decisions at each stage are made to achieve a global optimum. This involves the recursive function V(s_t) which represents the maximum value achievable from state s_t, with decisions (actions) and immediate rewards guiding the transitions to subsequent states, encapsulated with a discount factor to weigh the temporal value of decisions. The recursive nature leads to the establishment of Bellman's Principle of Optimality as a mathematical representation .

In dynamic programming, an optimal policy is independent of the system's previous history because the decision at each stage is based on the current state and the recursive relationships established, rather than past decisions. This allows for the optimization to be focused on future outcomes from present states without being constrained by previous environmental conditions or past actions, aligning with Bellman's Principle of Optimality .

Bellman's Principle of Optimality states that an optimal policy has the property whereby any initial decisions at any stage, the remaining decisions must constitute an optimal policy given the state resulting from the first decision. The mathematical formulation involves the value function V(s_t) that maximizes the value starting from state s_t, the action a_t taken, the immediate reward R(s_t, a_t), and the state s_{t+1} resulting from taking action a_t, with a discount factor gamma. This recursive formulation is crucial in the backward computation to solve dynamic programming problems .

Recursive relationships in dynamic programming connect the optimal solution of an earlier stage with the return function from the current stage. They are significant because they allow the problem to be broken down into smaller sub-problems (stages) that can be solved sequentially and independently, ensuring the decision at one stage is not dependent on previous histories, thus simplifying the optimization process .

State variables play a crucial role in linking stages in dynamic programming, representing the current status or condition at each stage. They help transition from one stage to another by capturing the requisite data that influences the subsequent decisions and stages, ensuring that decisions align with the specific conditions of each stage for optimal policy formulation .

In dynamic programming, a 'stage' refers to the point where a decision is required, marking the beginning and end of a sub-problem or step in the overall process. Each decision required at a stage determines the transition to the next stage, emphasizing the decomposition of the larger problem into sequential, manageable parts that ensures optimal decision-making throughout the process .

The process of constructing a network map in dynamic programming involves identifying the points (cities) as nodes and the routes as edges connecting them. Each edge is labeled with the distance between the cities. Using this framework, one can systematically identify and calculate the optimal travel path between origin and destination by weighing distances and applying the recursive relationships between stages (cities).

In dynamic programming, the forward computational procedure involves solving the recursive equation starting from the first stage to the last stage, progressing sequentially. In contrast, the backward computational procedure involves solving the recursive equation starting from the last stage to the first stage, which often results in easier computation for finding the optimal policy in multistage problems .

Key characteristics of dynamic programming include: the problem can be divided into stages with policy decisions at each stage; each stage has multiple states with state variables that indicate possible transitions; decisions at each stage convert the current state to the next stage; and the recursive equation developed for optimization solutions indicates independence among stages .

Alternatives at each stage in dynamic programming represent the various choices available that influence the transition to the next state. They determine the path of decisions, as selecting different alternatives can lead to different successive stages, thus affecting the total outcome. By exploring these alternatives, dynamic programming ensures the selection of the best choice aligning with the optimal policy to maximize objectives or minimize costs, depending on the problem .

You might also like