Question

R exercise

implement a greedy nearest-neighbour approach to find a suitable route for visiting all houses (pairs of coordinates generated).

The route should be as short as possible.

Starting at house 1, visit the house nearest to house 1 first. Then, each time move on to the nearest house not yet visited and, after visiting all houses, return to house 1.

Suppose house 1 is at point (0,1) .

Write a function called gp which will take the matrix of coordinates of the houses as argument and will return

the coordinates of the path found by the greedy algorithm.

( You can generate a set of coordinates of the houses using the function gen.h

gen.h=function(n=10) {
while (TRUE) {
r <- sqrt(runif(n))*0.9
phi <- runif(n) * 2 * pi
houses <- cbind(x=r*sin(phi), y=r*cos(phi))
if (min(dist(houses))>0.15)
return(houses)
}
}

houses <- gen.h ()

Answer 1

Below is the R Code for function gp.

gen.h=function(n=10) {
while (TRUE) {
r <- sqrt(runif(n))*0.9
phi <- runif(n) * 2 * pi
houses <- cbind(x=r*sin(phi), y=r*cos(phi))
if (min(dist(houses))>0.15)
return(houses)
}
}
houses <- gen.h ()

gp <- function(houses) {
house.visited <- c() # Initialize the house.visited and path vactor
path <- c()
for (i in 1:10) {
house.visited[i] <- 0 # Initializing that all houses are not visited
}
current.house <- 1 # Initialize the current house
house.visited[current.house] <- 1 # Initialize the current house visited
distance <- as.matrix(dist(houses, upper = TRUE)) # Calculate the distance of each houses from each other
path[1] <- current.house # Initialize the path
for (k in 1:9) {
min <- Inf # Initialize next minimum distance to infinity
for (i in 1:10) {
if (house.visited[i] == 0) { # House not visited
if (min > distance[i, current.house]) { # The current min distance is greater than the distance between i and current house
min <- distance[i, current.house] # New distance is the distance between i and current house
next.house <- i # Next house is the house i
}
}
}
current.house <- next.house # Next house will be current house in next iteration
path[k+1] <- current.house # Store the next house in the the path vector
house.visited[current.house] <- 1 # Make current house as visited
}
path.coordinates <- houses[path,] # Store the path corrdinates
path.coordinates
}