Guessing a String by Heuristic Greedy Search

Python 2.7 and above should be installed on your system. Anaconda is recommended.

Download simpleai.zip from and unzip it.

Create a file named guess_ greedy_heuristic.py, place it on the same folder of simpleai as shown in the below figure.

Use the following code in the file.

# guessing a given string by using heuristic greedy algorithm

import argparse

import simpleai.search as ss

def build_arg_parser():

parser = argparse.ArgumentParser(description='Creates the input string \

using the greedy algorithm')

parser.add_argument("--input-string", dest="input_string", required=True, help="Input string")

parser.add_argument("--initial-state", dest="initial_state", required=False, default='', help="Starting point for the search")

return parser

class MySolveProblem(ss.SearchProblem):

def set_target(self, target_string):

self.target_string = target_string

# Check the current state and take the right action

def actions(self, cur_state):

if len(cur_state) < len(self.target_string):

alphabets = 'abcdefghijklmnopqrstuvwxyz'

return list(alphabets + ' ' + alphabets.upper())

else:

return []

# Concatenate state and action to get the result

def result(self, cur_state, action):

return cur_state + action

# Check if goal has been achieved

def is_goal(self, cur_state):

return cur_state == self.target_string

# Define the heuristic that will be used

def heuristic(self, cur_state):

# Compare current string with target string

dist = sum([1 if cur_state[i] != self.target_string[i] else 0

for i in range(len(cur_state))])

# Difference between the lengths

diff = len(self.target_string) - len(cur_state)

#print(cur_state,dist)

return dist + diff

if __name__=='__main__':

args = build_arg_parser().parse_args()

# Initialize the object

problem = MySolveProblem()

# Set target string and initial state

problem.set_target(args.input_string)

problem.initial_state = args.initial_state

# Solve the problem

output = ss.greedy(problem)

print(' Target string:', args.input_string)

print(' Path to the solution:')

for item in output.path():

print(item)

1a) In this code, a class is created to contain the methods needed to solve the problem. What is the classs name? Hint: this class inherits another class provided in the simpleai library.

1b) Here we have to override a set of methods to suit our needs. The first method set_target is a custom method that we define to set the target string. Then, the actions is a method that comes with a SearchProblem and we have to override it. It is responsible for taking the right steps towards the goal. Please give the explanation of what the actions method has done?

Please indicate the file in which the class of SearchProblem is defined? Hint: Read __init__.py file.

1c) A method is used to compute the result by concatenating the current string and the action that needs to be take. This method also comes with a SearchProblem and we have to override it. Please figure out which the method is?

1d) The method is_goal is a part of the SearchProblem and it is used to check if we reach the goal. In the method heuristic is also a part of SearchProblem and overriding is needed. Our own heuristic is defined to solve the problem. Please explain what kind of heuristic method we adopt towards the goal?

1e) Change heuristic function by removing returned dist (ie. return diff only). Run the program and observe what has happened. Recall the content about heuristic method that we have learned in class and give the explanation?

2a) There is a solver in the program which uses the greedy algorithm. Which sentence in the code shows the solver?

2b) It seems that greedy() function is from the namespace of simpleai.search. Please indicate which python file contains greedy() function? Hint: read the guide file __init__.py

2c) In greedy() function, it has a comment that describes several methods in the class of SearchProblem are required. Please indicates what are the required methods for greedy() function?

2d) Among these required methods, please check if they are overridden in your python file guess_ greedy_heuristic.py? Which one(s) is/are not overridden? Why is/are they not overridden? Hint: read the source code of SearchProblem as well.

2e) Run the program with the input string computer science at Brockport. Paste your screenshot of the running results.