Strategi Penyelesaian Masalah

Strategi PenyelesaianMasalah

Strategi Penyelesaian Masalah Untuk membangunkan sistem yang dapat

meyelesaikan sesuatu masalah, perlu bbrpstrategi:

Takrifkan masalah secara tepat

Analisis Masalah

Asingkan dan wakilkan pengetahuan yang perluuntuk penyelesaian masalah

Pilih kaedah penyelesaian masalah yang terbaik

Persoalan terhadap strategipenyelesaian

Adakah penyelesaimasalah terjaminmendapat penyelesaian??

Adalah penyelesai masalahselalunya menamatkanpencarian atauterperangkap dalamkeadaan tak terhingga??

Apabila penyelesaianditemui, adakahpenyelesaian itu optimum?

Apakah kekompleksanproses carian?

Bagaimanamengurangkannya?

Bagaimanamendapatkanpewakilan keadaanyang terbaik?

Graf Ruang Keadaan

Salah satu alatan utama dalam penyelesaianmasalah

mewakilkan masalah dalam bentuk graf ruangkeadaan.

menggunakan teori graf dalam analisis strukturdan kekompleksan masalah dan proses carian.

Graf Ruang Keadaan

Graf terdiri daripada nod dan lintasan/pautanyang menghubungkan pasangan nod.

Micro-world Problems

Graf Ruang Keadaan: ContohBridges of Konisberg Problem

Bandar Konisberg menggunakan dua tebing dandua pulau bagi satu sungai.

Pulau dan tebing sungai dihubungkan dengantujuh jambatan seperti gambarajah.

Masalah jambatan2 Konisberg ialah adakahterdapat laluan mengelilingi bandar yang melintasi setiap jambatan hanya sekali.

Island 1 Island 2

2

5

3

6

1

4

7

Riverbank 2

Riverbank 1

Masalah Bandar Konisberg


The people wondered whether or not one could walk around the city in a way that would involve crossing each bridge exactly once.


Leonhard Euler proposed a problem about this city, a sort of brain teaser:

Walk around the city, crossing each bridge exactly once while ending where you started


Problem 1Try it. Sketch the above map of the city on a sheet of paper and try to 'plan your journey' with a pencil in such a way that you trace over each bridge once and only once and you complete the 'plan' with one continuous pencil stroke.

Having trouble? That's okay, so did Euler. It doesn't seem possible to cross every bridge exactly once. In fact it isn't. To find out why, go to Some failed attempts to solve the problem:

Euler realized that all problems of this form could be represented by replacing areas of land by points (he called them vertices), and the bridges to and from them by arcs. For Konigsberg, let us represent land with red dots and bridges with black curves:

In order to solve the problem, to prove that it was not possible to do this, Euler developed a formal mathematical representation which has the first definition of a graph.

The graph for the city:

A

B

C D

Graf Sistem Jambatan Kronisberg

rb1

b2

i1

b5

rb2

b6b7

i2

b4

b1

Knowledge Representation:Predicate Calculus

connect(i1, i2, b1)connect(rb1, i1, b2)connect(rb1, i1, b3)connect(rb1, i2, b4)connect(rb2, i1, b5)connect(rb2, i1, b6)connect(rb2, i2, b7)

connect(i2, i1, b1)connect(i1, rb1, b2)connect(i1, rb1, b3)connect(i2, rb1, b4)connect(i1, rb2, b5)connect(i1, rb2, b6)connect(i2, rb2, b7)

connect(X, Y, Z)=connect(Y, X, Z)

A Water Jug Problem

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug.

A Water Jug Problem:The state space

Can be described as set of ordered pairs of integers(x, y)x = 0, 1, 2, 3 or 4 x number of gallons of water in the 4- gallon jug

y = 0, 1, 2, or 3 y the quantity of water in the 3- gallon jug

A Water Jug Problem:The state space

(x, y) start state : (0, 0) goal state : (2, n) for any value of n

A Water Jug Problem:The representation

Rules representatione.g. (x, y) (4, y)

if x

A Water Jug Problem:Assumption

can fill a jug from the pump

can pour water out of a jug into the ground

can pour water from one jug to another

there are no other measuring devices

A Water Jug Problem:Rules

Empty the 3-gallon jug on the ground

(x, 0)(x, y)if (y > 0)

6

Empty the 4-gallon jug on the ground

(0, y)(x, y)if(x > 0)

5

Pour some water out of 3-gallon jug

(x, y - d)(x, y)if (y > 0)

4

Pour some water out of the 4-gallon jug

(x d, y)(x, y)if (x > 0)

3

Fill the 3-gallon jug(x, 3)(x, y)if (y < 3)

2

Fill the 4-gallon jug(4, y)(x, y)if (x < 4)

1


Pour all water from 3-gallon juginto 4-gallon jug

(x+y,0)(x, y)if (x+y) 4 and y > 0

9

Pour water from the4-gallon jug into the3-gallon jug until the3-gallon jug is full

(x-(3-y), 3)(x, y)if (x+y) 3 and x > 0

8

Pour water from the3-gallon jug into the4-gallon jug until the4-gallon jug is full

(4, y-(4-x))(x, y)if (x+y) 4 and y > 0

7


Empty the 2 gallons in the 4-gallon jug on the ground

(0,y)(2, y)12

Pour 2 gallonsfrom 3-gallon juginto 4-gallon jug

(2,0)(0, 2)11

Pour all water from 4-gallon juginto 3-gallon jug

(0, x+y)(x, y)if (x+y) 3 and x > 0

10

One solution to the Water Jug Problem

02

20

24

33

03

30

00

Rule AppliedGallons in the 3-Gallon Jug

Gallons in the 4-Gallon Jug

2

92

7

5 or 12

9 or 11

The Water Jugs ProblemHere, the first jug is full (with 20 litres), and the target is to fill the last jug with exactly 4 litres. The two other jugs (of capacity 8 and 5 litres respectively) can be used as intermediate storage.

The Water Jugs Problem

Our study of planning and learning will parallel the study of problem solving. You will first modify and extend the rulesyou wrote for the Water Jug problem and then the Missionaries and Cannibals problem.

The Traveling Salesman Problem

Seorang jurujualmempunyai 5 bandaruntuk dilawati dan mestipulang keasal.

Gol bagi masalah ini ialahmencari laluan terpendekuntuk pengembaraanjurujual , melawati setiapbandar dan pulang kebandar permulaan.

100AB

C

D

E

75

50100

100125

125125

7550


nod graf mewakili bandar

setiap lintasan dilabel dengannilai pemberat menandakankos melalui lintasan tersebut

kos ini boleh mewakili jarakyang perlu utk laluan keretaatau kos laluan penerbanganantara dua bandar

100AB

C

D

E

75

50100

100125

125125

7550


laluan [A, D, C, B, E, A] dengan kos 450 km adalahsatu contoh litar yang mungkin.

Gol memerlukan satu litaryang lengkap dengan kosyang minimum

100AB

C

D

E

75

50100

100125

125125

7550

The Traveling Salesman ProblemKemungkinan Penyelesaian

A

A A A

B

B

C

C

C

C

D

D

D

D

E

E

E E

E E

The Traveling Salesman ProblemKemungkinan Penyelesaian

Application:

Optimization and Scheduling problems

Monkey & Banana Problems

There is a monkey at the door into a room. In the middle of the room a banana is hanging from the ceiling. The monkey is hungry and wants to get the banana, but he cannot stretch high enough from the floor. At the window of the room there is a box that the monkey can use.

The monkey can perform the following actions: walk on the floor, climb the box, push the box around (if he is already at it), and grasp the banana if he is standing on the box and directly underneath the banana. Can the monkey grasp the banana? http://www.compapp.dcu.ie/~alex/LOGIC/monkey.html

Monkey & Banana ProblemsThe monkey and banana problem is a famous problem studied in the community of logical programming. Instead of the programmer explicitly specifying the path for the monkey to reach the banana, the computer actually reasons out a possible way that the monkey reaches the banana.

grab to get the banana climb to get onto the box walk for the monkey to move push to push the box to some other position.

move( initial state, type of move, resulting state )

The 8 Puzzle

1 2 3

8 4

7 6 5

The 8 PuzzleRuang Keadaan

1 4 3

5 8 2

7 6

1 3

5 8 2

7 64

1 4 3

5 8 2

67

1 4 3

5 2

7 68

1 4 3

5 8 2

7 6

1 3

5 8 2

7 64

4 3

5 8 2

1 67

1 3

5 8 2

7 64

1 4 3

5 2

7 68

1 4 3

8 2

5 67

1 4 3

5 2

7 68

1 4 3

5 8

7 26

1 4

5 8 2

7 36

up left downright

left right up down left right up down

Strategi Carian Ruang Keadaan

Carian Data-Driven Carian Goal-Driven Carian Dalam Dahulu (Depth First) Carian Melebar Dahulu (Breadth First) Carian Heuristik

Strategi Penyelesaian Masalah

Documents

Transcript of Strategi Penyelesaian Masalah