Zhang-m5
Luoben Zhang
11/22/2019
2. Matrix Representation
n <- 1000
d <- runif(n*n)
d[d < 0.80] <- NA
d <- matrix(d,nrow=n,ncol=n)
diag(d) <- NA # no self-loops
d[upper.tri(d)] = t(d)[upper.tri(d)]
AdjMatrix2List <- function (d) {
head<-c()
tail<-c()
weight<-c()
a<-0
for(i in 1:n) {
for(j in 1:n){
if(!is.na(d[i,j])){
a<-a+1
head[a]<-i
tail[a]<-j
weight[a]<-d[i,j]
}
}
}
b<-cbind(head,tail, weight)
}
ds <- AdjMatrix2List(d)str(d)## num [1:1000, 1:1000] NA 0.873 NA 0.946 0.912 ...str(ds)## num [1:200636, 1:3] 1 1 1 1 1 1 1 1 1 1 ...
## - attr(*, "dimnames")=List of 2
## ..$ : NULL
## ..$ : chr [1:3] "head" "tail" "weight"head(ds)## head tail weight
## [1,] 1 2 0.8731795
## [2,] 1 4 0.9459925
## [3,] 1 5 0.9115088
## [4,] 1 7 0.8882128
## [5,] 1 32 0.9788768
## [6,] 1 34 0.96788123. Euclidean Minimum Spanning Tree
3.1
n <- 50
x <- round(runif(n)*1000)
y <- round(runif(n)*1000)
#plot(x,y,pch=16)
q <- c()
for (i in 1:n){
for (j in 1:n){
q <- append(q, sqrt((x[j]-x[i])^2+(y[j]-y[i])^2))
}
}
matrix3 <- matrix(q, nrow=50)It is a complete graph. By definition, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. What we have done satisfies the definition.
3.2
p <- AdjMatrix2List(matrix3)
v <- c()
for (i in 1:nrow(p)){
if (p[i,1] != p[i,2]){
v <- append(v, p[i,2])
}
}
dimnames(v) <- NULL
v1 <- matrix(1:50, ncol =1)
v <- matrix(v, ncol = 49, byrow = TRUE)
ds <- cbind(v1,v)3.3
ds.mst <- msTreePrim(1:n, AdjMatrix2List(matrix3)) # nodes, arcs
str(ds.mst)## List of 4
## $ tree.nodes : num [1:50] 1 12 11 2 29 25 10 16 30 31 ...
## $ tree.arcs : num [1:49, 1:3] 1 1 12 2 29 25 11 16 30 30 ...
## ..- attr(*, "dimnames")=List of 2
## .. ..$ : NULL
## .. ..$ : chr [1:3] "ept1" "ept2" "weight"
## $ stages : num 49
## $ stages.arcs: num [1:49] 1 2 3 4 5 6 7 8 9 10 ...3.4
plot.mst <- function(arcList){
for (i in 1:nrow(arcList)){
segments(x0=x[arcList[i,1]], y0=y[arcList[i,1]], x1=x[arcList[i,2]], y1=y[arcList[i,2]])
}
}
plot(x,y,pch=16)
plot.mst(ds.mst$tree.arcs)
4. Hostile Agents
1. This is a graph optimization problem simply because we can visualize the problem. And furthermore, we should use minimum spanning tree(MST) to finally solve it after we visualize it.
2. We can create a adjacency matrix just like what we have done above, we create a n*n matrix, and each elements of this matrix represent the probability(Pij) that message passed between these agents will fall into hostile hands.
3. From my opinion, we should use Kruskal algorithm to slove this problem.
4. It takes O(ElgE) to run this algorithm. I think it is more efficient to use for this problem.
5. Project Scheduling
5.4 Earliest Start Times(ES)
s.labels <- c('a','b','c','d','e','f','g','h','i','j')
s.nodes <- c(90,15,5,20,21,25,14,28,30,45)
#s.nodes1 <- c('-90','-15','-5','-20','-21','-25','-14','-28','-30','-45')
n <- 13
d1 <- NA
d1 <- matrix(d1,nrow=n,ncol=n)
d1[1,2] <- -90; d1[1,9] <- -90; d1[1,6] <- -90;
d1[2,3] <- -15;
d1[3,7] = -5;
d1[7,4] = -14;
d1[4,10] =-20; d1[4,8]=-20;
d1[4,5] <- -20;
d1[9,10]=-30;
d1[6,7]= -25;
d1[10,11] = -45
d1[5,12] = -21
d1[8,13] = -28
diag(d1) <- NA
ak <- AdjMatrix2List(d1)
zlb <- getShortestPathTree(1:13,ak,algorithm = "Bellman-Ford", directed = TRUE)##
## Shortest path tree
## Algorithm: Bellman-Ford
## Stages: 12 | Time: 0.01
## ------------------------------
## head tail weight
## 1 2 -90
## 1 6 -90
## 1 9 -90
## 2 3 -15
## 4 5 -20
## 4 8 -20
## 4 10 -20
## 5 12 -21
## 6 7 -25
## 7 4 -14
## 8 13 -28
## 10 11 -45
## ------------------------------
## Total = -478
##
## Distances from source:
## ------------------------------
## source node distance
## 1 2 -90
## 1 3 -105
## 1 4 -129
## 1 5 -149
## 1 6 -90
## 1 7 -115
## 1 8 -149
## 1 9 -90
## 1 10 -149
## 1 11 -194
## 1 12 -170
## 1 13 -177
## ------------------------------
### 5.5
CT <- as.Date("2019-11-01")-min(zlb$distances)
print(paste("Earliest Overall Project Completion Time will be:", CT))## [1] "Earliest Overall Project Completion Time will be: 2020-05-13"5.6
90 days after will be the earliest finish date for A
90+15=105 days after will be the earliest finish date for B
105+5=110 days after will be the earliest finish date for C
129+20=149 days after will be the earliest finish date for D
149+21=170 days after will be the earliest finish date for E
90+25=115 days after will be the earliest finish date for F
115+14=129 days after will be the earliest finish date for G
149+28=177 days after will be the earliest finish date for H
90+30=120 days after will be the earliest finish date for I
149+45=194 days after will be the earliest finish date for J
EF <- c(90, 105, 110, 149, 170, 115, 129, 177, 120, 194)
n <- 11
d2 <- NA
d2 <- matrix(d2,nrow=n,ncol=n)
d2[11, 5] <- 0
d2[11,8] <- 0
d2[11,10] <- 0
d2[5,4] <- -21
d2[8,4] <- -28
d2[4,7] <- -20
d2[10,4] <- -45
d2[10,9] <- -45
d2[9,1] <- -30
d2[7,6] <- -14
d2[7,3] <- -14
d2[6,1] <- -25
d2[3,2] <- -5
d2[2,1] <- -15
diag(d2) <- NA
ak1 <- AdjMatrix2List(d2)
zlb1 <- getShortestPathTree(1:11,ak1,algorithm = "Bellman-Ford", source.node = 11, directed = TRUE)##
## Shortest path tree
## Algorithm: Bellman-Ford
## Stages: 10 | Time: 0
## ------------------------------
## head tail weight
## 3 2 -5
## 4 7 -20
## 6 1 -25
## 7 3 -14
## 7 6 -14
## 10 4 -45
## 10 9 -45
## 11 5 0
## 11 8 0
## 11 10 0
## ------------------------------
## Total = -168
##
## Distances from source:
## ------------------------------
## source node distance
## 11 1 -104
## 11 2 -84
## 11 3 -79
## 11 4 -45
## 11 5 0
## 11 6 -79
## 11 7 -65
## 11 8 0
## 11 9 -45
## 11 10 0
## ------------------------------
5.7
LF <- c(194 + zlb1$distances)
LF <- LF[1:10]90 days will be the latest finish times for A
110 days will be the latest finish times for B
115 days will be the latest finish times for C
149 days will be the latest finish times for D
194 days will be the latest finish times for E
115 days will be the latest finish times for F
129 days will be the latest finish times for G
194 days will be the latest finish times for H
149 days will be the latest finish times for I
194 days will be the latest finish times for J
5.8
LS <- LF - s.nodes0 days will be the latest start times for A
95 days will be the latest start times for B
110 days will be the latest start times for C
129 days will be the latest start times for D
173 days will be the latest start times for E
90 days will be the latest start times for F
115 days will be the latest start times for G
166 days will be the latest start times for H
119 days will be the latest start times for I
149 days will be the latest start times for J
5.9
slack <- LF - EF