Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- import math
- import random
- import bisect
- from sys import maxsize as infinity
- """
- 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): Queue 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))
- """
- Informed graph search.
- """
- def memoize(fn, slot=None):
- """ Store the calculated value for any arguments list. If a
- slot is specified, store the result in that slot in the first
- argument. If slot is false, store the results in a dictionary.
- :param fn: given function
- :param slot: name of the attribute for saving the function results
- :return: modified function for storing the results
- """
- if slot:
- def memoized_fn(obj, *args):
- if hasattr(obj, slot):
- return getattr(obj, slot)
- else:
- val = fn(obj, *args)
- setattr(obj, slot, val)
- return val
- else:
- def memoized_fn(*args):
- if args not in memoized_fn.cache:
- memoized_fn.cache[args] = fn(*args)
- return memoized_fn.cache[args]
- memoized_fn.cache = {}
- return memoized_fn
- def best_first_graph_search(problem, f):
- """The idea of Best First Search is to use an evaluation function
- to decide which adjacent is most promising and then explore.
- :param problem: given problem
- :param f: given heuristic function
- :return: Node or None
- """
- f = memoize(f, 'f')
- node = Node(problem.initial)
- if problem.goal_test(node.state):
- return node
- frontier = PriorityQueue(min, f)
- frontier.append(node)
- explored = set()
- while frontier:
- node = frontier.pop()
- if problem.goal_test(node.state):
- return node
- explored.add(node.state)
- for child in node.expand(problem):
- if child.state not in explored and child not in frontier:
- frontier.append(child)
- elif child in frontier:
- incumbent = frontier[child]
- if f(child) < f(incumbent):
- del frontier[incumbent]
- frontier.append(child)
- return None
- def greedy_best_first_graph_search(problem, h=None):
- """ Greedy best-first search is implemented with f(n) = h(n).
- :param problem: given problem
- :param h: given heuristic function
- :return: Node or None
- """
- h = memoize(h or problem.h, 'h')
- return best_first_graph_search(problem, h)
- def astar_search(problem, h=None):
- """ A* search is best-first graph search where f(n) = g(n) + h(n).
- :param problem: given problem
- :param h: given heuristic function
- :return: Node or None
- """
- h = memoize(h or problem.h, 'h')
- return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
- def recursive_best_first_search(problem, h=None):
- """ Recursive best first search - limits recursion by
- keeping track of the f-value of the best alternative
- path from any ancestor node (one step look-ahead).
- :param problem: given problem
- :param h: given heuristic function
- :return: Node or None
- """
- h = memoize(h or problem.h, 'h')
- def RBFS(problem, node, flimit):
- if problem.goal_test(node.state):
- return node, 0 # (the second value is not important)
- successors = node.expand(problem)
- if len(successors) == 0:
- return None, infinity
- for s in successors:
- s.f = max(s.path_cost + h(s), node.f)
- while True:
- # Sort them according to the lowest f value
- successors.sort(key=lambda x: x.f)
- best = successors[0]
- if best.f > flimit:
- return None, best.f
- if len(successors) > 1:
- alternative = successors[1].f
- else:
- alternative = infinity
- result, best.f = RBFS(problem, best, min(flimit, alternative))
- if result is not None:
- return result, best.f
- node = Node(problem.initial)
- node.f = h(node)
- result, bestf = RBFS(problem, node, infinity)
- return result
- """
- Finite graph search.
- """
- def distance(a, b):
- """The distance between two (x, y) points."""
- return math.hypot((a[0] - b[0]), (a[1] - b[1]))
- class Graph:
- """A graph connects nodes (verticies) by edges (links). Each edge can also
- have a length associated with it. The constructor call is something like:
- g = Graph({'A': {'B': 1, 'C': 2})
- this makes a graph with 3 nodes, A, B, and C, with an edge of length 1 from
- A to B, and an edge of length 2 from A to C. You can also do:
- g = Graph({'A': {'B': 1, 'C': 2}, directed=False)
- This makes an undirected graph, so inverse links are also added. The graph
- stays undirected; if you add more links with g.connect('B', 'C', 3), then
- inverse link is also added. You can use g.nodes() to get a list of nodes,
- g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the
- length of the link from A to B. 'Lengths' can actually be any object at
- all, and nodes can be any hashable object."""
- def __init__(self, dictionary=None, directed=True):
- self.dict = dictionary or {}
- self.directed = directed
- if not directed:
- self.make_undirected()
- else:
- # add empty edges dictionary for those nodes that do not
- # have edges and are not included in the dictionary as keys
- nodes_no_edges = list({y for x in self.dict.values()
- for y in x if y not in self.dict})
- for node in nodes_no_edges:
- self.dict[node] = {}
- def make_undirected(self):
- """Make a digraph into an undirected graph by adding symmetric edges."""
- for a in list(self.dict.keys()):
- for (b, dist) in self.dict[a].items():
- self.connect1(b, a, dist)
- def connect(self, node_a, node_b, distance_val=1):
- """Add a link from node_a and node_b of given distance_val, and also add the inverse
- link if the graph is undirected."""
- self.connect1(node_a, node_b, distance_val)
- if not self.directed:
- self.connect1(node_b, node_a, distance_val)
- def connect1(self, node_a, node_b, distance_val):
- """Add a link from node_a to node_b of given distance_val, in one direction only."""
- self.dict.setdefault(node_a, {})[node_b] = distance_val
- def get(self, a, b=None):
- """Return a link distance or a dict of {node: distance} entries.
- .get(a,b) returns the distance or None;
- .get(a) returns a dict of {node: distance} entries, possibly {}."""
- links = self.dict.get(a)
- if b is None:
- return links
- else:
- return links.get(b)
- def nodes(self):
- """Return a list of nodes in the graph."""
- return list(self.dict.keys())
- def UndirectedGraph(dictionary=None):
- """Build a Graph where every edge (including future ones) goes both ways."""
- return Graph(dictionary=dictionary, directed=False)
- def RandomGraph(nodes=list(range(10)), min_links=2, width=400, height=300,
- curvature=lambda: random.uniform(1.1, 1.5)):
- """Construct a random graph, with the specified nodes, and random links.
- The nodes are laid out randomly on a (width x height) rectangle.
- Then each node is connected to the min_links nearest neighbors.
- Because inverse links are added, some nodes will have more connections.
- The distance between nodes is the hypotenuse times curvature(),
- where curvature() defaults to a random number between 1.1 and 1.5."""
- g = UndirectedGraph()
- g.locations = {}
- # Build the cities
- for node in nodes:
- g.locations[node] = (random.randrange(width), random.randrange(height))
- # Build roads from each city to at least min_links nearest neighbors.
- for i in range(min_links):
- for node in nodes:
- if len(g.get(node)) < min_links:
- here = g.locations[node]
- def distance_to_node(n):
- if n is node or g.get(node, n):
- return math.inf
- return distance(g.locations[n], here)
- neighbor = nodes.index(min(nodes, key=distance_to_node))
- d = distance(g.locations[neighbor], here) * curvature()
- g.connect(node, neighbor, int(d))
- return g
- class GraphProblem(Problem):
- """The problem of searching a graph from one node to another."""
- def __init__(self, initial, goal, graph):
- super().__init__(initial, goal)
- self.graph = graph
- def actions(self, state):
- """The actions at a graph node are just its neighbors."""
- return list(self.graph.get(state).keys())
- def result(self, state, action):
- """The result of going to a neighbor is just that neighbor."""
- return action
- def path_cost(self, c, state1, action, state2):
- return c + (self.graph.get(state1, state2) or math.inf)
- def h(self, node):
- """h function is straight-line distance from a node's state to goal."""
- locs = getattr(self.graph, 'locations', None)
- if locs:
- return int(distance(locs[node.state], locs[self.goal]))
- else:
- return math.inf
- def update_obs(position):
- x = position[0]
- y = position[1]
- n = position[2]
- if(y == 1 and n == -1) or (y == 6 and n == 1):
- n = n * (-1)
- y = y + n
- position = (x,y,n)
- return position
- class Explorer(Problem):
- def __init__(self, initial, goal):
- self.initial = initial
- self.goal = goal
- def successor(self, state):
- successors = dict()
- x = state[0]
- y = state[1]
- obs1 = (state[2],state[3],state[4])
- obs2 = (state[5],state[6],state[7])
- #Move obs
- obs1 = update_obs(obs1)
- obs2 = update_obs(obs2)
- obs = [(obs1[0],obs1[1]),(obs2[0],obs2[1])]
- #Right -> x+1,y until x=8
- if x < 8 and (x+1,y) not in obs:
- state_new = (x+1,y,obs1[0],obs1[1],obs1[2],obs2[0],obs2[1],obs2[2])
- successors['Right'] = state_new
- #Left -> x-1,y until x=1
- if x > 1 and (x-1,y) not in obs:
- state_new = (x-1,y,obs1[0],obs1[1],obs1[2],obs2[0],obs2[1],obs2[2])
- successors['Left'] = state_new
- #Up -> x,y+1 until y=6
- if y < 6 and (x,y+1) not in obs:
- state_new = (x,y+1,obs1[0],obs1[1],obs1[2],obs2[0],obs2[1],obs2[2])
- successors['Up'] = state_new
- #Down -> x,y-1 until x=1
- if y > 1 and (x,y-1) not in obs:
- state_new = (x,y-1,obs1[0],obs1[1],obs1[2],obs2[0],obs2[1],obs2[2])
- successors['Down'] = state_new
- return successors
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- def goal_test(self, state):
- position = (state[0],state[1])
- return position == self.goal
- man_x = int(input())
- man_y = int(input())
- house_x = int(input())
- house_y = int(input())
- initial = (man_x,man_y,3,6,-1,6,1,1)
- goal = (house_x,house_y)
- explorer = Explorer(initial,goal)
- result = breadth_first_graph_search(explorer).solution()
- print(result)
- solution = breadth_first_graph_search(explorer).solve()
- print(solution)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement