## Question

Program called “puzzlesolver.py”

The program should take two mandatory input arguments. The first argument is a configuration file for the problem your program has to solve (see the next section for more information). The second argument is a keyword that specifies which search algorithm to use to solve the problem: bfs, unicost, greedy, iddfs and Astar (with the exception of the iddfs, assume “graph-search”).

Your program should solve the input problem using the specified search algorithm and strategy. Upon completion, it should output the following information:

• The solution path (or “No solution” if nothing was found): print one state per line.

• Time: expressed in terms of the total number of nodes created.

• Space: expressed as the maximum number of nodes kept in memory (the biggest size that the frontier list grew to) as well as the maximum number of states stored on the explored list. Please report these as two separate numbers.

• Cost: the final cost of the specified path or configuration.

An important element of this assignment is to separate the problem specific parts from the generic search algorithm part. Make sure that your implementation of the search does not hard code in any problem specific details. For this assignment, your program will be working with three problems: the wireless sensor monitoring problem and the data aggregation problem. And one more to be revealed a week later. If you’ve kept the problem/search abstraction clean, when you get the new problem, you ought to be able to just code up the functions relevant to setting up that problem as a state space search (e.g., get_successor_states, and goal_test, etc.)

Wireless sensor monitoring

You are given a set of sensors and a set of targets, we want the sensors to monitor the targets for the longest time possible. Each sensor runs on a battery, a sensor loses power with a rate dependent on the distance between sensor and the target it is monitoring. We need to maximize the time of monitoring all the targets (the time before the first target gets out monitoring range) by minimizing the power consumption of all sensors. Two sensors can monitor one target so that if one is dead the other can still continue, that means the target is still monitored. We will use the configuration file to specify the particular instance of the problem. It has the following format:

• Line 1 is a keyword (monitor) that tells you this is the monitoring problem

• Line 2 is a list of the sensors IDs, location and power to start with; e.g., [(“S_1”,1,1,100),(” S_2”,10,5,88),(”S_3”,3,4,120), …..]

• Line 3 is a list of the target IDs and locations; e.g., [(“T_1”,0,0),(”T_2”,2,3),(”T_3”,1, 5)]

• Power loss function is, Pt = P(t-1) - Euclidian distance between target and sensor. You may assume that we will not stress test with bad inputs like negative power or impossible states.

Data Aggregation Problem

For this problem, we will read in a graph representation of nodes and connections between them are undirected edges with time delay. We need to find the node to start from and the path so that we can visit all nodes and aggregate the data within these nodes with minimum time delay. Here is the format of the input configuration file:

• Line 1 is a keyword (aggregation) that tells you that this is the data aggregation problem.

• Line 2 is a list of the node IDs and locations of the nodes; e.g., [(“N_1”,1,1),(”N_2”,2,3),(”N_3”,1, 5)]

• Each of the following lines specifies a connection between two nodes and the time delay between the two nodes; e.g.,: (“N_1”, “N_2”, 4) specifies that it the time delay between N_1 to N_2 is 4 or vice versa. You may assume that we will not stress test with bad inputs like connections with negative or zero cost. We may try a large graph with this problem, however.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import astimport sys

file = 'aggregation.config'

algorithm = 'Astar'

if len(sys.argv) > 1:

file = sys.argv[1]

if len(sys.argv) > 2:

algorithm = sys.argv[2]

'''

Graph Superclass

'''

class Graph:

# BFS Search Algorithm

def bfs(self, source):

S = [source]

Q = [source]

result = []

space = 1

visited = 0

while len(Q) != 0:

visited += 1

space = max(space, len(Q))

# BFS -- traverse first visited node

current = Q.pop(0)

result.append(current)

for edge in self.getEdges(current):

other = edge[0]

if other not in S:

S.append(other)

Q.append(other)

time = len(S)

cost = self.cost(result)

return result, time, space, visited, cost

# Unicost Search Algorithm

def unicost(self, source):

S = [source]

Q = [(source, 0)]

result = []

edges = self.getEdges(source)

space = 1

visited = 0

while len(Q) != 0:

visited += 1

space = max(space, len(Q))

Q = sorted(Q, key=lambda x: x[1])

# Unicost -- traverse first node

current = Q.pop(0)[0]

result.append(current)

for edge in self.getEdges(current):

other = edge[0]

if other not in S:

S.append(other)

# Assign every node the same cost

Q.append((other, 1))

time = len(S)

cost = self.cost(result)

return result, time, space, visited, cost

# Greedy Search Algorithm

def greedy(self, source):

S = [source]

Q = [(source, 0)]

result = []

edges = self.getEdges(source)

space = 1

visited = 0

while len(Q) != 0:

visited += 1

space = max(space, len(Q))

Q = sorted(Q, key=lambda x: x[1])

# Greedy -- traverse best node

current = Q.pop(0)[0]

result.append(current)

for edge in self.getEdges(current):

other = edge[0]

weight = edge[1]

if other not in S:

S.append(other)

Q.append((other, weight))

time = len(S)

cost = self.cost(result)

return result, time, space, visited, cost

# IDDFS Search Algorithm

def iddfs(self, source):

S = [source...

By purchasing this solution you'll be able to access the following files:

Solution.zip.