Posted: November 1st, 2022

Project 2
Milestone1

Project 2
Milestone1

Algorithms :

Function temperature_schedule(alpha, k, T0):
1. Return value of temperature by (alpha * k * T0)

Function nearest_neighbour(k,previous_sol) :
1. If previous_sol is 0, then compute the previous_sol
a. Select one random path from G from source to sink vertex and compute the flow of sink vertex by calling value funciton and return the flow.
2. Else return previous_sol always

Function value(G):
1. Get the adjacency list of graph G
2. Initial total_flow to zero
3. Iterate over the connectivity of vertex ‘t’
4. If any vertex v is connected to vertex ‘t’ and direction is towards ‘t’
5. Then
total_flow += flow from vertex ‘v’ to vertex ‘t’
6. Return the total_flow

Function simulated_annealing():
1. Initialize the alpha to 0.98, T0 to 10000 , k to 1, previous_sol to 0.
2. Assign the random values from 4000 to 10000 to each edges of the graph G
3. Get previous_sol by calling nearest_neighbour function.
4. While loop until T(alpha,k,T0) > 1
a. Repeat:
i. Pick a path P from G from vertex ‘s’ to ‘t’ randomly.
ii. Change the value on the edges of path P, by doing 3000 randomly
b. until no violation for capacity.
c. Compute current_sol by calling value funciton on G for path p.
d. Get previous_sol by calling nearest_neighbour function
e. compute deltaE by current_sol – previous_sol
f. if deltaE is positive, then current_sol is saved as previous_sol
g. else generate random value between 0 to 1, and compute e^(delta/T) if random is greater, then save previous_sol as current_sol

Check Price Discount

Study Notes & Homework Samples: CHICANO HISTORY »Paper 1 (Cultural Site paper or oral history interview)