# Announcements

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

## Documents

Published:

Views: 2 | Pages: 27

Share
Related documents
Description
Want to cross a river using one canoe. Canoe can hold up to two people. ... will show number of cannibals, missionaries and canoes on each side of the river. ...
Tags

## canoes

Transcript
Title: Announcements 1 Announcements
• Homework 1 due today write up on The Thinking Machine
• Department Picnic Thursday, September 13 120 to 230
• Lab 0 due Thursday, September 13
• Writing Assignments Posted
• Caves of Steel due 10/4
• Current Events Presentation
• 2 Representations Semantic Nets, Frames, and Trees
• Lecture 3
• 3 The Need for a Good Representation
• A computer needs a representation of a problem in order to solve it.
• A representation must be
• Efficient not wasteful in time or resources.
• Useful allows the computer to solve the problem.
• Meaningful really relates to the problem.
• 4 Semantic Nets
• A graph with nodes, connected by edges.
• The nodes represent objects or properties.
• The edges represent relationships between the objects.
• Label to indicate nature of relationship
• 5 A Simple Semantic Net 6 Create a Semantic Net
• A Ford is a type of car. Bob owns two cars. Bob parks his car at home. His house is in California, which is a state. Sacramento is the state capital of California. Cars drive on the freeway, such as Route 101 and Highway 81.
• 7 Your Semantic Web 8 Inheritance
• Inheritance is the process by which a subclass inherits properties from a superclass.
• Example
• Mammals give birth to live young.
• Fido is a mammal.
• Therefore Fido gives birth to live young.
• In some cases, as in the example above, inherited values may need to be overridden. (Fido may be a mammal, but if hes male then he probably wont give birth).
• 9 Frames
• A frame system consists of a number of frames, connected by edges, like a semantic net.
• Class frames describe classes.
• Instance frames describe instances.
• Each frame has a number of slots.
• Each slot can be assigned a slot value.
• 10 Frames A Simple Example 11 Other relationships
• Aggregation one object being part of another object
• Fido has a tail
• Association explains how objects are related to each other
• "chases relationship" how Fido and Fang are related
• 12 Create a frame-based representation
• A Ford is a type of car. Bob owns two cars. Bob parks his car at home. His house is in California, which is a state. Sacramento is the state capital of California. Cars drive on the freeway, such as Route 101 and Highway 81.
• 13 Your Frame-Based Representation 14 Why Are Frames Useful?
• Used as a data structure by Expert Systems
• All information about an object stored in one place
• As opposed to rule-based systems
• In real world systems frames have a large number of slots
• Searching for all relevant information would take a long time
• 15 Search Space
• A set of possible choices in a given problem
• One or more are the solution to the problem
• Identify one or more goals
• Identify one or more paths to those goals
• Problem
• set of states
• states connected by paths that represent actions
• 16 Search Trees
• Semantic trees a type of semantic net.
• Used to represent search spaces.
• Root node has no predecessor.
• Leaf nodes have no successors.
• Goal nodes (of which there may be more than one) represent solutions to a problem.
• 17 Search Trees An Example
• A is the root node.
• L is the goal node.
• H, I, J, K, M, N and O are leaf nodes.
• There is only one complete path
• A, C, F, L
• 18 Example Missionaries and Cannibals
• Three missionaries and three cannibals
• Want to cross a river using one canoe.
• Canoe can hold up to two people.
• Can never be more cannibals than missionaries on either side of the river.
• Aim To get all safely across the river without any missionaries being eaten.
• 19 A Representation
• The first step in solving the problem is to choose a suitable representation.
• We will show number of cannibals, missionaries and canoes on each side of the river.
• Start state is therefore
• C3,M3,B1 0,0,0
• 20 A Simpler Representation
• In fact, since the system is closed, we only need to represent one side of the river, as we can deduce the other side.
• We will represent the finishing side of the river, and omit the starting side.
• So start state is
• 0,0,0
• 21 Operators
• Now we have to choose suitable operators that can be applied
• Move one cannibal across the river.
• Move two cannibals across the river.
• Move one missionary across the river.
• Move two missionaries across the river.
• Move one missionary and one cannibal.
• 22 The Search Tree
• Cycles have been removed.
• Nodes represent states, edges represent operators.
• There are two shortest paths that lead to the solution.
• 23 What Other Representations are Possible? 24 Combinatorial Explosion
• Problems that involve assigning values to a set of variables can grow exponentially with the number of variables.
• Some such problems can be extremely hard to solve (NP-Complete, NP-Hard).
• Reduce state space
• select good representation help
• using heuristics (see chapter 4).
• 25 Problem Reduction
• Breaking a problem down into smaller sub-problems (or sub-goals).
• Can be represented using goal trees (or and-or trees).
• Nodes in the tree represent sub-problems.
• The root node represents the overall problem.
• Some nodes are and nodes, meaning all their children must be solved.
• 26 Problem Reduction Example
Recommended

1 page

32 pages

1 page

1 page

11 pages

6 pages

6 pages

7 pages

5 pages

9 pages

26 pages

28 pages

14 pages

17 pages

17 pages

View more...