CT002-3-2 AI Methods

Overview of Module
 Learning outcomes:

On successful completion of this module, you should be

able to:

• 1. Design and implement a system that models / simulates

intelligent behaviour

• 2. Able to analyse and appraise areas related to artificial intelligence

and recommend a suitable solution

• 3. Explain different AI techniques in terms of the solutions that they

offer to a particular problem in a particular context

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Assessment Methods and Types

• Group In-course assignment weighted at 50%

with 30% of the total contributed by an individual
component.

• An Exam length 2 hours weighted at 50%

(Section A & Section B) – format to be discussed
during revision week.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Topics in AI Methods

• Computational Problem Solving

• Machine Learning
• Introduction to Robotics
• Introduction to Natural Language Processing
• Artificial Immune System and algorithm
• Swarm Intelligence, technique and application

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Main references supporting the
course
Essential Reading
• Callan R (2005), Artificial Intelligence, Macmillan, Basingstoke,
(ISBN: 0333801369)
• Luger GF & Stubblefield WA (2004), Artificial Intelligence, Addison-
Wesley-Longman, Reading, USA, (ISBN: 0321263189)

Further Reading
• Russell S and Norvig P (1995), Artificial Intelligence: A Modern
Approach, Prentice Hall, New Jersey, USA, (ISBN: 0137903952)

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Contact & Consultation

Hema Latha Krishna Nair

Lecturer, CSSE Group

Email: [email protected]

Handphone No : 012 7030510

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 CT002-3-2 AI Methods

Computational Problem Solving

 Overview of the Chapter

• History of Computational.
• Computational Problem : Software Development Model Steps.
• Types of Computation Model : Decision Problem, Search
Problem & Optimizing Problem.
• Computational Algorithm
• Solution in computational

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Learning Outcomes

• To understand the concept of computational problems

• To discuss a common practice in AI : Turing Test &
Travelling Salesman Problem approach
• To understand and able to explain each type of
Computational Problems Solving techniques
• To identify the steps of solution in computational
• To describe computational algorithm

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 History
With this kind of computational power, it
might seem anything is possible. But
mathematicians in the 1920s and 30s
wondered if perhaps some computers could
solve problems that other computers
couldn’t. A young Alan Turing answered this question in the
negative by proposing an ideal computer that we now call a
Turing Machine and then proving that this machine could
perform any mathematical procedure that could be represented by
an algorithm.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Turing Test (act like humanly)
To pass this test requires:
natural language processing
knowledge representation
automated reasoning
machine learning

A total Turing test would require the program to also use:

computer vision
robotics

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Quantifiers

There are 4 quantifiers are required for this computational

solving :
1. Size / complexity of hypothesis space
2. Accuracy to which target concept must be approximated
3. The probability that the learner will be output a
successful hypothesis
4. The manner which examples of training are presented to
the learner.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Step of Computational Solving

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 CONCEPT

A (computational) problem: an infinite set of

possible instances with a question.
Example
•REACHABILITY
– INSTANCE: A graph (V,E) and nodes v,u ∈
V.
– QUESTION: Is there a path in the graph from
v to u?

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Understand the concept
• Problem may comes in 2 forms; certain and uncertain. To
solve it you may need considerate some questions :

a) What condition the particular algorithm assured of learning

successful?
b) Is it possible to identify classes of learning problems that are
inherently difficult or easy ?
c) Can 1 characterize the number of training example necessary and
sufficient to assure successful learning?
d) How if learner allow to pose new query?
e) How to categorize the number of mistakes will make after learning
target function?
Notes : Refreshment : Probability Theory

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Travelling Salesman Problem
The traveling salesman problem consists of a salesman and a set of cities.

The salesman has to visit each one of the cities starting from a certain one (e.g. the
hometown) and returning to the same city.

The challenge of the problem is that the traveling salesman wants to minimize the total
length of the trip.

The traveling salesman problem can be described as follows:

TSP = {(G, f, t): G = (V, E) a complete graph,
f is a function V×V → Z,
t ∈ Z,
G is a graph that contains a traveling salesman tour with cost that does
not exceed t}.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Travelling Salesman Problem

Figure 1: A graph with weights (distance)on the edges

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Travelling Salesman Problem

P = {A, B, C, D, E} is a Hamiltonian cycle.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Computational Problems – Further
Derived

• Different types of computational problems

• Examples of computational problems
• Relationships between problems

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Different types of computational
problems
 Decision problem:
A decision problem has only two possible outputs, yes or no (or alternately 1 or 0)
on any input.

 Search (function) problem:

given an instance find a solution (object satisfying certain properties).

 Optimization problem:
given an instance find a best solution according to some cost criterion.

 Counting problem:
given an instance count the number of solutions.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Type of Computational Problem :
Decision Problems
• A decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any input.
• a decision problem is a question in some formal system with a yes-or-no answer, depending on the values
of some input parameters. E.g :
The problem "given two numbers x and y, does x evenly divide y?"

The answer can be either 'yes' or 'no',

and depends upon the values of x and y.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Type of Computational Problem :
Search (Function) Problems

• given an instance find a solution (object

satisfying certain properties),
• It is a type of computational problem
represented by a binary relation.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Type of Computational Problem :
Search Problems

EXAMPLE:

Case: Finding the PATH

INSTANCE: A graph (V,E) and nodes v,u ∈ V.
QUESTION: Find a path from v to u

The problem consists in finding a structure (v..u) in an object V.

An algorithm is said to solve the problem if it behaves in the following
way: if at least one corresponding structure exists, then one occurrence
of this structure is the output; otherwise, the algorithm stops with an
appropriate output.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Search Problem definitions

• A search problem is defined by:

a) A set of states
b) A start state
c) A goal state or goal test
d) A boolean function which tells us whether a given state is a
goal state
e) A successor function
f) Line a mapping from a state to a set of new states

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Search Problems : Method
• Generic search algorithm: given a graph, start nodes, and goal
nodes, incrementally explore paths from the start nodes.
• Maintain a frontier of paths from the start node that have been
explored.
• As search proceeds, the frontier expands into the unexplored
nodes until a goal node is encountered.
• The way in which the
frontier is expanded
defines the search
strategy.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Type of Computational Problem :
Optimization Problem
• An optimization problem is the problem of finding the best
solution from all feasible solutions.
• given an instance find a best solution according to some cost
criterion.
• Typically this is formalized by specifying
– what are feasible solutions for an instance and
– a cost function which assigns a cost (typically a integer/real number) to each
feasible solution.
• A solution to an optimization problem instance is a feasible
solution that has the minimal (or maximal) cost.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Examples of Optimization Problem
EXAMPLE:

Case: FIND SHORTEST PATH

INSTANCE: A graph (V,E) and nodes v,u ∈ V.
QUESTION: Find a shortest path from v to u.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Optimization Problems
• In computer science, interesting optimization problems
usually have the above properties and are therefore NPO
problems.
• A problem is additionally called a P-optimization (PO)
problem, if there exists an algorithm which finds optimal
solutions in polynomial time.
• Often, when dealing with the class NPO, one is interested
in optimization problems for which the decision versions
are NP-hard.
• Note that hardness relations are always with respect to
some reduction.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Solving Optimization Problems

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Type of Computational Problem :
Counting Problem
given an instance count the number of
solutions.

EXAMPLE:

CASE: No of PATH
INSTANCE: A graph (V,E) and nodes v,u ∈ V.
QUESTION: Count the number of simple paths from v to u

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Examples of Methods for Difficult
Computational problems
• Many problems are computationally easy:
– there is a polynomial time algorithm for the problem, i.e. there is an
algorithm solving.

• Some problems are not computationally easy:

– there is no known solution.
– DEDUCTION OF ANSWER MAY GO INFINITE

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 PROBLEM 1

SAT (Boolean Satisfiability Problem)

INSTANCE: a (boolean) propositional formula in conjunctive normalform
QUESTION:
•(D) Is the formula satisfiable?
•(S) Find a satisfiable truth assignment for the formula.
•(O) Find a truth assignment satisfying the most clauses in the formula.

Propositional formulas consist of literals (variables and their negations),

conjunctions (“and” ∧) and disjunctions (“or” ∨).
Conjunctive normal form: conjunction of disjunctions (=clauses)

x1 ∧(x2 ∨ ¬x2)

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 SAT (Boolean Satisfiability Problem)

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 PROBLEM 2
GRAPH COLORING

INSTANCE: A graph (V,E) and a positive integer k

QUESTION:
•(D) Is there a k-coloring of the graph, i.e. an assignment of one of
•the k colors to each vertex such that vertices connected with an
•edge do not have the same color?
•(S) Find a k-coloring.
•(O) Find an l-coloring with the smallest number l of colors.

CLIQUE (CORELATION)
INSTANCE: A graph (V,E) and a positive integer k
QUESTION:
•(D) Is there a k-clique in the graph, i.e. a set of k nodes such that
•there is an edge between every pair of vertices from the set.
•(S) Find a k-clique.
•(O) Find an l-clique with the largest number l of vertices.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 PROBLEM 3

TSP (TRAVELING SALESPERSON)

INSTANCE: n cities 1,...,n and a nonnegative integer distance dij between any
two cities i and j (such that dij = dji) and a positive integer B.

QUESTION:
•(D) Is there a tour of length at most B, i.e. a permutation π of the cities
such that the length n

∑ dπ(i)π(i+1)
i=1
– is at most B (where π(n+1) = π(1))?
– (S) Find a tour of length at most B.
– (O) Find the shortest tour of the cities.

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Travelling Salesman Problem –
Solution in context of Decision &
Optimisation
A TSP(O) algorithm using a TSP(D) algorithm as a subroutine:
/*Find the cost C of an optimal tour by binary search*/
C:= 0; Cu := D; /* D is the sum of maximal distances from each city */
while (Cu > C) do
if there is a tour of cost ⌊(Cu +C)/2⌋ or less then
Cu := ⌊(Cu +C)/2⌋
else
C := ⌊(Cu +C)/2⌋+1;
endif
/* Find an optimal tour given the cost C of an optimal tour */
For every intercity distance d(i,j) do
set the distance to C +1;
if
there is a tour cost C or less, freeze the distance to C +1
else
restore the original distance and add (i,j) to the tour;
endfor

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Other Travelling Salesman
Problem – Solution

• Using the triangle inequality to solve

the traveling salesman problem .

• A heuristic solution proposed by Karp

• Greedy Algorithm

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Relationship between different
kinds of problems

Decision problems vs search problems

•A decision problem reduces to the corresponding search problem trivially, i.e., if a search
problem can be solved efficient so can the corresponding decision problem.
•But also a search problem reduces to the corresponding decision problem.

Decision problems vs OPTIMISATION problems

Consider TSP(D) vs TSP(O)

If TSP(O) can solved in polynomial time, then so can TSP(D).
If TSP(D) can solved in polynomial time, then so can TSP(O).
An optimal tour can be found using an algorithm which
- finds the cost C of an optimal tour by binary search (with a polynomial number of calls to the
polynomial time algorithm for TSP(D));
- finds an optimal tour using C (with a polynomial number of calls to
the polynomial time algorithm for TSP(D)).

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Using Polynomial time reduction

• A decision problem P is said to be complete for a set of

dicision problem S , if P is a member of S and every
problem in S can be reducted to P.

• Complete decision problem can be used in

computational complexity satisfiability.

Note : Check example of Boolean

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Combinatorial Optimization

(I,f,m,g) : I is a set of instances;

• given instance xẸ I, f(x) is set of feasible
• given instance R and feasible solution y of x m(x,y)
denote the measure of y usually positive real and g is the
goal either min or max
So conclusion :

M(x,y) = g {m(x,y’)|y’ f(x)}

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Algorithm design techniques for
complex problems
• There are several approaches to developing efficient
algorithms
• for computationally challenging problems such as:
– Identify special cases (using tools from complexity theory) and
– develop special algorithms for these
◮ approximation algorithms
◮ randomized algorithms
• However, it typically requires a substantial amount of
expertise and resources to develop an efficient algorithm
for a problem

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 Q and A

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods
 • Next topic :

Machine Learning

CE00371-1: Introduction to Software Development Problem Solving using programmed solutions

CT002-3.5-2 AI-Methods