Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- **********Patuvanje niz germ************
- # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
- # ______________________________________________________________________________________________
- # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
- import sys
- import bisect
- infinity = float('inf') # sistemski definirana vrednost za beskonecnost
- # ______________________________________________________________________________________________
- # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): A Last In First Out Queue.
- FIFOQueue(): A First In First Out Queue.
- PriorityQueue(order, f): Queue in sorted order (default min-first).
- Each type supports the following methods and functions:
- q.append(item) -- add an item to the queue
- q.extend(items) -- equivalent to: for item in items: q.append(item)
- q.pop() -- return the top item from the queue
- len(q) -- number of items in q (also q.__len())
- item in q -- does q contain item?
- Note that isinstance(Stack(), Queue) is false, because we implement stacks
- as lists. If Python ever gets interfaces, Queue will be an interface."""
- def __init__(self):
- raise NotImplementedError
- def extend(self, items):
- for item in items:
- self.append(item)
- def Stack():
- """A Last-In-First-Out Queue."""
- return []
- class FIFOQueue(Queue):
- """A First-In-First-Out Queue."""
- def __init__(self):
- self.A = []
- self.start = 0
- def append(self, item):
- self.A.append(item)
- def __len__(self):
- return len(self.A) - self.start
- def extend(self, items):
- self.A.extend(items)
- def pop(self):
- e = self.A[self.start]
- self.start += 1
- if self.start > 5 and self.start > len(self.A) / 2:
- self.A = self.A[self.start:]
- self.start = 0
- return e
- def __contains__(self, item):
- return item in self.A[self.start:]
- class PriorityQueue(Queue):
- """A queue in which the minimum (or maximum) element (as determined by f and
- order) is returned first. If order is min, the item with minimum f(x) is
- returned first; if order is max, then it is the item with maximum f(x).
- Also supports dict-like lookup. This structure will be most useful in informed searches"""
- def __init__(self, order=min, f=lambda x: x):
- self.A = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort(self.A, (self.f(item), item))
- def __len__(self):
- return len(self.A)
- def pop(self):
- if self.order == min:
- return self.A.pop(0)[1]
- else:
- return self.A.pop()[1]
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.A)
- def __getitem__(self, key):
- for _, item in self.A:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.A):
- if item == key:
- self.A.pop(i)
- # ______________________________________________________________________________________________
- # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
- # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
- # na sekoj eden problem sto sakame da go resime
- class Problem:
- """The abstract class for a formal problem. You should subclass this and
- implement the method successor, and possibly __init__, goal_test, and
- path_cost. Then you will create instances of your subclass and solve them
- with the various search functions."""
- def __init__(self, initial, goal=None):
- """The constructor specifies the initial state, and possibly a goal
- state, if there is a unique goal. Your subclass's constructor can add
- other arguments."""
- 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. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible from that state"""
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the 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."""
- 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."""
- return c + 1
- def value(self):
- """For optimization problems, each state has a value. Hill-climbing
- and related algorithms try to maximize this value."""
- raise NotImplementedError
- # ______________________________________________________________________________
- # Definiranje na klasa za strukturata na jazel od prebaruvanje
- # Klasata Node ne se nasleduva
- class Node:
- """A node in a search tree. Contains a pointer to the parent (the node
- that this is a successor of) and to the actual state for this node. Note
- that if a state is arrived at by two paths, then there are two nodes with
- the same state. Also includes the action that got us to this state, and
- the total path_cost (also known as g) to reach the node. Other functions
- may add an f and h value; see best_first_graph_search and astar_search for
- an explanation of how the f and h values are handled. You will not need to
- subclass this class."""
- def __init__(self, state, parent=None, action=None, path_cost=0):
- "Create a search tree Node, derived from a parent by an action."
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0
- 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."
- 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"
- next = problem.result(self.state, action)
- return Node(next, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next))
- def solution(self):
- "Return the sequence of actions to go from the root to this node."
- 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 [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."
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- return list(reversed(result))
- # We want for a queue of nodes in breadth_first_search or
- # astar_search to have no duplicated states, so we treat nodes
- # with the same state as equal. [Problem: this may not be what you
- # want in other contexts.]
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- # ________________________________________________________________________________________________________
- #Neinformirano prebaruvanje vo ramki na drvo
- #Vo ramki na drvoto ne razresuvame jamki
- def tree_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- The argument fringe should be an empty queue."""
- fringe.append(Node(problem.initial))
- while fringe:
- node = fringe.pop()
- 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."
- return tree_search(problem, FIFOQueue())
- def depth_first_tree_search(problem):
- "Search the deepest nodes in the search tree first."
- return tree_search(problem, Stack())
- # ________________________________________________________________________________________________________
- #Neinformirano prebaruvanje vo ramki na graf
- #Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi
- def graph_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- The argument fringe should be an empty queue.
- If two paths reach a state, only use the best one."""
- closed = {}
- 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[node.state] = True
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_graph_search(problem):
- "Search the shallowest nodes in the search tree first."
- return graph_search(problem, FIFOQueue())
- def depth_first_graph_search(problem):
- "Search the deepest nodes in the search tree first."
- return graph_search(problem, Stack())
- 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))
- def depth_limited_search(problem, limit=50):
- "depth first search with limited depth"
- 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 != None:
- return result
- if cutoff_occurred:
- return 'cutoff'
- else:
- return None
- # Body of depth_limited_search:
- return recursive_dls(Node(problem.initial), problem, limit)
- def iterative_deepening_search(problem):
- for depth in xrange(sys.maxint):
- result = depth_limited_search(problem, depth)
- if result is not 'cutoff':
- return result
- # ________________________________________________________________________________________________________
- #Pomosna funkcija za informirani prebaruvanja
- #So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
- def memoize(fn, slot=None):
- """Memoize fn: make it remember the computed value for any argument list.
- If slot is specified, store result in that slot of first argument.
- If slot is false, store results in a dictionary."""
- 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 not memoized_fn.cache.has_key(args):
- memoized_fn.cache[args] = fn(*args)
- return memoized_fn.cache[args]
- memoized_fn.cache = {}
- return memoized_fn
- # ________________________________________________________________________________________________________
- #Informirano prebaruvanje vo ramki na graf
- def best_first_graph_search(problem, f):
- """Search the nodes with the lowest f scores first.
- You specify the function f(node) that you want to minimize; for example,
- if f is a heuristic estimate to the goal, then we have greedy best
- first search; if f is node.depth then we have breadth-first search.
- There is a subtlety: the line "f = memoize(f, 'f')" means that the f
- values will be cached on the nodes as they are computed. So after doing
- a best first search you can examine the f values of the path returned."""
- 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 accomplished by specifying f(n) = h(n)"
- 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 with f(n) = g(n)+h(n)."
- h = memoize(h or problem.h, 'h')
- return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
- # ________________________________________________________________________________________________________
- #Dopolnitelni prebaruvanja
- #Recursive_best_first_search e implementiran
- #Kako zadaca za studentite da gi implementiraat SMA* i IDA*
- def recursive_best_first_search(problem, h=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 immaterial)
- 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:
- # Order by 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
- # Graphs and Graph Problems
- import math
- 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, dict=None, directed=True):
- self.dict = dict or {}
- self.directed = directed
- if not directed:
- self.make_undirected()
- 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, A, B, distance=1):
- """Add a link from A and B of given distance, and also add the inverse
- link if the graph is undirected."""
- self.connect1(A, B, distance)
- if not self.directed:
- self.connect1(B, A, distance)
- def connect1(self, A, B, distance):
- """Add a link from A to B of given distance, in one direction only."""
- self.dict.setdefault(A, {})[B] = distance
- 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.setdefault(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(dict=None):
- """Build a Graph where every edge (including future ones) goes both ways."""
- return Graph(dict=dict, 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 infinity
- return distance(g.locations[n], here)
- neighbor = argmin(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):
- Problem.__init__(self, initial, goal)
- self.graph = graph
- def actions(self, A):
- """The actions at a graph node are just its neighbors."""
- return list(self.graph.get(A).keys())
- def result(self, state, action):
- """The result of going to a neighbor is just that neighbor."""
- return action
- def path_cost(self, cost_so_far, A, action, B):
- return cost_so_far + (self.graph.get(A, B) or infinity)
- 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 0
- Pocetok = input()
- Kraj = input()
- germania_map=UndirectedGraph(dict(
- Frankfurt=dict(Mannheim=85, Wurzburg=217, Kassel=173),
- Mannheim=dict(Karlsruhe=80),
- Wurzburg=dict(Erfurt=186, Nurnberg=103),
- Nurnberg=dict(Stuttgart=183, Munchen=167),
- Kassel=dict(Munchen=502),
- Karlsruhe=dict(Augsburg=250),
- Augsburg=dict(Munchen=84)))
- germania_problem=GraphProblem(Pocetok,Kraj,germania_map)
- answer=astar_search(germania_problem)
- print answer.path_cost
- ****graf*******
- # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
- # ______________________________________________________________________________________________
- # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
- import sys
- import bisect
- infinity = float('inf') # sistemski definirana vrednost za beskonecnost
- # ______________________________________________________________________________________________
- # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): A Last In First Out Queue.
- FIFOQueue(): A First In First Out Queue.
- PriorityQueue(order, f): Queue in sorted order (default min-first).
- Each type supports the following methods and functions:
- q.append(item) -- add an item to the queue
- q.extend(items) -- equivalent to: for item in items: q.append(item)
- q.pop() -- return the top item from the queue
- len(q) -- number of items in q (also q.__len())
- item in q -- does q contain item?
- Note that isinstance(Stack(), Queue) is false, because we implement stacks
- as lists. If Python ever gets interfaces, Queue will be an interface."""
- def __init__(self):
- raise NotImplementedError
- def extend(self, items):
- for item in items:
- self.append(item)
- def Stack():
- """A Last-In-First-Out Queue."""
- return []
- class FIFOQueue(Queue):
- """A First-In-First-Out Queue."""
- def __init__(self):
- self.A = []
- self.start = 0
- def append(self, item):
- self.A.append(item)
- def __len__(self):
- return len(self.A) - self.start
- def extend(self, items):
- self.A.extend(items)
- def pop(self):
- e = self.A[self.start]
- self.start += 1
- if self.start > 5 and self.start > len(self.A) / 2:
- self.A = self.A[self.start:]
- self.start = 0
- return e
- def __contains__(self, item):
- return item in self.A[self.start:]
- class PriorityQueue(Queue):
- """A queue in which the minimum (or maximum) element (as determined by f and
- order) is returned first. If order is min, the item with minimum f(x) is
- returned first; if order is max, then it is the item with maximum f(x).
- Also supports dict-like lookup. This structure will be most useful in informed searches"""
- def __init__(self, order=min, f=lambda x: x):
- self.A = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort(self.A, (self.f(item), item))
- def __len__(self):
- return len(self.A)
- def pop(self):
- if self.order == min:
- return self.A.pop(0)[1]
- else:
- return self.A.pop()[1]
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.A)
- def __getitem__(self, key):
- for _, item in self.A:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.A):
- if item == key:
- self.A.pop(i)
- # ______________________________________________________________________________________________
- # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
- # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
- # na sekoj eden problem sto sakame da go resime
- class Problem:
- """The abstract class for a formal problem. You should subclass this and
- implement the method successor, and possibly __init__, goal_test, and
- path_cost. Then you will create instances of your subclass and solve them
- with the various search functions."""
- def __init__(self, initial, goal=None):
- """The constructor specifies the initial state, and possibly a goal
- state, if there is a unique goal. Your subclass's constructor can add
- other arguments."""
- 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. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible from that state"""
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the 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."""
- 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."""
- return c + 1
- def value(self):
- """For optimization problems, each state has a value. Hill-climbing
- and related algorithms try to maximize this value."""
- raise NotImplementedError
- # ______________________________________________________________________________
- # Definiranje na klasa za strukturata na jazel od prebaruvanje
- # Klasata Node ne se nasleduva
- class Node:
- """A node in a search tree. Contains a pointer to the parent (the node
- that this is a successor of) and to the actual state for this node. Note
- that if a state is arrived at by two paths, then there are two nodes with
- the same state. Also includes the action that got us to this state, and
- the total path_cost (also known as g) to reach the node. Other functions
- may add an f and h value; see best_first_graph_search and astar_search for
- an explanation of how the f and h values are handled. You will not need to
- subclass this class."""
- def __init__(self, state, parent=None, action=None, path_cost=0):
- "Create a search tree Node, derived from a parent by an action."
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0
- 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."
- 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"
- next = problem.result(self.state, action)
- return Node(next, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next))
- def solution(self):
- "Return the sequence of actions to go from the root to this node."
- 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 [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."
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- return list(reversed(result))
- # We want for a queue of nodes in breadth_first_search or
- # astar_search to have no duplicated states, so we treat nodes
- # with the same state as equal. [Problem: this may not be what you
- # want in other contexts.]
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- # ________________________________________________________________________________________________________
- #Neinformirano prebaruvanje vo ramki na drvo
- #Vo ramki na drvoto ne razresuvame jamki
- def tree_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- The argument fringe should be an empty queue."""
- fringe.append(Node(problem.initial))
- while fringe:
- node = fringe.pop()
- 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."
- return tree_search(problem, FIFOQueue())
- def depth_first_tree_search(problem):
- "Search the deepest nodes in the search tree first."
- return tree_search(problem, Stack())
- # ________________________________________________________________________________________________________
- #Neinformirano prebaruvanje vo ramki na graf
- #Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi
- def graph_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- The argument fringe should be an empty queue.
- If two paths reach a state, only use the best one."""
- closed = {}
- 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[node.state] = True
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_graph_search(problem):
- "Search the shallowest nodes in the search tree first."
- return graph_search(problem, FIFOQueue())
- def depth_first_graph_search(problem):
- "Search the deepest nodes in the search tree first."
- return graph_search(problem, Stack())
- 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))
- def depth_limited_search(problem, limit=50):
- "depth first search with limited depth"
- 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 != None:
- return result
- if cutoff_occurred:
- return 'cutoff'
- else:
- return None
- # Body of depth_limited_search:
- return recursive_dls(Node(problem.initial), problem, limit)
- def iterative_deepening_search(problem):
- for depth in xrange(sys.maxint):
- result = depth_limited_search(problem, depth)
- if result is not 'cutoff':
- return result
- # ________________________________________________________________________________________________________
- #Pomosna funkcija za informirani prebaruvanja
- #So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
- def memoize(fn, slot=None):
- """Memoize fn: make it remember the computed value for any argument list.
- If slot is specified, store result in that slot of first argument.
- If slot is false, store results in a dictionary."""
- 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 not memoized_fn.cache.has_key(args):
- memoized_fn.cache[args] = fn(*args)
- return memoized_fn.cache[args]
- memoized_fn.cache = {}
- return memoized_fn
- # ________________________________________________________________________________________________________
- #Informirano prebaruvanje vo ramki na graf
- def best_first_graph_search(problem, f):
- """Search the nodes with the lowest f scores first.
- You specify the function f(node) that you want to minimize; for example,
- if f is a heuristic estimate to the goal, then we have greedy best
- first search; if f is node.depth then we have breadth-first search.
- There is a subtlety: the line "f = memoize(f, 'f')" means that the f
- values will be cached on the nodes as they are computed. So after doing
- a best first search you can examine the f values of the path returned."""
- 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 accomplished by specifying f(n) = h(n)"
- 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 with f(n) = g(n)+h(n)."
- h = memoize(h or problem.h, 'h')
- return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
- # ________________________________________________________________________________________________________
- #Dopolnitelni prebaruvanja
- #Recursive_best_first_search e implementiran
- #Kako zadaca za studentite da gi implementiraat SMA* i IDA*
- def recursive_best_first_search(problem, h=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 immaterial)
- 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:
- # Order by 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
- # Graphs and Graph Problems
- import math
- 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, dict=None, directed=True):
- self.dict = dict or {}
- self.directed = directed
- if not directed:
- self.make_undirected()
- 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, A, B, distance=1):
- """Add a link from A and B of given distance, and also add the inverse
- link if the graph is undirected."""
- self.connect1(A, B, distance)
- if not self.directed:
- self.connect1(B, A, distance)
- def connect1(self, A, B, distance):
- """Add a link from A to B of given distance, in one direction only."""
- self.dict.setdefault(A, {})[B] = distance
- 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.setdefault(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(dict=None):
- """Build a Graph where every edge (including future ones) goes both ways."""
- return Graph(dict=dict, 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 infinity
- return distance(g.locations[n], here)
- neighbor = argmin(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):
- Problem.__init__(self, initial, goal)
- self.graph = graph
- def actions(self, A):
- """The actions at a graph node are just its neighbors."""
- return list(self.graph.get(A).keys())
- def result(self, state, action):
- """The result of going to a neighbor is just that neighbor."""
- return action
- def path_cost(self, cost_so_far, A, action, B):
- return cost_so_far + (self.graph.get(A, B) or infinity)
- 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 infinity
- Pocetok = input()
- Stanica1 = input()
- Stanica2 = input()
- Kraj = input()
- ABdistance=distance((2,1),(2,4))
- BIdistance=distance((2,4),(8,5))
- BCdistance=distance((2,4),(2,10))
- HIdistance=distance((8,1),(8,5))
- IJdistance=distance((8,5),(8,8))
- FCdistance=distance((5,9),(2,10))
- GCdistance=distance((4,11),(2,10))
- CDdistance=distance((2,10),(2,15))
- FGdistance=distance((5,9),(4,11))
- FJdistance=distance((5,9),(8,8))
- KGdistance=distance((8,13),(4,11))
- LKdistance=distance((8,15),(8,13))
- DEdistance=distance((2,15),(2,19))
- DLdistance=distance((2,15),(8,15))
- LMdistance=distance((8,15),(8,19))
- graph = UndirectedGraph({
- "B": {"A": ABdistance, "I": BIdistance, "C": BCdistance},
- "I": {"H": HIdistance, "J": IJdistance},
- "C": {"F": FCdistance, "G": GCdistance, "D": CDdistance},
- "F": {"G": FGdistance, "J": FJdistance},
- "K": {"G": KGdistance, "L": LKdistance},
- "D": {"E": DEdistance, "L": DLdistance},
- "M": {"L": LMdistance}
- })
- graph.locations = dict(
- A = (2,1) , B = (2,4) , C = (2,10) ,
- D = (2,15) , E = (2,19) , F = (5,9) ,
- G = (4,11) , H = (8,1) , I = (8,5),
- J = (8,8) , K = (8,13) , L = (8,15),
- M = (8,19))
- graphproblem1=GraphProblem(Pocetok,Stanica1,graph)
- rez1=astar_search(graphproblem1).solve()
- graphproblem2=GraphProblem(Stanica1, Kraj,graph)
- rez2=astar_search(graphproblem2).solve()
- pat1=rez1+rez2[1:len(rez2)]
- graphproblem1=GraphProblem(Pocetok,Stanica2,graph)
- rez1=astar_search(graphproblem1).solve()
- graphproblem2=GraphProblem(Stanica2, Kraj,graph)
- rez2=astar_search(graphproblem2).solve()
- pat2=rez1+rez2[1:len(rez2)]
- if len(pat1)<=len(pat2):
- if Stanica2 in pat1:
- print pat2
- else:
- print pat1
- else:
- print pat2
- **********drva na odluka*************
- trainingData=[
- [6.3,2.9,5.6,1.8,'I. virginica'],
- [6.5,3.0,5.8,2.2,'I. virginica'],
- [7.6,3.0,6.6,2.1,'I. virginica'],
- [4.9,2.5,4.5,1.7,'I. virginica'],
- [7.3,2.9,6.3,1.8,'I. virginica'],
- [6.7,2.5,5.8,1.8,'I. virginica'],
- [7.2,3.6,6.1,2.5,'I. virginica'],
- [6.5,3.2,5.1,2.0,'I. virginica'],
- [6.4,2.7,5.3,1.9,'I. virginica'],
- [6.8,3.0,5.5,2.1,'I. virginica'],
- [5.7,2.5,5.0,2.0,'I. virginica'],
- [5.8,2.8,5.1,2.4,'I. virginica'],
- [6.4,3.2,5.3,2.3,'I. virginica'],
- [6.5,3.0,5.5,1.8,'I. virginica'],
- [7.7,3.8,6.7,2.2,'I. virginica'],
- [7.7,2.6,6.9,2.3,'I. virginica'],
- [6.0,2.2,5.0,1.5,'I. virginica'],
- [6.9,3.2,5.7,2.3,'I. virginica'],
- [5.6,2.8,4.9,2.0,'I. virginica'],
- [7.7,2.8,6.7,2.0,'I. virginica'],
- [6.3,2.7,4.9,1.8,'I. virginica'],
- [6.7,3.3,5.7,2.1,'I. virginica'],
- [7.2,3.2,6.0,1.8,'I. virginica'],
- [6.2,2.8,4.8,1.8,'I. virginica'],
- [6.1,3.0,4.9,1.8,'I. virginica'],
- [6.4,2.8,5.6,2.1,'I. virginica'],
- [7.2,3.0,5.8,1.6,'I. virginica'],
- [7.4,2.8,6.1,1.9,'I. virginica'],
- [7.9,3.8,6.4,2.0,'I. virginica'],
- [6.4,2.8,5.6,2.2,'I. virginica'],
- [6.3,2.8,5.1,1.5,'I. virginica'],
- [6.1,2.6,5.6,1.4,'I. virginica'],
- [7.7,3.0,6.1,2.3,'I. virginica'],
- [6.3,3.4,5.6,2.4,'I. virginica'],
- [5.1,3.5,1.4,0.2,'I. setosa'],
- [4.9,3.0,1.4,0.2,'I. setosa'],
- [4.7,3.2,1.3,0.2,'I. setosa'],
- [4.6,3.1,1.5,0.2,'I. setosa'],
- [5.0,3.6,1.4,0.2,'I. setosa'],
- [5.4,3.9,1.7,0.4,'I. setosa'],
- [4.6,3.4,1.4,0.3,'I. setosa'],
- [5.0,3.4,1.5,0.2,'I. setosa'],
- [4.4,2.9,1.4,0.2,'I. setosa'],
- [4.9,3.1,1.5,0.1,'I. setosa'],
- [5.4,3.7,1.5,0.2,'I. setosa'],
- [4.8,3.4,1.6,0.2,'I. setosa'],
- [4.8,3.0,1.4,0.1,'I. setosa'],
- [4.3,3.0,1.1,0.1,'I. setosa'],
- [5.8,4.0,1.2,0.2,'I. setosa'],
- [5.7,4.4,1.5,0.4,'I. setosa'],
- [5.4,3.9,1.3,0.4,'I. setosa'],
- [5.1,3.5,1.4,0.3,'I. setosa'],
- [5.7,3.8,1.7,0.3,'I. setosa'],
- [5.1,3.8,1.5,0.3,'I. setosa'],
- [5.4,3.4,1.7,0.2,'I. setosa'],
- [5.1,3.7,1.5,0.4,'I. setosa'],
- [4.6,3.6,1.0,0.2,'I. setosa'],
- [5.1,3.3,1.7,0.5,'I. setosa'],
- [4.8,3.4,1.9,0.2,'I. setosa'],
- [5.0,3.0,1.6,0.2,'I. setosa'],
- [5.0,3.4,1.6,0.4,'I. setosa'],
- [5.2,3.5,1.5,0.2,'I. setosa'],
- [5.2,3.4,1.4,0.2,'I. setosa'],
- [5.5,2.3,4.0,1.3,'I. versicolor'],
- [6.5,2.8,4.6,1.5,'I. versicolor'],
- [5.7,2.8,4.5,1.3,'I. versicolor'],
- [6.3,3.3,4.7,1.6,'I. versicolor'],
- [4.9,2.4,3.3,1.0,'I. versicolor'],
- [6.6,2.9,4.6,1.3,'I. versicolor'],
- [5.2,2.7,3.9,1.4,'I. versicolor'],
- [5.0,2.0,3.5,1.0,'I. versicolor'],
- [5.9,3.0,4.2,1.5,'I. versicolor'],
- [6.0,2.2,4.0,1.0,'I. versicolor'],
- [6.1,2.9,4.7,1.4,'I. versicolor'],
- [5.6,2.9,3.6,1.3,'I. versicolor'],
- [6.7,3.1,4.4,1.4,'I. versicolor'],
- [5.6,3.0,4.5,1.5,'I. versicolor'],
- [5.8,2.7,4.1,1.0,'I. versicolor'],
- [6.2,2.2,4.5,1.5,'I. versicolor'],
- [5.6,2.5,3.9,1.1,'I. versicolor'],
- [5.9,3.2,4.8,1.8,'I. versicolor'],
- [6.1,2.8,4.0,1.3,'I. versicolor'],
- [6.3,2.5,4.9,1.5,'I. versicolor'],
- [6.1,2.8,4.7,1.2,'I. versicolor'],
- [6.4,2.9,4.3,1.3,'I. versicolor'],
- [6.6,3.0,4.4,1.4,'I. versicolor'],
- [6.8,2.8,4.8,1.4,'I. versicolor'],
- [6.7,3.0,5.0,1.7,'I. versicolor'],
- [6.0,2.9,4.5,1.5,'I. versicolor'],
- [5.7,2.6,3.5,1.0,'I. versicolor'],
- [5.5,2.4,3.8,1.1,'I. versicolor'],
- [5.5,2.4,3.7,1.0,'I. versicolor'],
- [5.8,2.7,3.9,1.2,'I. versicolor'],
- [6.0,2.7,5.1,1.6,'I. versicolor'],
- [5.4,3.0,4.5,1.5,'I. versicolor'],
- [6.0,3.4,4.5,1.6,'I. versicolor'],
- [6.7,3.1,4.7,1.5,'I. versicolor'],
- [6.3,2.3,4.4,1.3,'I. versicolor'],
- [5.6,3.0,4.1,1.3,'I. versicolor'],
- [5.5,2.5,4.0,1.3,'I. versicolor'],
- [5.5,2.6,4.4,1.2,'I. versicolor'],
- [6.1,3.0,4.6,1.4,'I. versicolor'],
- [5.8,2.6,4.0,1.2,'I. versicolor'],
- [5.0,2.3,3.3,1.0,'I. versicolor'],
- [5.6,2.7,4.2,1.3,'I. versicolor'],
- [5.7,3.0,4.2,1.2,'I. versicolor'],
- [5.7,2.9,4.2,1.3,'I. versicolor'],
- [6.2,2.9,4.3,1.3,'I. versicolor'],
- [5.1,2.5,3.0,1.1,'I. versicolor'],
- [5.7,2.8,4.1,1.3,'I. versicolor'],
- [6.4,3.1,5.5,1.8,'I. virginica'],
- [6.0,3.0,4.8,1.8,'I. virginica'],
- [6.9,3.1,5.4,2.1,'I. virginica'],
- [6.7,3.1,5.6,2.4,'I. virginica'],
- [6.9,3.1,5.1,2.3,'I. virginica'],
- [5.8,2.7,5.1,1.9,'I. virginica'],
- [6.8,3.2,5.9,2.3,'I. virginica'],
- [6.7,3.3,5.7,2.5,'I. virginica'],
- [6.7,3.0,5.2,2.3,'I. virginica'],
- [6.3,2.5,5.0,1.9,'I. virginica'],
- [6.5,3.0,5.2,2.0,'I. virginica'],
- [6.2,3.4,5.4,2.3,'I. virginica'],
- [4.7,3.2,1.6,0.2,'I. setosa'],
- [4.8,3.1,1.6,0.2,'I. setosa'],
- [5.4,3.4,1.5,0.4,'I. setosa'],
- [5.2,4.1,1.5,0.1,'I. setosa'],
- [5.5,4.2,1.4,0.2,'I. setosa'],
- [4.9,3.1,1.5,0.2,'I. setosa'],
- [5.0,3.2,1.2,0.2,'I. setosa'],
- [5.5,3.5,1.3,0.2,'I. setosa'],
- [4.9,3.6,1.4,0.1,'I. setosa'],
- [4.4,3.0,1.3,0.2,'I. setosa'],
- [5.1,3.4,1.5,0.2,'I. setosa'],
- [5.0,3.5,1.3,0.3,'I. setosa'],
- [4.5,2.3,1.3,0.3,'I. setosa'],
- [4.4,3.2,1.3,0.2,'I. setosa'],
- [5.0,3.5,1.6,0.6,'I. setosa'],
- [5.1,3.8,1.9,0.4,'I. setosa'],
- [4.8,3.0,1.4,0.3,'I. setosa'],
- [5.1,3.8,1.6,0.2,'I. setosa'],
- [5.9,3.0,5.1,1.8,'I. virginica']
- ]
- class decisionnode:
- def __init__(self,col=-1,value=None,results=None,tb=None,fb=None, level=0):
- self.col=col
- self.value=value
- self.results=results
- self.tb=tb
- self.fb=fb
- self.level=level
- def sporedi_broj(row,column,value):
- return row[column]>=value
- def sporedi_string(row,column,value):
- return row[column]==value
- # Divides a set on a specific column. Can handle numeric
- # or nominal values
- def divideset(rows,column,value):
- # Make a function that tells us if a row is in
- # the first group (true) or the second group (false)
- split_function=None
- if isinstance(value,int) or isinstance(value,float): # ako vrednosta so koja sporeduvame e od tip int ili float
- #split_function=lambda row:row[column]>=value # togas vrati funkcija cij argument e row i vrakja vrednost true ili false
- split_function=sporedi_broj
- else:
- # split_function=lambda row:row[column]==value # ako vrednosta so koja sporeduvame e od drug tip (string)
- split_function=sporedi_string
- # Divide the rows into two sets and return them
- # set1=[row for row in rows if split_function(row)] # za sekoj row od rows za koj split_function vrakja true
- # set2=[row for row in rows if not split_function(row)] # za sekoj row od rows za koj split_function vrakja false
- set1=[row for row in rows if split_function(row,column,value)] # za sekoj row od rows za koj split_function vrakja true
- set2=[row for row in rows if not split_function(row,column,value)] # za sekoj row od rows za koj split_function vrakja false
- return (set1,set2)
- # Create counts of possible results (the last column of
- # each row is the result)
- def uniquecounts(rows):
- results={}
- for row in rows:
- # The result is the last column
- r=row[len(row)-1]
- if r not in results: results[r]=0
- results[r]+=1
- return results
- # Probability that a randomly placed item will
- # be in the wrong category
- def giniimpurity(rows):
- total=len(rows)
- counts=uniquecounts(rows)
- imp=0
- for k1 in counts:
- p1=float(counts[k1])/total
- for k2 in counts:
- if k1==k2: continue
- p2=float(counts[k2])/total
- imp+=p1*p2
- return imp
- # Entropy is the sum of p(x)log(p(x)) across all
- # the different possible results
- def entropy(rows):
- from math import log
- log2=lambda x:log(x)/log(2)
- results=uniquecounts(rows)
- # Now calculate the entropy
- ent=0.0
- for r in results.keys():
- p=float(results[r])/len(rows)
- ent=ent-p*log2(p)
- return ent
- def buildtree(rows,scoref=entropy,level=0):
- if len(rows)==0: return decisionnode()
- current_score=scoref(rows)
- # Set up some variables to track the best criteria
- best_gain=0.0
- best_criteria=None
- best_sets=None
- column_count=len(rows[0])-1
- for col in range(0,column_count):
- # Generate the list of different values in
- # this column
- column_values={}
- for row in rows:
- column_values[row[col]]=1
- # Now try dividing the rows up for each value
- # in this column
- for value in column_values.keys():
- (set1,set2)=divideset(rows,col,value)
- # Information gain
- p=float(len(set1))/len(rows)
- gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)
- if gain>best_gain and len(set1)>0 and len(set2)>0:
- best_gain=gain
- best_criteria=(col,value)
- best_sets=(set1,set2)
- # Create the subbranches
- if best_gain>0:
- trueBranch=buildtree(best_sets[0], level=level+1)
- falseBranch=buildtree(best_sets[1], level=level+1)
- return decisionnode(col=best_criteria[0],value=best_criteria[1],
- tb=trueBranch, fb=falseBranch, level=level)
- else:
- return decisionnode(results=uniquecounts(rows))
- def printtree(tree,indent=''):
- # Is this a leaf node?
- if tree.results!=None:
- print (str(tree.results))
- else:
- # Print the criteria
- print (str(tree.col)+':'+str(tree.value)+'? ' + 'Level='+ str(tree.level))
- # Print the branches
- print (indent+'T->',
- printtree(tree.tb,indent+' '))
- print (indent+'F->',
- printtree(tree.fb,indent+' '))
- def classify(observation, tree):
- if tree.results != None:
- if len(tree.results.keys()) == 1: #edna klasa
- return tree.results.keys()[0]
- else: #so njgolem br instanci
- max = 0
- best = None
- for i in tree.results.keys():
- if tree.results[i] > max:
- max = tree.results[i]
- best = i
- elif tree.results[i] == max and i < best:
- best = i
- return best
- else:
- vrednost = observation[tree.col]
- branch = None
- if isinstance(vrednost, int) or isinstance(vrednost, float):
- if vrednost >= tree.value:
- branch = tree.tb
- else:
- branch = tree.fb
- else:
- if vrednost == tree.value:
- branch = tree.tb
- else:
- branch = tree.fb
- return classify(observation, branch)
- if __name__ == "__main__":
- att1=input()
- att2=input()
- att3=input()
- att4=input()
- planttype=input()
- testCase=[att1,att2,att3,att4,planttype]
- t1=[]
- lenght=len(trainingData)
- for i in range (0,lenght/2):
- t1.append(trainingData[i])
- t2=[]
- for i in range(lenght/2,lenght):
- t2.append(trainingData[i])
- tree1=buildtree(t1)
- tree2=buildtree(t2)
- tree1_class=classify(testCase,tree1)
- tree2_class=classify(testCase,tree2)
- if tree1_class==tree2_class:
- print (tree1_class)
- else:
- print ("KONTRADIKCIJA")
- *************informirano podvizni prepreki****
- # Python modul vo koj se implementirani algoritmite za informirano prebaruvanje
- # ______________________________________________________________________________________________
- # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
- import sys
- import bisect
- infinity = float('inf') # sistemski definirana vrednost za beskonecnost
- # ______________________________________________________________________________________________
- # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): A Last In First Out Queue.
- FIFOQueue(): A First In First Out Queue.
- PriorityQueue(order, f): Queue in sorted order (default min-first).
- Each type supports the following methods and functions:
- q.append(item) -- add an item to the queue
- q.extend(items) -- equivalent to: for item in items: q.append(item)
- q.pop() -- return the top item from the queue
- len(q) -- number of items in q (also q.__len())
- item in q -- does q contain item?
- Note that isinstance(Stack(), Queue) is false, because we implement stacks
- as lists. If Python ever gets interfaces, Queue will be an interface."""
- def __init__(self):
- raise NotImplementedError
- def extend(self, items):
- for item in items:
- self.append(item)
- def Stack():
- """A Last-In-First-Out Queue."""
- return []
- class FIFOQueue(Queue):
- """A First-In-First-Out Queue."""
- def __init__(self):
- self.A = []
- self.start = 0
- def append(self, item):
- self.A.append(item)
- def __len__(self):
- return len(self.A) - self.start
- def extend(self, items):
- self.A.extend(items)
- def pop(self):
- e = self.A[self.start]
- self.start += 1
- if self.start > 5 and self.start > len(self.A) / 2:
- self.A = self.A[self.start:]
- self.start = 0
- return e
- def __contains__(self, item):
- return item in self.A[self.start:]
- class PriorityQueue(Queue):
- """A queue in which the minimum (or maximum) element (as determined by f and
- order) is returned first. If order is min, the item with minimum f(x) is
- returned first; if order is max, then it is the item with maximum f(x).
- Also supports dict-like lookup. This structure will be most useful in informed searches"""
- def __init__(self, order=min, f=lambda x: x):
- self.A = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort(self.A, (self.f(item), item))
- def __len__(self):
- return len(self.A)
- def pop(self):
- if self.order == min:
- return self.A.pop(0)[1]
- else:
- return self.A.pop()[1]
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.A)
- def __getitem__(self, key):
- for _, item in self.A:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.A):
- if item == key:
- self.A.pop(i)
- # ______________________________________________________________________________________________
- # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
- # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
- # na sekoj eden problem sto sakame da go resime
- class Problem:
- """The abstract class for a formal problem. You should subclass this and
- implement the method successor, and possibly __init__, goal_test, and
- path_cost. Then you will create instances of your subclass and solve them
- with the various search functions."""
- def __init__(self, initial, goal=None):
- """The constructor specifies the initial state, and possibly a goal
- state, if there is a unique goal. Your subclass's constructor can add
- other arguments."""
- 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. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible from that state"""
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the 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."""
- 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."""
- return c + 1
- def value(self):
- """For optimization problems, each state has a value. Hill-climbing
- and related algorithms try to maximize this value."""
- raise NotImplementedError
- # ______________________________________________________________________________
- # Definiranje na klasa za strukturata na jazel od prebaruvanje
- # Klasata Node ne se nasleduva
- class Node:
- """A node in a search tree. Contains a pointer to the parent (the node
- that this is a successor of) and to the actual state for this node. Note
- that if a state is arrived at by two paths, then there are two nodes with
- the same state. Also includes the action that got us to this state, and
- the total path_cost (also known as g) to reach the node. Other functions
- may add an f and h value; see best_first_graph_search and astar_search for
- an explanation of how the f and h values are handled. You will not need to
- subclass this class."""
- def __init__(self, state, parent=None, action=None, path_cost=0):
- "Create a search tree Node, derived from a parent by an action."
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0
- 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."
- 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"
- next = problem.result(self.state, action)
- return Node(next, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next))
- def solution(self):
- "Return the sequence of actions to go from the root to this node."
- 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 [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."
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- return list(reversed(result))
- # We want for a queue of nodes in breadth_first_search or
- # astar_search to have no duplicated states, so we treat nodes
- # with the same state as equal. [Problem: this may not be what you
- # want in other contexts.]
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- # ________________________________________________________________________________________________________
- #Pomosna funkcija za informirani prebaruvanja
- #So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
- def memoize(fn, slot=None):
- """Memoize fn: make it remember the computed value for any argument list.
- If slot is specified, store result in that slot of first argument.
- If slot is false, store results in a dictionary."""
- 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 not memoized_fn.cache.has_key(args):
- memoized_fn.cache[args] = fn(*args)
- return memoized_fn.cache[args]
- memoized_fn.cache = {}
- return memoized_fn
- # ________________________________________________________________________________________________________
- #Informirano prebaruvanje vo ramki na graf
- def best_first_graph_search(problem, f):
- """Search the nodes with the lowest f scores first.
- You specify the function f(node) that you want to minimize; for example,
- if f is a heuristic estimate to the goal, then we have greedy best
- first search; if f is node.depth then we have breadth-first search.
- There is a subtlety: the line "f = memoize(f, 'f')" means that the f
- values will be cached on the nodes as they are computed. So after doing
- a best first search you can examine the f values of the path returned."""
- 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 accomplished by specifying f(n) = h(n)"
- 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 with f(n) = g(n)+h(n)."
- h = memoize(h or problem.h, 'h')
- return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
- # ________________________________________________________________________________________________________
- #Dopolnitelni prebaruvanja
- #Recursive_best_first_search e implementiran
- #Kako zadaca za studentite da gi implementiraat SMA* i IDA*
- def recursive_best_first_search(problem, h=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 immaterial)
- 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:
- # Order by 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
- # _________________________________________________________________________________________________________
- #PRIMER 2 : PROBLEM NA SLOZUVALKA
- #OPIS: Dadena e slozuvalka 3x3 na koja ima polinja so brojki od 1 do 8 i edno prazno pole
- # Praznoto pole e obelezano so *. Eden primer na slozuvalka e daden vo prodolzenie:
- # -------------
- # | * | 3 | 2 |
- # |---|---|---|
- # | 4 | 1 | 5 |
- # |---|---|---|
- # | 6 | 7 | 8 |
- # -------------
- #Problemot e kako da se stigne do nekoja pocetna raspredelba na polinjata do nekoja posakuvana, na primer do:
- # -------------
- # | * | 1 | 2 |
- # |---|---|---|
- # | 3 | 4 | 5 |
- # |---|---|---|
- # | 6 | 7 | 8 |
- # -------------
- #AKCII: Akciite ke gi gledame kako dvizenje na praznoto pole, pa mozni akcii se : gore, dole, levo i desno.
- #Pri definiranjeto na akciite mora da se vnimava dali akciite voopsto mozat da se prevzemat vo dadenata slozuvalka
- #STATE: Sostojbata ke ja definirame kako string koj ke ima 9 karakteri (po eden za sekoe brojce plus za *)
- #pri sto stringot ke se popolnuva so izminuvanje na slozuvalkata od prviot kon tretiot red, od levo kon desno.
- # Na primer sostojbata za pocetnata slozuvalka e: '*32415678'
- # Sostojbata za finalnata slozuvalka e: '*12345678'
- # ________________________________________________________________________________________________________
- #
- default_goal = '*12345678' #predefinirana cel
- #Ke definirame 3 klasi za problemot
- #Prvata klasa nema implementirano nikakva hevristika
- class P8(Problem):
- name = 'No Heuristic'
- def __init__(self, goal=default_goal, initial=None, N=20):
- self.goal = goal
- self.initial = initial
- def successor(self, state):
- return successor8(state)
- def actions(self, state):
- return self.successor(state).keys()
- def h(self, node):
- """Heuristic for 8 puzzle: returns 0"""
- return 0
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- #Slednite klasi ke nasleduvaat od prethodnata bez hevristika so toa sto ovde ke ja definirame i hevristikata
- class P8_h1(P8):
- """ Slozuvalka so hevristika
- HEVRISTIKA: Brojot na polinja koi ne se na vistinskoto mesto"""
- name = 'Out of Place Heuristic'
- def h(self, node):
- """Funkcija koja ja presmetuva hevristikata,
- t.e. razlikata pomegu nekoj tekoven jazel od prebaruvanjeto i celniot jazel"""
- matches = 0
- for (t1, t2) in zip(node.state, self.goal):
- #zip funkcijata od dve listi na vlez pravi edna lista od parovi (torki)
- #primer: zip(['a','b','c'],[1,2,3]) == [('a',1),('b',2),('c',3)]
- # zip('abc','123') == [('a','1'),('b','2'),('c','3')]
- if t1 != t2:
- matches = + 1
- return matches
- class P8_h2(P8):
- """ Slozuvalka so hevristika
- HEVRISTIKA: Menheten rastojanie do celna sostojba"""
- name = 'Manhattan Distance Heuristic (MHD)'
- def h(self, node):
- """Funkcija koja ja presmetuva hevristikata,
- t.e. Menheten rastojanieto pomegu nekoj tekoven jazel od prebaruvanjeto i celniot jazel, pri sto
- Menheten rastojanieto megu jazlite e zbir od Menheten rastojanijata pomegu istite broevi vo dvata jazli"""
- sum = 0
- for c in '12345678':
- sum = + mhd(node.state.index(c), self.goal.index(c)) #pomosna funkcija definirana vo prodolzenie
- return sum
- # Za da mozeme da go definirame rastojanieto treba da definirame koordinaten sistem
- # Pozetokot na koordinatniot sistem e postaven vo gorniot lev agol na slozuvalkata
- # Definirame recnik za koordinatite na sekoe pole od slozuvalkata
- coordinates = {0: (0, 0), 1: (1, 0), 2: (2, 0),
- 3: (0, 1), 4: (1, 1), 5: (2, 1),
- 6: (0, 2), 7: (1, 2), 8: (2, 2)}
- #Funkcija koja presmetuva Menheten rastojanie za slozuvalkata
- #Na vlez dobiva dva celi broja koi odgovaraat na dve polinja na koi se naogaat broevite za koi treba da presmetame rastojanie
- def mhd(n, m):
- x1, y1 = coordinates[n]
- x2, y2 = coordinates[m]
- return abs(x1 - x2) + abs(y1 - y2)
- def successor8(S):
- """Pomosna funkcija koja generira recnik za sledbenicite na daden jazel"""
- blank = S.index('*') #kade se naoga praznoto pole
- succs = {}
- # GORE: Ako praznoto pole ne e vo prviot red, togas vo sostojbata napravi swap
- # na praznoto pole so brojceto koe se naoga na poleto nad nego
- if blank > 2:
- swap = blank - 3
- succs['GORE'] = S[0:swap] + '*' + S[swap + 1:blank] + S[swap] + S[blank + 1:]
- # DOLE: Ako praznoto pole ne e vo posledniot red, togas vo sostojbata napravi swap
- # na praznoto pole so brojceto koe se naoga na poleto pod nego
- if blank < 6:
- swap = blank + 3
- succs['DOLE'] = S[0:blank] + S[swap] + S[blank + 1:swap] + '*' + S[swap + 1:]
- # LEVO: Ako praznoto pole ne e vo prvata kolona, togas vo sostojbata napravi swap
- # na praznoto pole so brojceto koe se naoga na poleto levo od nego
- if blank % 3 > 0:
- swap = blank - 1
- succs['LEVO'] = S[0:swap] + '*' + S[swap] + S[blank + 1:]
- # DESNO: Ako praznoto pole ne e vo poslednata kolona, togas vo sostojbata napravi swap
- # na praznoto pole so brojceto koe se naoga na poleto desno od nego
- if blank % 3 < 2:
- swap = blank + 1
- succs['DESNO'] = S[0:blank] + S[swap] + '*' + S[swap + 1:]
- return succs
- # So vaka definiraniot problem mozeme da gi koristime site informirani, no i neinformirani prebaruvanja
- # Vo prodolzenie se dadeni mozni povici (vnimavajte za da moze da napravite povik mora da definirate problem)
- #
- # s='*32415678'
- # p1=P8(initial=s)
- # p2=P8_h1(initial=s)
- # p3=P8_h2(initial=s)
- #
- # answer1 = greedy_best_first_graph_search(p1)
- # print answer1.solve()
- #
- # answer2 = greedy_best_first_graph_search(p2)
- # print answer2.solve()
- #
- # answer3 = greedy_best_first_graph_search(p3)
- # print answer3.solve()
- #
- # answer4 = astar_search(p1)
- # print answer4.solve()
- #
- # answer5 = astar_search(p2)
- # print answer5.solve()
- #
- # answer6 = astar_search(p3)
- # print answer6.solve()
- #
- # answer7 = recursive_best_first_search(p1)
- # print answer7.solve()
- #
- # answer8 = recursive_best_first_search(p2)
- # print answer8.solve()
- #
- # answer9 = recursive_best_first_search(p3)
- # print answer9.solve()
- def updateP1(P1):
- x = P1[0]
- y = P1[1]
- n = P1[2]
- if (y == 4 and n == 1):
- n = n * (-1)
- if (y == 0 and n == -1):
- n = n * (-1)
- ynew = y + n
- return (x, ynew, n)
- def updateP2(P2):
- x = P2[0]
- y = P2[1]
- n = P2[2]
- if (x == 5 and y == 4 and n == 1):
- n = n * (-1)
- if (y == 0 and x == 9 and n == -1):
- n = n * (-1)
- xnew = x - n
- ynew = y + n
- return (xnew, ynew, n)
- def updateP3(P3):
- x = P3[0]
- y = P3[1]
- n = P3[2]
- if (x == 5 and n == -1):
- n = n * (-1)
- if (x == 9 and n == 1):
- n = n * (-1)
- xnew = x + n
- return (xnew, y, n)
- def isValid(x, y, P1, P2, P3):
- t = 1
- if (x == P1[0] and y == P1[1]) or (x == P1[0] and y == P1[1] + 1):
- t = 0
- if (x == P2[0] and y == P2[1]) or (x == P2[0] and y == P2[1] + 1) or (x == P2[0] + 1 and y == P2[1]) or (
- x == P2[0] + 1 and y == P2[1] + 1):
- t = 0
- if (x == P3[0] and y == P3[1]) or (x == P3[0] + 1 and y == P3[1]):
- t = 0
- return t
- class Istrazuvac(Problem):
- def __init__(self, initial, goal):
- self.initial = initial
- self.goal = goal
- def successor(self, state):
- successors = dict()
- X = state[0]
- Y = state[1]
- P1 = state[2]
- P2 = state[3]
- P3 = state[4]
- P1new = updateP1(P1)
- P2new = updateP2(P2)
- P3new = updateP3(P3)
- # Levo
- if Y - 1 >= 0:
- Ynew = Y - 1
- Xnew = X
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Levo'] = (Xnew, Ynew, P1new, P2new, P3new)
- # Desno
- if X < 5 and Y < 5:
- Ynew = Y + 1
- Xnew = X
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
- elif X >= 5 and Y < 10:
- Xnew = X
- Ynew = Y + 1
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
- # Dolu
- if X < 10:
- Xnew = X + 1
- Ynew = Y
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Dolu'] = (Xnew, Ynew, P1new, P2new, P3new)
- # Gore
- if Y >= 6 and X > 5:
- Xnew = X - 1
- Ynew = Y
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
- elif Y < 6 and X > 0:
- Xnew = X - 1
- Ynew = Y
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
- 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):
- g = self.goal
- return (state[0] == g[0] and state[1] == g[1])
- def h(self,node):
- rez=abs(node.state[0]-self.goal[0])+abs(node.state[1]-self.goal[1])
- return rez
- #Vcituvanje na vleznite argumenti za test primerite
- CoveceRedica = input()
- CoveceKolona = input()
- KukaRedica = input()
- KukaKolona = input()
- #Vasiot kod pisuvajte go pod ovoj komentar
- # prepreka 1 ima lev kvadrat na 2,2 odi levo (-1) na pocetok, prepreka 2 ima goren lev kvadrat na 2,7 odi gore desno (1)
- # prepreka 3 ima gore kvadrat na 8,7 odi nagore na pocetok(-1)
- IstrazuvacInstance = Istrazuvac((CoveceRedica, CoveceKolona, (2, 2, -1), (7, 2, 1), (7, 8, 1)),(KukaRedica, KukaKolona))
- answer=astar_search(IstrazuvacInstance).solution()
- print(answer)
- ***************informirano misioneri ********
- #Vcituvanje na vleznite argumenti za test primerite
- N = input()
- K = input()
- #Vasiot kod pisuvajte go pod ovoj komentar
- # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
- # ______________________________________________________________________________________________
- # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
- import math
- import sys
- import bisect
- infinity = float('inf') # sistemski definirana vrednost za beskonecnost
- # ______________________________________________________________________________________________
- # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): A Last In First Out Queue.
- FIFOQueue(): A First In First Out Queue.
- PriorityQueue(order, f): Queue in sorted order (default min-first).
- Each type supports the following methods and functions:
- q.append(item) -- add an item to the queue
- q.extend(items) -- equivalent to: for item in items: q.append(item)
- q.pop() -- return the top item from the queue
- len(q) -- number of items in q (also q.__len())
- item in q -- does q contain item?
- Note that isinstance(Stack(), Queue) is false, because we implement stacks
- as lists. If Python ever gets interfaces, Queue will be an interface."""
- def __init__(self):
- raise NotImplementedError
- def extend(self, items):
- for item in items:
- self.append(item)
- class PriorityQueue(Queue):
- """A queue in which the minimum (or maximum) element (as determined by f and
- order) is returned first. If order is min, the item with minimum f(x) is
- returned first; if order is max, then it is the item with maximum f(x).
- Also supports dict-like lookup. This structure will be most useful in informed searches"""
- def __init__(self, order=min, f=lambda x: x):
- self.A = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort(self.A, (self.f(item), item))
- def __len__(self):
- return len(self.A)
- def pop(self):
- if self.order == min:
- return self.A.pop(0)[1]
- else:
- return self.A.pop()[1]
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.A)
- def __getitem__(self, key):
- for _, item in self.A:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.A):
- if item == key:
- self.A.pop(i)
- # ______________________________________________________________________________________________
- # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
- # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
- # na sekoj eden problem sto sakame da go resime
- class Problem:
- """The abstract class for a formal problem. You should subclass this and
- implement the method successor, and possibly __init__, goal_test, and
- path_cost. Then you will create instances of your subclass and solve them
- with the various search functions."""
- def __init__(self, initial, goal=None):
- """The constructor specifies the initial state, and possibly a goal
- state, if there is a unique goal. Your subclass's constructor can add
- other arguments."""
- 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. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible from that state"""
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the 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."""
- 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."""
- return c + 1
- def value(self):
- """For optimization problems, each state has a value. Hill-climbing
- and related algorithms try to maximize this value."""
- raise NotImplementedError
- # ______________________________________________________________________________
- # Definiranje na klasa za strukturata na jazel od prebaruvanje
- # Klasata Node ne se nasleduva
- class Node:
- """A node in a search tree. Contains a pointer to the parent (the node
- that this is a successor of) and to the actual state for this node. Note
- that if a state is arrived at by two paths, then there are two nodes with
- the same state. Also includes the action that got us to this state, and
- the total path_cost (also known as g) to reach the node. Other functions
- may add an f and h value; see best_first_graph_search and astar_search for
- an explanation of how the f and h values are handled. You will not need to
- subclass this class."""
- def __init__(self, state, parent=None, action=None, path_cost=0):
- "Create a search tree Node, derived from a parent by an action."
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0
- 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."
- return [self.child_node(problem, action)
- for action in problem.actions(self.state)] # samo ednash se povikuva actions za momentalnata sostojba
- def child_node(self, problem, action):
- "Return a child node from this node"
- next = problem.result(self.state, action)
- return Node(next, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next))
- def solution(self):
- "Return the sequence of actions to go from the root to this node."
- 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 [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."
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- return list(reversed(result))
- # We want for a queue of nodes in breadth_first_search or
- # astar_search to have no duplicated states, so we treat nodes
- # with the same state as equal. [Problem: this may not be what you
- # want in other contexts.]
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- # ________________________________________________________________________________________________________
- # Pomosna funkcija za informirani prebaruvanja
- # So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
- def memoize(fn, slot=None):
- """Memoize fn: make it remember the computed value for any argument list.
- If slot is specified, store result in that slot of first argument.
- If slot is false, store results in a dictionary."""
- 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 not memoized_fn.cache.has_key(args):
- memoized_fn.cache[args] = fn(*args)
- return memoized_fn.cache[args]
- memoized_fn.cache = {}
- return memoized_fn
- # ________________________________________________________________________________________________________
- # Informirano prebaruvanje vo ramki na graf
- def best_first_graph_search(problem, f):
- """Search the nodes with the lowest f scores first.
- You specify the function f(node) that you want to minimize; for example,
- if f is a heuristic estimate to the goal, then we have greedy best
- first search; if f is node.depth then we have breadth-first search.
- There is a subtlety: the line "f = memoize(f, 'f')" means that the f
- values will be cached on the nodes as they are computed. So after doing
- a best first search you can examine the f values of the path returned."""
- 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 node.state == (1, 1, 'D', 2, 2):
- # print(child.state)
- 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 accomplished by specifying f(n) = h(n)"
- h = memoize(h or problem.h, 'h')
- return best_first_graph_search(problem, h)
- class Mission(Problem):
- def __init__(self,N,capacity):
- self.initial=(N, N, 'L', 0, 0)
- self.capacity=capacity
- def goal_test(self, state):
- return (state[0]==0 and state[1]==0)
- def h(self,node):
- missionaryLeft=node.state[0]
- cannibalLeft=node.state[1]
- return (missionaryLeft+cannibalLeft)/2
- def is_valid(self,missionaryLeft, cannibalLeft,missionaryRight, cannibalRight):
- return (missionaryLeft>=0 and missionaryRight>=0 and cannibalLeft>=0 and cannibalRight>=0 \
- and (missionaryLeft ==0 or missionaryLeft >= cannibalLeft) and ( missionaryRight == 0 or missionaryRight >= cannibalRight))
- def successor(self, state):
- successors=dict()
- missionaryLeft = state[0]
- cannibalLeft = state[1]
- boat = state[2]
- missionaryRight = state[3]
- cannibalRight = state[4]
- if boat=='L':
- for i in range(1,self.capacity+1):
- for j in range(0, i+1):
- newMissionaryLeft=missionaryLeft-(i-j)
- newCannibalLeft=cannibalLeft-j
- newMissionaryRight=missionaryRight+(i-j)
- newCannibalRight=cannibalRight+j
- if(self.is_valid(newMissionaryLeft,newCannibalLeft,newMissionaryRight,newCannibalRight)):
- successors[str(i-j)+'M_'+str(j)+'K']=(newMissionaryLeft,newCannibalLeft,'D',newMissionaryRight,newCannibalRight)
- if boat=='D':
- for i in range(1,self.capacity+1):
- for j in range(0, i+1):
- newMissionaryRight = missionaryRight - (i-j)
- newCannibalRight = cannibalRight - j
- newMissionaryLeft=missionaryLeft+(i-j)
- newCannibalLeft=cannibalLeft+j
- if(self.is_valid(newMissionaryLeft,newCannibalLeft,newMissionaryRight,newCannibalRight)):
- successors[str(i-j)+'M_'+str(j)+'K']=(newMissionaryLeft,newCannibalLeft,'L',newMissionaryRight,newCannibalRight)
- return successors
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- MissionInstance=Mission(int(N),int(K))
- answer = greedy_best_first_graph_search(MissionInstance)
- print(answer.solve())
- *********podvizni neinf***
- # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
- # ______________________________________________________________________________________________
- # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
- import sys
- import bisect
- infinity = float('inf') # sistemski definirana vrednost za beskonecnost
- # ______________________________________________________________________________________________
- # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): A Last In First Out Queue.
- FIFOQueue(): A First In First Out Queue.
- PriorityQueue(order, f): Queue in sorted order (default min-first).
- Each type supports the following methods and functions:
- q.append(item) -- add an item to the queue
- q.extend(items) -- equivalent to: for item in items: q.append(item)
- q.pop() -- return the top item from the queue
- len(q) -- number of items in q (also q.__len())
- item in q -- does q contain item?
- Note that isinstance(Stack(), Queue) is false, because we implement stacks
- as lists. If Python ever gets interfaces, Queue will be an interface."""
- def __init__(self):
- raise NotImplementedError
- def extend(self, items):
- for item in items:
- self.append(item)
- class FIFOQueue(Queue):
- """A First-In-First-Out Queue."""
- def __init__(self):
- self.A = []
- self.start = 0
- def append(self, item):
- self.A.append(item)
- def __len__(self):
- return len(self.A) - self.start
- def extend(self, items):
- self.A.extend(items)
- def pop(self):
- e = self.A[self.start]
- self.start += 1
- if self.start > 5 and self.start > len(self.A) / 2:
- self.A = self.A[self.start:]
- self.start = 0
- return e
- def __contains__(self, item):
- return item in self.A[self.start:]
- # ______________________________________________________________________________________________
- # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
- # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
- # na sekoj eden problem sto sakame da go resime
- class Problem:
- """The abstract class for a formal problem. You should subclass this and
- implement the method successor, and possibly __init__, goal_test, and
- path_cost. Then you will create instances of your subclass and solve them
- with the various search functions."""
- def __init__(self, initial, goal=None):
- """The constructor specifies the initial state, and possibly a goal
- state, if there is a unique goal. Your subclass's constructor can add
- other arguments."""
- 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. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible from that state"""
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the 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."""
- 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."""
- return c + 1
- def value(self):
- """For optimization problems, each state has a value. Hill-climbing
- and related algorithms try to maximize this value."""
- raise NotImplementedError
- # ______________________________________________________________________________
- # Definiranje na klasa za strukturata na jazel od prebaruvanje
- # Klasata Node ne se nasleduva
- class Node:
- """A node in a search tree. Contains a pointer to the parent (the node
- that this is a successor of) and to the actual state for this node. Note
- that if a state is arrived at by two paths, then there are two nodes with
- the same state. Also includes the action that got us to this state, and
- the total path_cost (also known as g) to reach the node. Other functions
- may add an f and h value; see best_first_graph_search and astar_search for
- an explanation of how the f and h values are handled. You will not need to
- subclass this class."""
- def __init__(self, state, parent=None, action=None, path_cost=0):
- "Create a search tree Node, derived from a parent by an action."
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0
- 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."
- 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"
- next = problem.result(self.state, action)
- return Node(next, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next))
- def solution(self):
- "Return the sequence of actions to go from the root to this node."
- 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 [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."
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- return list(reversed(result))
- # We want for a queue of nodes in breadth_first_search or
- # astar_search to have no duplicated states, so we treat nodes
- # with the same state as equal. [Problem: this may not be what you
- # want in other contexts.]
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- def graph_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- The argument fringe should be an empty queue.
- If two paths reach a state, only use the best one."""
- closed = {}
- 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[node.state] = True
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_graph_search(problem):
- "Search the shallowest nodes in the search tree first."
- return graph_search(problem, FIFOQueue())
- def updateP1(P1):
- x = P1[0]
- y = P1[1]
- n = P1[2]
- if (y == 4 and n == 1):
- n = n * (-1)
- if (y == 0 and n == -1):
- n = n * (-1)
- ynew = y + n
- return (x, ynew, n)
- def updateP2(P2):
- x = P2[0]
- y = P2[1]
- n = P2[2]
- if (x == 5 and y == 4 and n == 1):
- n = n * (-1)
- if (y == 0 and x == 9 and n == -1):
- n = n * (-1)
- xnew = x - n
- ynew = y + n
- return (xnew, ynew, n)
- def updateP3(P3):
- x = P3[0]
- y = P3[1]
- n = P3[2]
- if (x == 5 and n == -1):
- n = n * (-1)
- if (x == 9 and n == 1):
- n = n * (-1)
- xnew = x + n
- return (xnew, y, n)
- def isValid(x, y, P1, P2, P3):
- t = 1
- if (x == P1[0] and y == P1[1]) or (x == P1[0] and y == P1[1] + 1):
- t = 0
- if (x == P2[0] and y == P2[1]) or (x == P2[0] and y == P2[1] + 1) or (x == P2[0] + 1 and y == P2[1]) or (
- x == P2[0] + 1 and y == P2[1] + 1):
- t = 0
- if (x == P3[0] and y == P3[1]) or (x == P3[0] + 1 and y == P3[1]):
- t = 0
- return t
- class Istrazuvac(Problem):
- def __init__(self, initial, goal):
- self.initial = initial
- self.goal = goal
- def successor(self, state):
- successors = dict()
- X = state[0]
- Y = state[1]
- P1 = state[2]
- P2 = state[3]
- P3 = state[4]
- P1new = updateP1(P1)
- P2new = updateP2(P2)
- P3new = updateP3(P3)
- # Levo
- if Y - 1 >= 0:
- Ynew = Y - 1
- Xnew = X
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Levo'] = (Xnew, Ynew, P1new, P2new, P3new)
- # Desno
- if X < 5 and Y < 5:
- Ynew = Y + 1
- Xnew = X
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
- elif X >= 5 and Y < 10:
- Xnew = X
- Ynew = Y + 1
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
- # Dolu
- if X < 10:
- Xnew = X + 1
- Ynew = Y
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Dolu'] = (Xnew, Ynew, P1new, P2new, P3new)
- # Gore
- if Y >= 6 and X > 5:
- Xnew = X - 1
- Ynew = Y
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
- elif Y < 6 and X > 0:
- Xnew = X - 1
- Ynew = Y
- if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
- successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
- 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):
- g = self.goal
- return (state[0] == g[0] and state[1] == g[1])
- CoveceRedica = int(input())
- CoveceKolona = int(input())
- KukaRedica = int(input())
- KukaKolona = int(input())
- # prepreka 1 ima lev kvadrat na 2,2 odi levo (-1) na pocetok, prepreka 2 ima goren lev kvadrat na 2,7 odi gore desno (1)
- # prepreka 3 ima gore kvadrat na 8,7 odi nagore na pocetok(-1)
- IstrazuvacInstance = Istrazuvac((CoveceRedica, CoveceKolona, (2, 2, -1), (7, 2, 1), (7, 8, 1)),(KukaRedica, KukaKolona))
- answer = breadth_first_graph_search(IstrazuvacInstance)
- print(answer.solution())
- ****molekula neinf***
- # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
- # ______________________________________________________________________________________________
- # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
- import sys
- import bisect
- infinity = float('inf') # sistemski definirana vrednost za beskonecnost
- # ______________________________________________________________________________________________
- # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): A Last In First Out Queue.
- FIFOQueue(): A First In First Out Queue.
- PriorityQueue(order, f): Queue in sorted order (default min-first).
- Each type supports the following methods and functions:
- q.append(item) -- add an item to the queue
- q.extend(items) -- equivalent to: for item in items: q.append(item)
- q.pop() -- return the top item from the queue
- len(q) -- number of items in q (also q.__len())
- item in q -- does q contain item?
- Note that isinstance(Stack(), Queue) is false, because we implement stacks
- as lists. If Python ever gets interfaces, Queue will be an interface."""
- def __init__(self):
- raise NotImplementedError
- def extend(self, items):
- for item in items:
- self.append(item)
- def Stack():
- """A Last-In-First-Out Queue."""
- return []
- class FIFOQueue(Queue):
- """A First-In-First-Out Queue."""
- def __init__(self):
- self.A = []
- self.start = 0
- def append(self, item):
- self.A.append(item)
- def __len__(self):
- return len(self.A) - self.start
- def extend(self, items):
- self.A.extend(items)
- def pop(self):
- e = self.A[self.start]
- self.start += 1
- if self.start > 5 and self.start > len(self.A) / 2:
- self.A = self.A[self.start:]
- self.start = 0
- return e
- def __contains__(self, item):
- return item in self.A[self.start:]
- class PriorityQueue(Queue):
- """A queue in which the minimum (or maximum) element (as determined by f and
- order) is returned first. If order is min, the item with minimum f(x) is
- returned first; if order is max, then it is the item with maximum f(x).
- Also supports dict-like lookup. This structure will be most useful in informed searches"""
- def __init__(self, order=min, f=lambda x: x):
- self.A = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort(self.A, (self.f(item), item))
- def __len__(self):
- return len(self.A)
- def pop(self):
- if self.order == min:
- return self.A.pop(0)[1]
- else:
- return self.A.pop()[1]
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.A)
- def __getitem__(self, key):
- for _, item in self.A:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.A):
- if item == key:
- self.A.pop(i)
- # ______________________________________________________________________________________________
- # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
- # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
- # na sekoj eden problem sto sakame da go resime
- class Problem:
- """The abstract class for a formal problem. You should subclass this and
- implement the method successor, and possibly __init__, goal_test, and
- path_cost. Then you will create instances of your subclass and solve them
- with the various search functions."""
- def __init__(self, initial, goal=None):
- """The constructor specifies the initial state, and possibly a goal
- state, if there is a unique goal. Your subclass's constructor can add
- other arguments."""
- 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. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible from that state"""
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the 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."""
- 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."""
- return c + 1
- def value(self):
- """For optimization problems, each state has a value. Hill-climbing
- and related algorithms try to maximize this value."""
- raise NotImplementedError
- # ______________________________________________________________________________
- # Definiranje na klasa za strukturata na jazel od prebaruvanje
- # Klasata Node ne se nasleduva
- class Node:
- """A node in a search tree. Contains a pointer to the parent (the node
- that this is a successor of) and to the actual state for this node. Note
- that if a state is arrived at by two paths, then there are two nodes with
- the same state. Also includes the action that got us to this state, and
- the total path_cost (also known as g) to reach the node. Other functions
- may add an f and h value; see best_first_graph_search and astar_search for
- an explanation of how the f and h values are handled. You will not need to
- subclass this class."""
- def __init__(self, state, parent=None, action=None, path_cost=0):
- "Create a search tree Node, derived from a parent by an action."
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0
- 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."
- 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"
- next = problem.result(self.state, action)
- return Node(next, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next))
- def solution(self):
- "Return the sequence of actions to go from the root to this node."
- 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 [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."
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- return list(reversed(result))
- # We want for a queue of nodes in breadth_first_search or
- # astar_search to have no duplicated states, so we treat nodes
- # with the same state as equal. [Problem: this may not be what you
- # want in other contexts.]
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- # ________________________________________________________________________________________________________
- #Neinformirano prebaruvanje vo ramki na drvo
- #Vo ramki na drvoto ne razresuvame jamki
- def tree_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- The argument fringe should be an empty queue."""
- 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."
- return tree_search(problem, FIFOQueue())
- def depth_first_tree_search(problem):
- "Search the deepest nodes in the search tree first."
- return tree_search(problem, Stack())
- # ________________________________________________________________________________________________________
- #Neinformirano prebaruvanje vo ramki na graf
- #Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi
- def graph_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- The argument fringe should be an empty queue.
- If two paths reach a state, only use the best one."""
- closed = {}
- 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[node.state] = True
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_graph_search(problem):
- "Search the shallowest nodes in the search tree first."
- return graph_search(problem, FIFOQueue())
- def depth_first_graph_search(problem):
- "Search the deepest nodes in the search tree first."
- return graph_search(problem, Stack())
- 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))
- def depth_limited_search(problem, limit=50):
- "depth first search with limited depth"
- 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 != None:
- return result
- if cutoff_occurred:
- return 'cutoff'
- else:
- return None
- # Body of depth_limited_search:
- return recursive_dls(Node(problem.initial), problem, limit)
- #def iterative_deepening_search(problem):
- #
- # for depth in xrange(sys.maxint):
- # result = depth_limited_search(problem, depth)
- # if result is not 'cutoff':
- # return result
- # _________________________________________________________________________________________________________
- #PRIMER 1 : PROBLEM SO DVA SADA SO VODA
- #OPIS: Dadeni se dva sada J0 i J1 so kapaciteti C0 i C1
- #Na pocetok dvata sada se polni. Inicijalnata sostojba moze da se prosledi na pocetok
- #Problemot e kako da se stigne do sostojba vo koja J0 ke ima G0 litri, a J1 ke ima G1 litri
- #AKCII: 1. Da se isprazni bilo koj od sadovite
- #2. Da se prefrli tecnosta od eden sad vo drug so toa sto ne moze da se nadmine kapacitetot na sadovite
- # Moze da ima i opcionalen tret vid na akcii 3. Napolni bilo koj od sadovite (studentite da ja implementiraat ovaa varijanta)
- # ________________________________________________________________________________________________________
- class WJ(Problem):
- """STATE: Torka od oblik (3,2) if jug J0 has 3 liters and J1 2 liters
- Opcionalno moze za nekoj od sadovite da se sretne i vrednost '*' sto znaci deka e nebitno kolku ima vo toj sad
- GOAL: Predefinirana sostojba do kade sakame da stigneme. Ako ne interesira samo eden sad za drugiot mozeme da stavime '*'
- PROBLEM: Se specificiraat kapacitetite na sadovite, pocetna sostojba i cel """
- def __init__(self, capacities=(5, 2), initial=(5, 0), goal=(0, 1)):
- self.capacities = capacities
- self.initial = initial
- self.goal = goal
- def goal_test(self, state):
- """ Vraka true ako sostojbata e celna """
- g = self.goal
- return (state[0] == g[0] or g[0] == '*') and \
- (state[1] == g[1] or g[1] == '*')
- def successor(self, J):
- """Vraka recnik od sledbenici na sostojbata"""
- successors = dict()
- J0, J1 = J
- #print (J)
- (C0, C1) = self.capacities
- if J0 > 0:
- Jnew = 0, J1
- successors['dump jug 0'] = Jnew
- if J1 > 0:
- Jnew = J0, 0
- successors['dump jug 1'] = Jnew
- if J1 < C1 and J0 > 0:
- delta = min(J0, C1 - J1)
- Jnew = J0 - delta, J1 + delta
- successors['pour jug 0 into jug 1'] = Jnew
- if J0 < C0 and J1 > 0:
- delta = min(J1, C0 - J0)
- Jnew = J0 + delta, J1 - delta
- successors['pour jug 1 into jug 0'] = Jnew
- return successors
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- # So vaka definiraniot problem mozeme da gi koristime site neinformirani prebaruvanja
- # Vo prodolzenie se dadeni mozni povici (vnimavajte za da moze da napravite povik mora da definirate problem)
- #
- WJInstance = WJ((5, 2), (5, 2), ('*', 1))
- #print (WJInstance)
- #
- #answer1 = breadth_first_tree_search(WJInstance)
- #print (answer1.solve())
- #
- # answer2 = depth_first_tree_search(WJInstance) #vnimavajte na ovoj povik, moze da vleze vo beskonecna jamka
- # print answer2.solve()
- #
- #
- #answer3 = breadth_first_graph_search(WJInstance)
- #print (answer3.solve())
- #
- # answer4 = depth_first_graph_search(WJInstance)
- # print answer4.solve()
- #
- # answer5 = depth_limited_search(WJInstance)
- # print answer5.solve()
- #
- # answer6 = iterative_deepening_search(WJInstance)
- # print answer6.solve()
- Prepreki = [(6, 1), (6, 2), (4, 2), (2, 3), (1, 4), (1, 6), (1, 8), \
- (2, 9), (6, 4), (5, 5), (6, 7), (5, 7), (4, 7), (4, 8)]
- def goreAtomH1(A):
- while (A[0] > 0 and A[0] < 8 and A[1] > 0 and A[1] < 10 and \
- ((A[0], A[1]) not in Prepreki) and \
- ((A[0], A[1]) not in ((A[2], A[3]), (A[4], A[5])))):
- X = A[0]
- X = X - 1
- A = X, A[1], A[2], A[3], A[4], A[5]
- Anew = A[0] + 1, A[1]
- return Anew
- def doluAtomH1(A):
- while(A[0]>0 and A[0] < 8 and A[1] > 0 and A[1] < 10 and((A[0], A[1]) not in Prepreki) and \
- ((A[0], A[1]) not in ((A[2], A[3]), (A[4], A[5])))):
- x = A[0]
- x = x + 1
- A = x, A[1], A[2], A[3], A[4], A[5]
- Anew = A[0] - 1, A[1]
- return Anew
- def levoAtomH1(A):
- while(A[0]>0 and A[0] < 8 and A[1] > 0 and A[1] < 10 and((A[0], A[1]) not in Prepreki) and \
- ((A[0], A[1]) not in ((A[2], A[3]), (A[4], A[5])))):
- y = A[1]
- y = y - 1
- A = A[0], y, A[2], A[3], A[4], A[5]
- Anew = A[0], A[1] + 1
- return Anew
- def desnoAtomH1(A):
- while(A[0]>0 and A[0] < 8 and A[1] > 0 and A[1] < 10 and((A[0], A[1]) not in Prepreki) and \
- ((A[0], A[1]) not in ((A[2], A[3]), (A[4], A[5])))):
- y = A[1]
- y = y + 1
- A = A[0], y, A[2], A[3], A[4], A[5]
- Anew = A[0], A[1] - 1
- return Anew
- def doluAtomO(A):
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and \
- ((A[2], A[3]) not in Prepreki) and \
- ((A[2], A[3]) not in ((A[0], A[1]), (A[4], A[5])))):
- X = A[2]
- X = X + 1
- A = A[0], A[1], X, A[3], A[4], A[5]
- Anew = A[2] - 1, A[3]
- return Anew
- def goreAtomO(A):
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and \
- ((A[2], A[3]) not in Prepreki) and \
- ((A[2], A[3]) not in ((A[0], A[1]), (A[4], A[5])))):
- X = A[2]
- X = X - 1
- A = A[0], A[1], X, A[3], A[4], A[5]
- Anew = A[2] + 1, A[3]
- return Anew
- def desnoAtomO(A):
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and \
- ((A[2], A[3]) not in Prepreki) and \
- ((A[2], A[3]) not in ((A[0], A[1]), (A[4], A[5])))):
- Y = A[3]
- Y = Y + 1
- A = A[0], A[1], A[2], Y, A[4], A[5]
- Anew = A[2], A[3] - 1
- return Anew
- def levoAtomO(A):
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and \
- ((A[2], A[3]) not in Prepreki) and \
- ((A[2], A[3]) not in ((A[0], A[1]), (A[4], A[5])))):
- Y = A[3]
- Y = Y - 1
- A = A[0], A[1], A[2], Y, A[4], A[5]
- Anew = A[2], A[3] + 1
- return Anew
- def goreAtomH2(A):
- while (A[4] > 0 and A[4] < 8 and A[5] > 0 and A[5] < 10 and \
- ((A[4], A[5]) not in Prepreki) and \
- ((A[4], A[5]) not in ((A[2], A[3]), (A[0], A[1])))):
- X = A[4]
- X = X - 1
- A = A[0], A[1], A[2], A[3], X, A[5]
- Anew = A[4] + 1, A[5]
- return Anew
- def doluAtomH2(A):
- while(A[4] > 0 and A[4] < 8 and A[5] > 0 and A[5] < 10 and((A[4], A[5]) not in Prepreki) and \
- ((A[4], A[5]) not in ((A[2], A[3]), (A[0], A[1])))):
- X = A[4]
- X = X + 1
- A = A[0], A[1], A[2], A[3], X, A[5]
- Anew = A[4] - 1, A[5]
- return Anew
- def levoAtomH2(A):
- while(A[4] > 0 and A[4] < 8 and A[5] > 0 and A[5] < 10 and((A[4], A[5]) not in Prepreki) and \
- ((A[4], A[5]) not in ((A[2], A[3]), (A[0], A[1])))):
- y = A[5]
- y = y - 1
- A = A[0], A[1], A[2], A[3], A[4], y
- Anew = A[4], A[5] + 1
- return Anew
- def desnoAtomH2(A):
- while(A[4] > 0 and A[4] < 8 and A[5] > 0 and A[5] < 10 and((A[4], A[5]) not in Prepreki) and \
- ((A[4], A[5]) not in ((A[2], A[3]), (A[0], A[1])))):
- y = A[5]
- y = y + 1
- A = A[0], A[1], A[2], A[3], A[4], y
- Anew = A[4], A[5] - 1
- return Anew
- class Molekula(Problem):
- def __init__(self, initial):
- self.initial = initial
- def goal_test(self, state):
- H1x = state[0]
- H1y = state[1]
- Ox = state[2]
- Oy = state[3]
- H2x = state[4]
- H2y = state[5]
- return (H1x + 1 == Ox and Ox + 1 == H2x and Oy == H1y \
- and H2y == Oy)
- def successor(self, state):
- successors = dict()
- H1 = state[0], state[1]
- O = state[2], state[3]
- H2 = state[4], state[5]
- H1new = goreAtomH1(state)
- Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
- successors['GoreH1'] = Statenew
- H1new = doluAtomH1(state)
- Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
- successors['DoluH1'] = Statenew
- H1new = desnoAtomH1(state)
- Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
- successors['DesnoH1'] = Statenew
- H1new = levoAtomH1(state)
- Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
- successors['LevoH1'] = Statenew
- Onew = goreAtomO(state)
- Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
- successors['GoreO'] = Statenew
- Onew = doluAtomO(state)
- Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
- successors['DoluO'] = Statenew
- Onew = levoAtomO(state)
- Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
- successors['LevoO'] = Statenew
- Onew = desnoAtomO(state)
- Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
- successors['DesnoO'] = Statenew
- H2new = goreAtomH2(state)
- Statenew = (H1[0], H1[1], O[0], O[1], H2new[0], H2new[1])
- successors['GoreH2'] = Statenew
- H2new = doluAtomH2(state)
- Statenew = (H1[0], H1[1], O[0], O[1], H2new[0], H2new[1])
- successors['DoluH2'] = Statenew
- H2new = desnoAtomH2(state)
- Statenew = (H1[0], H1[1], O[0], O[1], H2new[0], H2new[1])
- successors['DesnoH2'] = Statenew
- H2new = levoAtomH2(state)
- Statenew = (H1[0], H1[1], O[0], O[1], H2new[0], H2new[1])
- successors['LevoH2'] = Statenew
- return successors
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- H1AtomRedica = int(input())
- H1AtomKolona = int(input())
- OAtomRedica = int(input())
- OAtomKolona = int(input())
- H2AtomRedica = int(input())
- H2AtomKolona = int(input())
- M = (H1AtomRedica, H1AtomKolona, OAtomRedica, OAtomKolona, H2AtomRedica, H2AtomKolona)
- MolekulaInstance = Molekula(M)
- answer = breadth_first_graph_search(MolekulaInstance)
- print (answer.solution())
- **********
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement