QuestionQuestion

Python Program exploring the connection between problem formulation and search strategies.
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 PreviewSolution 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 ast
import 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.

$67.50
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Python Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats