diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | .vscode/launch.json | 54 | ||||
| -rw-r--r-- | search.py | 31 |
3 files changed, 85 insertions, 1 deletions
@@ -145,3 +145,4 @@ cython_debug/ # VS Code files .vscode/* +!.vscode/launch.json diff --git a/.vscode/launch.json b/.vscode/launch.json new file mode 100644 index 0000000..10ed9ff --- /dev/null +++ b/.vscode/launch.json @@ -0,0 +1,54 @@ +{ + // Use IntelliSense to learn about possible attributes. + // Hover to view descriptions of existing attributes. + // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387 + "version": "0.2.0", + "configurations": [ + { + "name": "debug", + "type": "python", + "request": "launch", + "program": "pacman.py", + "args": [ + "--frameTime=0.01", + "--catchExceptions", + "--pacman=SearchAgent", + "--agentArgs=fn=${input:searchAlgorithm}", + "--layout=${input:mazeLayout}", + ] + }, + { + "name": "autograder", + "type": "python", + "request": "launch", + "program": "autograder.py", + } + ], + "inputs": [ + { + "id": "searchAlgorithm", + "type": "pickString", + "description": "Select the search algorithm", + "options": [ + "tinyMazeSearch", + "depthFirstSearch", + "breadthFirstSearch", + "uniformCostSearch" + ], + "default": "uniformCostSearch" + }, + { + "id": "mazeLayout", + "type": "pickString", + "description": "Select the maze layout", + "options": [ + "tinyMaze", + "mediumMaze", + "bigMaze", + "mediumScaryMaze", + "mediumDottedMaze" + ], + "default": "tinyMaze" + } + ] +}
\ No newline at end of file @@ -169,7 +169,36 @@ def breadthFirstSearch(problem): def uniformCostSearch(problem): """Search the node of least total cost first.""" "*** YOUR CODE HERE ***" - util.raiseNotDefined() + + # lambda to get the total cost of a node + cost = lambda node: problem.getCostOfActions(node[3]) + pq = util.PriorityQueueWithFunction(cost) + pq.push((problem.getStartState(), None, 0, [])) + visited = {} + + while not pq.isEmpty(): + node = pq.pop() + + # Add nextNode to visited list + visited[node[0]] = cost(node) + + # base case + if problem.isGoalState(node[0]): + return node[3] + + # Get all successors and push them into a priority queue based on cost + nextNodes = problem.getSuccessors(node[0]) + for nextNode in nextNodes: + # Append the node's path + nextNode's direction + nextNode = nextNode + (node[3] + [nextNode[1]],) + + # Check that nextNode has not been visited + if visited.has_key(nextNode[0]) and visited[nextNode[0]] < cost(nextNode): + continue + + # Push the child if it was not visited + pq.push(nextNode) + def nullHeuristic(state, problem=None): """ |