Question

Question 3 - Dynamic Programming 18 marks total a) Consider an acyclic network defined by a set of nodes N and a set of arcs A. We know the travel time for each arc and the value for visiting each node We wish to construct a maximum value path from a specified origin to a specified destination, subject to the constraint that the total travel time of the path is no more than a maximum duration Provide a dynamic programming formulation to solve this problem. You should use Bellman's equations and define data, stages, states, actions and the transition and value functions. [9 marks] b) At the beginning of the day a machine can be in one of two states - Good or Bad. Each morning it is possible to undertake maintenance on the machine, at a cost of $400. If the machine is Bad at the end of any day, we incur a cost of $300 If the machine is Good at the beginning of the day, it will be Good at the end of the day with probability 0.95 if it is maintained and it will be Good with probability 0.8 if it is not maintained If the machine is Bad at the beginning of the day, it will be Good with probability 0.9 if it is maintained and it will be Good with probability 0.1 if it is not maintained. Use stochastic dynamic programming to model this problem for a three day period, assuming the machine starts in the Good state. What strategy of maintenance is optimal and what is the expected cost of this strategy?

this is a dynamic programming problem

Answer 1

#include <bits/stdc++.h>
#include<iostream>
using namespace std;

// a structure to represent a weighted edge in graph
struct Edges
{
int src, dest, weight;
};

//weighted graph
struct Data
{
//these two represents vertex and edges
int V, E;

struct Edges* edge;
};

struct Data* createGraph(int V, int E)
{
struct Data* graph = new Data;
graph->V = V;
graph->E = E;
graph->edge = new Edges[E];
return graph;
}

void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
//Asyclic graph
void BellmanFord(struct Data* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];

for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;

for (int i = 1; i <= V-1; i++)
{
for (int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; i++)
{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
printf("Graph contains negative weight cycle");
}

printArr(dist, V);

return;
}

int main()
{

int V=5;//you can change the input as you want
int E=8;

struct Data* graph = createGraph(V, E);

// add edge 0-1 (or A-B in above figure)
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;

// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;

// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;

// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;

// add edge 1-4 (or A-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;

// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;

// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;

// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
//you can use the loop to manipulate more data example purpose only these are given
BellmanFord(graph, 0);

return 0;
}

CAUsers\senthilmurugan\Documents12.exe Vertex le 1 Distance from Source 0 2 4 Process returned 0 (0x0) Press any key to continue. execution time : 0.127 s X

B)

#include<iostream>

using namespace std;

int good()

{

static int n=0;

int total;

total=300+(0.95*0.8*n);

n++;

return total;

}

int bad()

{

static int n=0;

int total;

total=700+(0.9*0.1*n);

return total;

}

int main()

{

int years,goodMaintain,badMaintain;

cout<<"enter the number of years"<<endl;

cin>>years;

for(int i=0;i<3;i++)

{

goodMaintain= good();

badMaintain=bad();

}

cout<<"for good "<<goodMaintain;

cout<<"for bad:"<<badMaintain;

return 0;

}