Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import bisect
- import sys
- """
- 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)
- """
- 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(min, lambda a: a.path_cost))
- class BoxWorld (Problem):
- def __init__(self, initial):
- self.initial = initial
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- return self.successor(state)[action]
- def goal_test(self, state):
- if (state[1] == (2,3) or state[1] == (2,5) or state[1] == (2,7)) and (
- state[2] == (2,3) or state[2] == (2,5) or state[2] == (2,7)) and (
- state[3] == (2,3) or state[3] == (2,5) or state[3] == (2,7)):
- return True
- else:
- return False
- def moveFigureUp (self,figure):
- x = figure [0]
- y = figure [1]
- return (x-1,y)
- def moveFigureDown (self,figure):
- x = figure [0]
- y = figure [1]
- return (x+1,y)
- def moveFigureLeft (self,figure):
- x = figure [0]
- y = figure [1]
- return (x,y-1)
- def moveFigureRight (self,figure):
- x = figure [0]
- y = figure [1]
- return (x,y+1)
- def moveBoxUp (self,box):
- x = box [0]
- y = box [1]
- return (x-1,y)
- def moveBoxDown (self,box):
- x = box [0]
- y = box [1]
- return (x+1,y)
- def moveBoxLeft (self,box):
- x = box [0]
- y = box [1]
- return (x,y-1)
- def moveBoxRight (self,box):
- x = box [0]
- y = box [1]
- return (x,y+1)
- def isValid(self, covek, box1, box2, box3):
- if covek[0] < 0 or covek[0] > 7:
- return False
- if covek[1] < 0 or covek[1] > 9:
- return False
- if box1[0] == 0 or box1[0] == 7:
- return False
- if box1[1] == 0 or box1[1] == 9:
- return False
- if box2[0] == 0 or box2[0] == 7:
- return False
- if box2[1] == 0 or box2[1] == 9:
- return False
- if box3[0] == 0 or box3[0] == 7:
- return False
- if box3[1] == 0 or box3[1] == 9:
- return False
- if box1 == box2 or box1 == box3 or box2 == box3 or covek == box1 or covek == box2 or covek == box3:
- return False
- return True
- def successor(self, state):
- successors = dict ()
- figura = state[0]
- box1 = state[1]
- box2 = state[2]
- box3 = state[3]
- box1X = box1[0]
- box2X = box2[0]
- box3X = box3[0]
- box1Y = box1[1]
- box2Y = box2[1]
- box3Y = box3[1]
- covekX=figura[0]
- covekY=figura[1]
- if covekX - box1X == 1 and covekY == box1Y:
- newFigura = self.moveFigureUp(figura)
- newBox1 = self.moveBoxUp(box1)
- if (self.isValid(newFigura,newBox1,box2,box3)):
- successors ['GoreCK'] = (newFigura,newBox1,box2,box3)
- if box1X - covekX == 1 and covekY == box1Y:
- newFigura = self.moveFigureDown(figura)
- newBox1 = self.moveBoxDown(box1)
- if (self.isValid(newFigura, newBox1, box2, box3)):
- successors['DoluCK'] = (newFigura, newBox1, box2, box3)
- if covekY - box1Y == 1 and covekX == box1X:
- newFigura = self.moveFigureLeft(figura)
- newBox1 = self.moveBoxLeft(box1)
- if (self.isValid(newFigura, newBox1, box2, box3)):
- successors['LevoCK'] = (newFigura, newBox1, box2, box3)
- if box1Y - covekY == 1 and covekX == box1X:
- newFigura = self.moveFigureRight(figura)
- newBox1 = self.moveBoxRight(box1)
- if (self.isValid(newFigura, newBox1, box2, box3)):
- successors['DesnoCK'] = (newFigura, newBox1, box2, box3)
- if covekX - box2X == 1 and covekY == box2Y:
- newFigura = self.moveFigureUp(figura)
- newBox2 = self.moveBoxUp(box2)
- if (self.isValid(newFigura, box1, newBox2, box3)):
- successors['GoreCK'] = (newFigura, box1, newBox2, box3)
- if box2X - covekX == 1 and covekY == box2Y:
- newFigura = self.moveFigureDown(figura)
- newBox2 = self.moveBoxDown(box2)
- if (self.isValid(newFigura, box1, newBox2, box3)):
- successors['DoluCK'] = (newFigura, box1, newBox2, box3)
- if covekY - box2Y == 1 and covekX == box2X:
- newFigura = self.moveFigureLeft(figura)
- newBox2 = self.moveBoxLeft(box2)
- if (self.isValid(newFigura, box1, newBox2, box3)):
- successors['LevoCK'] = (newFigura, box1, newBox2, box3)
- if box2Y - covekY == 1 and covekX == box2X:
- newFigura = self.moveFigureRight(figura)
- newBox2 = self.moveBoxRight(box2)
- if (self.isValid(newFigura, box1, newBox2, box3)):
- successors['DesnoCK'] = (newFigura, box1, newBox2, box3)
- if covekX - box3X == 1 and covekY == box3Y:
- newFigura = self.moveFigureUp(figura)
- newBox3 = self.moveBoxUp(box3)
- if (self.isValid(newFigura, box1, box2, newBox3)):
- successors['GoreCK'] = (newFigura, box1, box2, newBox3)
- if box3X - covekX == 1 and covekY == box3Y:
- newFigura = self.moveFigureDown(figura)
- newBox3 = self.moveBoxDown(box3)
- if (self.isValid(newFigura, box1, box2, newBox3)):
- successors['DoluCK'] = (newFigura, box1, box2, newBox3)
- if covekY - box3Y == 1 and covekX == box3X:
- newFigura = self.moveFigureLeft(figura)
- newBox3 = self.moveBoxLeft(box3)
- if (self.isValid(newFigura, box1, box2, newBox3)):
- successors['LevoCK'] = (newFigura, box1, box2, newBox3)
- if box3Y - covekY == 1 and covekX == box3X:
- newFigura = self.moveFigureRight(figura)
- newBox3 = self.moveBoxRight(box3)
- if (self.isValid(newFigura, box1, box2, newBox3)):
- successors['DesnoCK'] = (newFigura, box1, box2, newBox3)
- newFigura = self.moveFigureUp(figura)
- if (self.isValid(figura,box1,box2,box3)):
- successors['GoreC'] = (newFigura, box1, box2, box3)
- newFigura = self.moveFigureDown(figura)
- if (self.isValid(figura, box1, box2, box3)):
- successors['DoluC'] = (newFigura, box1, box2, box3)
- newFigura = self.moveFigureLeft(figura)
- if (self.isValid(figura, box1, box2, box3)):
- successors['LevoC'] = (newFigura, box1, box2, box3)
- newFigura = self.moveFigureRight(figura)
- if (self.isValid(figura, box1, box2, box3)):
- successors['DesnoC'] = (newFigura, box1, box2, box3)
- return successors
- if __name__ == '__main__':
- man_row = int(input())
- man_column = int(input())
- b1_row = int(input())
- b1_column = int(input())
- b2_row = int(input())
- b2_column = int(input())
- b3_row = int(input())
- b3_column = int(input())
- Man = (man_row,man_column)
- Box1 = (b1_row,b1_column)
- Box2 = (b2_row,b2_column)
- Box3 = (b3_row,b3_column)
- Dot1 = (2,3)
- Dot2 = (2,5)
- Dot3 = (2,7)
- initalState = (Man,Box1,Box2,Box3,Dot1,Dot2,Dot3)
- # print (state[1])
- problem = BoxWorld (initalState)
- answer = uniform_cost_search(problem)
- print (answer.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement