program程序讲解 、辅导 Java/Python编程
Task 2 - Search Space
Congratulations! We can now encrypt and decrypt messages if we have the key (i.e. the sequence of letters to swap). However, what happens if we don’t have the key? Well, as the name of this assignment suggests, we’ll have to search for one! In this task, we’ll look at how we can represent our search space as a tree and we’ll also work on a program to generate child nodes for that tree. This will be very helpful when we come to implement our search algorithms later.
Before starting, let’s revise the key elements of a search problem from the lecture slides:
In our case, the initial state is the encrypted message. Can you work out what each of the other elements (i.e. goal state, operators and path cost function) should be?
The answers are—wait! Are you sure you want to read on? Thinking about these questions is a great exercise (and helpful for the exam 😊). If yes, the answers are as follows: 1) the goal state is the decoded message, 2) the operators are the letter swaps (e.g. A ↔ E), since these transform messages into other messages and 3) the path cost is the number of letter swaps (e.g. if we applied A ↔ E, then E ↔ B, that would have a cost of 2.
Now that we have formulated our search problem, we can start setting up tools to help us with the search. In this task, you will write a function to find all of the successors of a state in our search space, given a set of allowed letters to swap. The function should have two parameters:
1.The name of a text file containing the parent state
2.A string containing all letters that are allowed to be swapped. For example, “ABC” would mean A ↔ B, A ↔ C and B ↔ C are allowed, but nothing else. Note that we are adding this condition so we can make the state space smaller, which will help with debugging. This will also be useful when we come to decoding the secret message.
The function will return a string which includes the number of successor states, followed by a list of these states separated by lines. The successors should be generated by applying the allowed operators in alphabetical order. For example, all of the A swaps (e.g. A ↔ B, A ↔ C, A ↔ D… etc.) should come before the B swaps (e.g. B ↔ C, B ↔ D, B ↔ E etc.). Additionally, A ↔ B should come before A ↔ C., since B comes before C. There is no need to include repeats (e.g. we don’t need B ↔ A, since it is the same as A ↔ B), or operators that do nothing (e.g. A ↔ A always does nothing, and A ↔ B does nothing if the message doesn’t contain any A’s or B’s). Some examples are given :
Task 4 - DFS, BFS, IDS, UCS
Fantastic! We now have tools to help us generate children and to perform goal checks. In this task, you will now combine all your work so far to write a function to perform uninformed searches. It should take six inputs:
1.A character (d, b, i or u) specifying the algorithm (DFS, BFS, IDS and UCS, respectively)
2.The name of a text file containing a secret message
3.The name of a text file containing a list of words, in alphabetical order and each on a separate line, which will act as a dictionary of correct words
4.A threshold, t, specifying what percentage of words must be correct for this to count as a goal (given as an integer between 0 and 100).
5.A string containing the letters that are allowed to be swapped
6.A character (y or n) indicating whether to print the messages corresponding to the first 10 expanded nodes.
It should then perform DFS, BFS, IDS or UCS to search for a decryption to the given message, reusing your code from previous tasks if you would like to. Note that children should be generated in the same order as in Task 2, and you do not need to handle cycles. In the case of UCS, if two nodes have the same priority for expansion, you should expand the node that was added to the fringe first, first. Additionally, you should stop the search if 1000 nodes have been expanded without finding a solution.
The function should return a string. This string must contain the following information, in order:
1.The decrypted message, key for generating that message and the path cost, if a solution was found. If no solution was found, the program should print, "No solution found."
2.The number of nodes expanded during the search. Note that the start node counts as an expanded node and, in the case of IDS, the final expanded node count should be the sum of the expanded node counts on each iteration.
3.The maximum number of nodes in the fringe at the same time during the search
4.The maximum search depth reached. That is, the depth of the deepest expanded node. Note that the start node has a depth of 0, and its children have depths of 1.
5.(If indicated with y) the messages corresponding to the first 10 expanded nodes in the search. If less than 10 nodes were expanded, it should print all expanded nodes.
Some examples of function calls and results are given below.
Task 6 - Greedy, A*
In this final task, you should modify your solution to Task 4 to include the greedy and A* algorithms. The input and output should be in exactly the same format. The only difference is that the first input can now be d, b, i, u, g or a, where g indicates greedy search and a indicates A* search. Use the heuristic we developed in Task 5 for these informed search strategies.
Once you are finished, try running your greedy and A* searches with the following inputs to decrypt the secret message