Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import bisect
- """
- Defining a class for the problem structure that we will solve with a search.
- The Problem class is an abstract class from which we make inheritance to define the basic
- characteristics of every problem we want to solve
- """
- class Problem:
- def __init__(self, initial, goal=None):
- self.initial = initial
- self.goal = goal
- def successor(self, state):
- """Given a state, return a dictionary of {action : state} pairs reachable
- from this state. If there are many successors, consider an iterator
- that yields the successors one at a time, rather than building them
- all at once.
- :param state: given state
- :return: dictionary of {action : state} pairs reachable
- from this state
- :rtype: dict
- """
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible
- from that state
- :param state: given state
- :return: list of actions
- :rtype: list
- """
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the resulting state
- :param state: given state
- :param action: given action
- :return: resulting state
- """
- raise NotImplementedError
- def goal_test(self, state):
- """Return True if the state is a goal. The default method compares
- the state to self.goal, as specified in the constructor. Implement
- this method if checking against a single self.goal is not enough.
- :param state: given state
- :return: is the given state a goal state
- :rtype: bool
- """
- return state == self.goal
- def path_cost(self, c, state1, action, state2):
- """Return the cost of a solution path that arrives at state2 from state1
- via action, assuming cost c to get up to state1. If the problem is such
- that the path doesn't matter, this function will only look at state2.
- If the path does matter, it will consider c and maybe state1 and action.
- The default method costs 1 for every step in the path.
- :param c: cost of the path to get up to state1
- :param state1: given current state
- :param action: action that needs to be done
- :param state2: state to arrive to
- :return: cost of the path after executing the action
- :rtype: float
- """
- return c + 1
- def value(self):
- """For optimization problems, each state has a value.
- Hill-climbing and related algorithms try to maximize this value.
- :return: state value
- :rtype: float
- """
- raise NotImplementedError
- """
- Definition of the class for node structure of the search.
- The class Node is not inherited
- """
- class Node:
- def __init__(self, state, parent=None, action=None, path_cost=0):
- """Create node from the search tree, obtained from the parent by
- taking the action
- :param state: current state
- :param parent: parent state
- :param action: action
- :param path_cost: path cost
- """
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0 # search depth
- if parent:
- self.depth = parent.depth + 1
- def __repr__(self):
- return "<Node %s>" % (self.state,)
- def __lt__(self, node):
- return self.state < node.state
- def expand(self, problem):
- """List the nodes reachable in one step from this node.
- :param problem: given problem
- :return: list of available nodes in one step
- :rtype: list(Node)
- """
- return [self.child_node(problem, action)
- for action in problem.actions(self.state)]
- def child_node(self, problem, action):
- """Return a child node from this node
- :param problem: given problem
- :param action: given action
- :return: available node according to the given action
- :rtype: Node
- """
- next_state = problem.result(self.state, action)
- return Node(next_state, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next_state))
- def solution(self):
- """Return the sequence of actions to go from the root to this node.
- :return: sequence of actions
- :rtype: list
- """
- return [node.action for node in self.path()[1:]]
- def solve(self):
- """Return the sequence of states to go from the root to this node.
- :return: list of states
- :rtype: list
- """
- return [node.state for node in self.path()[0:]]
- def path(self):
- """Return a list of nodes forming the path from the root to this node.
- :return: list of states from the path
- :rtype: list(Node)
- """
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- result.reverse()
- return result
- """We want the queue of nodes at breadth_first_search or
- astar_search to not contain states-duplicates, so the nodes that
- contain the same condition we treat as the same. [Problem: this can
- not be desirable in other situations.]"""
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- """
- Definitions of helper structures for storing the list of generated, but not checked nodes
- """
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): Last In First Out Queue (stack).
- FIFOQueue(): First In First Out Queue.
- PriorityQueue(order, f): QQueue in sorted order (default min-first).
- """
- def __init__(self):
- raise NotImplementedError
- def append(self, item):
- """Adds the item into the queue
- :param item: given element
- :return: None
- """
- raise NotImplementedError
- def extend(self, items):
- """Adds the items into the queue
- :param items: given elements
- :return: None
- """
- raise NotImplementedError
- def pop(self):
- """Returns the first element of the queue
- :return: first element
- """
- raise NotImplementedError
- def __len__(self):
- """Returns the number of elements in the queue
- :return: number of elements in the queue
- :rtype: int
- """
- raise NotImplementedError
- def __contains__(self, item):
- """Check if the queue contains the element item
- :param item: given element
- :return: whether the queue contains the item
- :rtype: bool
- """
- raise NotImplementedError
- class Stack(Queue):
- """Last-In-First-Out Queue."""
- def __init__(self):
- self.data = []
- def append(self, item):
- self.data.append(item)
- def extend(self, items):
- self.data.extend(items)
- def pop(self):
- return self.data.pop()
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return item in self.data
- class FIFOQueue(Queue):
- """First-In-First-Out Queue."""
- def __init__(self):
- self.data = []
- def append(self, item):
- self.data.append(item)
- def extend(self, items):
- self.data.extend(items)
- def pop(self):
- return self.data.pop(0)
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return item in self.data
- class PriorityQueue(Queue):
- """A queue in which the minimum (or maximum) element is returned first
- (as determined by f and order). This structure is used in
- informed search"""
- def __init__(self, order=min, f=lambda x: x):
- """
- :param order: sorting function, if order is min, returns the element
- with minimal f (x); if the order is max, then returns the
- element with maximum f (x).
- :param f: function f(x)
- """
- assert order in [min, max]
- self.data = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort_right(self.data, (self.f(item), item))
- def extend(self, items):
- for item in items:
- bisect.insort_right(self.data, (self.f(item), item))
- def pop(self):
- if self.order == min:
- return self.data.pop(0)[1]
- return self.data.pop()[1]
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.data)
- def __getitem__(self, key):
- for _, item in self.data:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.data):
- if item == key:
- self.data.pop(i)
- # coding=utf-8
- import sys
- """
- Uninformed tree search.
- Within the tree we do not solve the loops.
- """
- def tree_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- :param problem: given problem
- :param fringe: empty queue
- :return: Node
- """
- fringe.append(Node(problem.initial))
- while fringe:
- node = fringe.pop()
- print(node.state)
- if problem.goal_test(node.state):
- return node
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_tree_search(problem):
- """Search the shallowest nodes in the search tree first.
- :param problem: given problem
- :return: Node
- """
- return tree_search(problem, FIFOQueue())
- def depth_first_tree_search(problem):
- """Search the deepest nodes in the search tree first.
- :param problem: given problem
- :return: Node
- """
- return tree_search(problem, Stack())
- """
- Uninformed graph search
- The main difference is that here we do not allow loops,
- i.e. repetition of states
- """
- def graph_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- If two paths reach a state, only use the best one.
- :param problem: given problem
- :param fringe: empty queue
- :return: Node
- """
- closed = set()
- fringe.append(Node(problem.initial))
- while fringe:
- node = fringe.pop()
- if problem.goal_test(node.state):
- return node
- if node.state not in closed:
- closed.add(node.state)
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_graph_search(problem):
- """Search the shallowest nodes in the search tree first.
- :param problem: given problem
- :return: Node
- """
- return graph_search(problem, FIFOQueue())
- def depth_first_graph_search(problem):
- """Search the deepest nodes in the search tree first.
- :param problem: given problem
- :return: Node
- """
- return graph_search(problem, Stack())
- def depth_limited_search(problem, limit=50):
- def recursive_dls(node, problem, limit):
- """Helper function for depth limited"""
- cutoff_occurred = False
- if problem.goal_test(node.state):
- return node
- elif node.depth == limit:
- return 'cutoff'
- else:
- for successor in node.expand(problem):
- result = recursive_dls(successor, problem, limit)
- if result == 'cutoff':
- cutoff_occurred = True
- elif result is not None:
- return result
- if cutoff_occurred:
- return 'cutoff'
- return None
- return recursive_dls(Node(problem.initial), problem, limit)
- def iterative_deepening_search(problem):
- for depth in range(sys.maxsize):
- result = depth_limited_search(problem, depth)
- if result is not 'cutoff':
- return result
- def uniform_cost_search(problem):
- """Search the nodes in the search tree with lowest cost first."""
- return graph_search(problem, PriorityQueue(lambda a, b:
- a.path_cost < b.path_cost))
- from enum import Enum
- # write class definitions after this comment line
- class Actions(Enum):
- RIGHT = 1
- LEFT = 2
- UP = 3
- DOWN = 4
- class ObstacleProblem(Problem):
- def __init__(self, initial, goal):
- super().__init__(initial, goal)
- self.initial = initial
- self.goal = goal
- def goal_test(self, state):
- g = self.goal
- (x, y) = state[0]
- return x == g[0] and y == g[1]
- def successor(self, state):
- successors = dict()
- move(Actions.RIGHT, state, successors)
- move(Actions.LEFT, state, successors)
- move(Actions.UP, state, successors)
- move(Actions.DOWN, state, successors)
- return successors
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- def value(self):
- pass
- def move(action, state, successors):
- x, y = state[0]
- o1 = state[1]
- o2 = state[2]
- o3 = state[3]
- o1_new = update_obstacle1(o1)
- o2_new = update_obstacle2(o2)
- o3_new = update_obstacle3(o3)
- if action == Actions.RIGHT:
- y = y + 1
- action_done = "Desno"
- elif action == Actions.LEFT:
- y = y - 1
- action_done = "Levo"
- elif action == Actions.UP:
- x = x - 1
- action_done = "Gore"
- elif action == Actions.DOWN:
- x = x + 1
- action_done = "Dolu"
- else:
- action_done = "Invalid"
- if is_valid(x, y, o1_new, o2_new, o3_new):
- new_man_pos = (x, y)
- new_state = (new_man_pos, o1_new, o2_new, o3_new)
- successors[action_done] = new_state
- def update_obstacle1(obstacle):
- x = obstacle[0]
- y = obstacle[1]
- direction = obstacle[2]
- if (y == 0 and direction == -1) or (y == 4 and direction == 1):
- direction *= -1
- y_new = y + direction
- new_pos = (x, y_new, direction)
- return new_pos
- def update_obstacle2(obstacle):
- x = obstacle[0]
- y = obstacle[1]
- direction = obstacle[2]
- if (x == 5 and direction == 1) or (x == 9 and direction == -1):
- direction *= -1
- x_new = x - direction
- y_new = y + direction
- new_pos = x_new, y_new, direction
- return new_pos
- def update_obstacle3(obstacle):
- x = obstacle[0]
- y = obstacle[1]
- direction = obstacle[2]
- if (x == 5 and direction == 1) or (x == 9 and direction == -1):
- direction *= -1
- x_new = x - direction
- new_pos = x_new, y, direction
- return new_pos
- def is_valid(x, y, o1, o2, o3):
- # Map check
- if x < 0 or y < 0 or x > 10 or y > 10:
- return False
- if y > 5 and x < 5:
- return False
- # Obstacle collision check
- if (x == o1[0] and y == o1[1]) or (x == o1[0] and (y == o1[1] + 1)):
- return False
- if (x == o2[0] and y == o2[1]) or (x == o2[0] + 1 and y == o2[1]) \
- or (x == o2[0] and y == o2[1] + 1) or (x == o2[0] + 1 and y == o2[1] + 1):
- return False
- if (x == o3[0] and y == o3[1]) or (x == o3[0] + 1 and y == o3[1]):
- return False
- return True
- if __name__ == '__main__':
- man_row = int(input())
- man_column = int(input())
- house_row = int(input())
- house_column = int(input())
- # continue the code for solving the problem after this comment line
- goal_state = (house_row, house_column)
- man = (man_row, man_column)
- obstacle1 = (2, 2, -1) # left
- obstacle2 = (7, 2, 1) # upward-right
- obstacle3 = (7, 8, -1) # downward
- initial_state = (man, obstacle1, obstacle2, obstacle3)
- solution_space = ObstacleProblem(initial_state, goal_state)
- answer = breadth_first_graph_search(solution_space)
- print(answer.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement