COS3109 Artificial Intelligence (AI)

COS3109
Artificial Intelligence (AI)
What is Artificial Intelligence?
• Intelligence is the ability to understand

and learn things.
• Intelligence is the ability to think and
understand instead of doing things by
instinct or automatically.
(Essential English Dictionary, Collins,
London, 1990)
COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 1

(cont’d)
• In order to think, someone or something
has to have a brain, or an organ that
enables someone or something to learn
and understand things, to solve problems
and to make decisions.
• So we can define intelligence as the ability
to learn and understand, to solve problems
and to make decisions.

(cont’d)
• The goal of artificial intelligence (AI) as a
science is to make machines do things
that would require intelligence if done by
humans.

Turing Test
• One of the most significant papers on
machine intelligence, “Computing
Machinery and Intelligence”, was written
by the British mathematician Alan Turing
over fifty years ago.
• He asked: Can machines think?
Turing Test (cont’d)

• In the first phase, the interrogator, a man
and a woman are each placed in separate
rooms.
• The interrogator’s objective is to work out
who is the man and who is the woman by
questioning them.
• The man should attempt to deceive the
interrogator that he is the woman, while
the woman has to convince the
interrogator that she is the woman.
6


• In the second phase of the game, the man
is replaced by a computer programmed to
deceive the interrogator as the man did.
• It would even be programmed to make
mistakes and provide fuzzy answers in the
way a human would.
• If the computer can fool the interrogator as
often as the man did, we may say this
computer has passed the intelligent
behaviour test.


• Although modern computers still cannot
pass the Turing test, it provides a basis for
the verification and validation of
knowledge-based systems.
• A program thought intelligent in some
narrow area of expertise is evaluated by
comparing its performance with the
performance of a human expert.
10

• To build an intelligent computer system,
we have to capture, organise and use
human expert knowledge in some narrow
area of expertise.
11
ปัญญาประดิษฐ์ คอื อะไร

ความหมาย
• ศาสตร์แขนงหนึ่งของวิทยาการคอมพิวเตอร์ ที่ตอ้ งการประดิษฐ์
เครื่ องจักร เช่น คอมพิวเตอร์ หรื อหุ่นยนต์ ให้สามารถคิดและมี
พฤติกรรมเลียนแบบมนุษย์ในกระบวนการตัดสิ นใจแก้ไขปัญหาได้ ซึ่ง
อาจจะต้องมีการวินิจฉัย หาเหตุผล จากความรู ้ที่จดั เก็บไว้ และนําความรู ้
นั้นมาเชื่อมโยงเพื่อหาข้อสรุ ปหรื อผลลัพธ์ของปัญหานั้นได้ในที่สุด
12

A bridged history of AI
• 1943 McCulloch & Pitts: Boolean circuit model of brain
• 1950 Turing's "Computing Machinery and Intelligence"
• 1956 Dartmouth meeting: "Artificial Intelligence" adopted
• 1952—69 Look, Ma, no hands!
• 1950s Early AI programs, including Samuel's checkers
program, Newell & Simon's Logic Theorist,
Gelernter's Geometry Engine
• 1965 Robinson's complete algorithm for logical reasoning
• 1966—73 AI discovers computational complexity
Neural network research almost disappears
• 1969—79 Early development of knowledge-based systems
• 1980-- AI becomes an industry
• 1986-- Neural networks return to popularity
• 1987-- AI becomes a science
• 1995-- The emergence of intelligent agents
13
Intelligent behavior
• Learn or understand from experience
• Make sense out of ambiguous or
contradictory message
• Respond quickly and successfully to a
new situation
• Use reason in solving problems and
directing conduct effectively
• Deal with perplexing situations
14

Intelligent behavior (cont’d)
• Understand and infer in ordinary, rational
ways
• Apply knowledge to manipulate the
environment
• Acquire and apply knowledge
• Think and reason
15
การประยุกต์ ใช้ ปัญญาประดิษฐ์ ในศาสตร์ แขนงอืน่ ๆ

1. หุ่นยนต์ (Robotic)
2. งานทีเ่ ป็ นแบบแผน (Formal task)
3. ระบบผู้เชี่ยวชาญ (Expert System : ES)
4. การประมวลผลภาษาธรรมชาติ (Natural Language
Processing : NLP) และ เทคโนโลยีเสี ยง (Voice Speech
Techology)
5. คอมพิวเตอร์ โครงข่ ายใยประสาท (Neural Computing)
16

หุ่นยนต์ (Robotic)
เป็ นเครื่ องจักรกลไฟฟ้ า ที่มนุษย์ประดิษฐ์ข้ ึนมา
เพื่อให้ทาํ งานหรื อกิจกรรมบางอย่างโดยอัตโนมัติแทน
มนุษย์
ความฉลาดของหุ่นยนต์
- มีอุปกรณ์รับความรู ้สึก (Sensory System)เช่น กล้อง
- ทําการแปลผลสารสนเทศที่เก็บรวบรวมไว้แล้ว
- ทําการตอบสนองและปรับตัวให้เข้ากับการ
เปลี่ยนแปลงของสภาพแวดล้อมได้ดีกว่าการทําตาม
คําสัง่ เพียงอย่างเดียว
17
ตัวอย่ างหุ่นยนต์
อาซิโม(ASIMO) หุ่นยนต์เลียนแบบมนุษย์ของบริ ษทั ฮอนดาสามารถเดิน

และวิ่งได้อย่างอิสระเสรี ขึ้นบันไดและเต้นรําได้ มีระบบบันทึกเสี ยงเพื่อตอบ
สนองคําสัง่ มนุษย์ จดจําใบหน้าคู่สนทนาได้อย่างแม่นยํา
18

หุ่นยนต์ดินสอ โดยคุณเฉลิมพล ปุณโณทกประธานเจ้าหน้าที่บริ หาร บริ ษทั ซี ที เอเชีย โรโบติกส์ จํากัด
https://www.thairath.co.th/content/1285166
ระบบปั ญญาประดิษฐ์ เป็ นตัวช่ วยสั่งการทํางานน้องดินสอมินิให้ดูแลผูส้ ู งอายุอย่างมีประสิ ทธิ ภาพ
โดยมีความสามารถเฝ้ าและแจ้งเตือน เพื่อป้ องกันการล้มของผูส้ ู งอายุ โดยจะแจ้งไปที่สมาร์ ทโฟน
ผ่านแอปพลิเคชันดินสอ, แพทย์สามารถสอบถามอาการแบบเห็นภาพผ่านหุ่ นยนต์ สั่งหันกล้องพื่อดู
ภาพมุมต่างๆได้, มี ปุ่มเรี ยกผูด้ ูแล หรื อเรี ยกรถพยาบาลฉุ กเฉิ น, เตือนให้ทานยา ให้วดั ความดัน, มี
ฟั งก์ชนั ชวนสวดมนต์, ฟั งเพลง พร้อมมีเกมฝึ กสมองชะลอความจําเสื่ อม
19
งานทีเ่ ป็ นแบบแผน (FORMAL TASK)
1 Games
- Chess
- Backgammon
- Go
2 Mathematics
- Geometry
- Logic
- Integral calculus
20

ระบบผู้เชี่ยวชาญ (Expert System : ES)
ความหมาย
โปรแกรมคอมพิวเตอร์ที่ใช้ในการนําเสนอองค์ความรู ้ของผูเ้ ชี่ยวชาญ
เพื่อแก้ปัญหาและให้คาํ แนะนําอย่างเป็ นเชิงเหตุและผล
21
องค์ ประกอบและโครงสร้ างการทํางานของระบบผู้เชี่ยวชาญ
ฐานองค์ ความรู้
ข้ อเท็จจริง (Facts) (Knowledge Based)
ผู้ใช้
(USER) กลไกวินิจฉัยสรุปความ
ความเชี่ยวชาญ
(Expertise) (Inference Engine)
22

การประมวลผลภาษาธรรมชาติ และ เทคโนโลยีเสี ยง
การประมวลผลภาษาธรรมชาติ เป็ นการติดต่อสื่ อสารระหว่างผูใ้ ช้

กับเครื่ องคอมพิวเตอร์ โดยที่ผใู ้ ช้สามารถนําเข้าข้อมูลด้วยเสี ยงพูด
ซึ่ งอาจจะเป็ นภาษาอังกฤษ หรื อภาษาใดก็ได้ตามที่ผพู ้ ฒั นาได้
โปรแกรมไว้
23
ตัวอย่ างซอฟต์ แวร์

ทีม่ กี ารประมวลผลภาษาธรรมชาติ
Speak to Mail Speech Recognition เป็ นโปรแกรมสนับสนุนการ
ทํางานของโปรแกรมรับ ส่ งอีเมล์ ที่จะช่วยให้การรับส่ งอีเมล์ของ
ผูใ้ ช้มีความสะดวกสบายมากยิง่ ขึ้น ด้วยความสามารถในการ
สัง่ งานด้วยเสี ยง ให้โปรแกรมพิมพ์ขอ้ ความ จัดการกับ Address
Book หรื อสมุดที่อยู่ และแนบไฟล์ไปกับอีเมล์ นอกจากนี้ ยัง
สามารถคัดลอกข้อความไปยังโปรแกรมประมวลผลคํา เช่น
Microsoft word
24

25
คอมพิวเตอร์ โครงข่ ายใยประสาท (Neural Computing)

หมายถึ ง คอมพิวเตอร์ ที่สามารถเลี ยนแบบการทํางานของสมอง
มนุ ษย์ได้ ด้วยการประมวลผลข้อมูลสารสนเทศ และองค์ความรู ้ได้
ในคราวละมาก ๆ นอกจากนี้ ยังสามารถรับและจดจําสารสนเทศใน
รู ปแบบที่เป็ นประสบการณ์ได้ ทําให้สามารถเชื่ อมโยงข้อเท็จจริ ง
เข้าด้วยกันเพื่อหาข้อสรุ ป และใช้ประสบการณ์ที่จดั เก็บไว้มาเรี ยนรู ้
และทําความเข้าใจว่า ข้อเท็จจริ งใหม่ที่ได้รับเข้ามามีความเกี่ยวข้อง
กันอย่างไร เพื่อทําการปรั บปรุ งองค์ความรู ้ ให้มีความทันสมัยเพื่อ
ประโยชน์ในอนาคต
26

ตัวอย่ างซอฟต์ แวร์
NeuroXL Predictor เป็ นซอฟต์แ วร์ ที่ พ ฒ
ั นาขึ้ น โดยใช้
เทคโนโลยีโครงข่ายใยประสาทเสมือนร่ วมกับกระดาษคํานวณ
อิเล็กทรอนิกส์ของโปรแกรม Ms Excel เพื่อเป็ นเครื่ องมือการ
วิเคราะห์และพยากรณ์ต่าง ๆ ด้านธุรกิจ
27
28

Q&A
29

Problem Solving with techniques
in Artificial Intelligence
การแก้ปัญหาด้วยเทคนิคทางปัญญาประดิษฐ์
เทคนิคในการแก้ ปัญหาของ Formal task
COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 1

ปัญหาควรมีลกั ษณะดังนี้
• ปัญหามีสถานะจุดเริ่ มต้นที่แน่นอนหรื อสามารถกําหนดได้วา่ จุดใด

คือจุดเริ่ มต้น
• ปัญหามีขอ้ กําหนดของการเปลี่ยนสถานะ (State) หากใช้กฎใดๆ
จะทําให้มีการเปลี่ยนสถานะ (State) จากสถานะหนึ่งไปยังสถานะ
อื่นๆได้
• ปัญหามีสถานะสิ้ นสุ ด หรื อเป้ าหมาย
วิธีการแก้ ปัญหาแบบห้ วงสถานะ

(State space search)
• เป็ นวิธีหนึ่งที่ใช้แก้ปัญหา Formal Task
• คือการกําหนดให้ปัญหามีสถานะเริ่ มต้น (Initial State) และมี
สถานะสิ้ นสุ ด (Final State)
• มีขอ้ กําหนดของการเปลี่ยนสถานะ
• การแก้ปัญหา คือการหาทางเปลี่ยนสถานะจากสถานะเริ่ มต้น
ไปยังสถานะสิ้ นสุ ด
• เทคนิคที่หาทางเปลี่ยนสถานะอาจทําให้ได้ผลลัพธ์ที่แตกต่าง
กัน 4

สิ่ งทีต่ ้ องทําในการแก้ ปัญหา
1. นิยามปั ญหาอย่างชัดเจน แสดงสถานการณ์ปัจจุบนั
(initial situation), สถานการณ์สิ้นสุ ด (final situation)
2. วิเคราะห์ปัญหา
3. หาความรู ้ที่ใช้ในการแก้ปัญหาว่ามีอะไรบ้าง
4. เลือกเทคนิคแก้ปัญหาที่เหมาะสม
ขั้นตอนการแก้ ปัญหาแบบห้ วงสถานะ

• นิยามปัญหาอย่างชัดเจน แสดง objects ทั้งหมดที่เกี่ยวข้องกับ
ปัญหา
• สถานการณ์เริ่ มต้น (Initial situation) ให้สถานะเริ่ มต้น (initial
state) แทนตําแหน่งเริ่ มต้น
• สถานการณ์สิ้นสุ ด (Final situation) ให้สถานะสิ้ นสุ ดหรื อ
สถานะเป้ าหมาย (final state or goal stage) แทนตําแหน่ง
สุ ดท้าย
• หากฏที่ใช้เปลี่ยนสถานะจากสถานะหนึ่งไปอีกสถานะหนึ่ง
• เลือกใช้โครงสร้างเพื่อการแก้ปัญหา
• เลือกเทคนิคการแก้ปัญหาที่เหมาะสม 6

1. การกําหนดนิยามให้ กบั ปัญหา
• คือ การอธิ บายลักษณะปัญหาเพื่อที่จะหาวิธีการแก้ไข
• ตัวอย่างที่ 1: ปัญหาคนโทนํ้า กําหนดให้มีคนโทนํ้า 2 ใบ ใบแรกมี
ความจุ 4 ลิตร และใบที่สองมีความจุ 3 ลิตร จะทําอย่างไรให้คนโทนํ้า
ใบแรกนี้มีน้ าํ อยู่ 2 ลิตรพอดี โดยไม่มีเครื่ องตวงวัดใดๆ
ใบแรก ความจุ 4 ลิตร ใบที่สอง ความจุ 3 ลิตร ใบแรก มีน้ าํ จุ 2 ลิตร

7
การกําหนดนิยามของปัญหาคนโทนํา้
1. ค่าของโอกาสต่างๆ ที่จะเกิดขึ้นในแต่ละสถานะ กําหนดให้ ตัวแปร
x แทนปริ มาณนํ้าในคนโทนํ้าใบแรก และ y แทนปริ มาณนํ้าใน
คนโทใบที่สอง
จะได้วา่ x = 0, 1, 2, 3, 4 (ใบแรกความจุ 4 ลิตร)
y = 0, 1, 2, 3 (ใบที่สองความจุ 3 ลิตร)

การกําหนดนิยามของปัญหาคนโทนํา้ (ต่ อ)
2. กําหนดจุดเริ่ มต้นและสิ้ นสุ ดการแก้ปัญหา
- สถานะเริ่ มต้น กําหนดให้สถานะเริ่ มต้นของปัญหานี้คือ ไม่มีน้ าํ ใน
คนโทนํ้าทั้งสองใบ ดังนั้นเราจึงใช้คู่อนั ดับ
(x,y) = (0,0)
- สถานะสิ้ นสุ ด ต้องการให้เหลือนํ้าในคนโทนํ้าใบแรกเพียง 2 ลิตร
ส่ วนคนโทนํ้าใบที่สองจะเหลือความจุเท่าใดก็ได้
(x,y) = (2,n)
3. กฎที่อธิ บายปัญหานั้นๆ
- ใส่ น้ าํ ในคนโทใบแรกจนเต็ม
- ใส่ น้ าํ ในคนโทใบที่สองจนเต็ม
- เทนํ้าบางส่ วนออกจากคนโทใบแรก
- เทนํ้าบางส่ วนออกจากคนโทใบที่สอง
เปลี่ยนกฎให้เป็ นเงื่อนไขที่ง่ายต่อการนําไปใช้จะได้ดงั นี้
10

กฎการผลิต (Production rule)
ลําดับกฏ กฎ คําอธิบาย
1. (X,Y: X < 4) -> (4,Y) เติมนํ้าลงในคนโทนํ้าใบแรกจนเต็ม
2. (X,Y: Y < 3) -> (X,3) เติมนํ้าลงในคนโทนํ้าใบที่สองจนเต็ม
3. (X,Y: X > D) -> (X-D,Y) เทนํ้าบางส่วนออกจากคนโทใบแรก
4. (X,Y: Y > D) -> (X,Y-D) เทนํ้าบางส่วนออกจากคนโทใบที่สอง
5. (X,Y: X > 0) -> (0,Y) เทนํ้าออกจากใบแรกจนหมด
6. (X,Y: Y > 0) -> (X,0) เทนํ้าออกจากใบที่สองจนหมด
7. (X,Y: X+Y >= 4^Y > 0) -> เทนํ้าจากคนโทใบที่สองใส่ใบแรกจนเต็ม โดยที่คนโท
(4, Y-(4-X)) นํ้าทั้งสองใบมีน้ าํ รวมกันมากกว่าหรื อเท่ากับ 4 ลิตร
8. (X,Y: X+Y >= 3^X > 0) -> เทนํ้าจากคนโทใบแรกใส่ใบที่สองจนเต็ม โดยที่คนโท
(X-(3-Y),3) นํ้าทั้งสองใบมีน้ าํ รวมกันมากกว่าหรื อเท่ากับ 3 ลิตร
9. (X,Y: X+Y <= 4^Y > 0) -> เทนํ้าจากคนโทใบที่สองมาใส่ในใบแรก โดยที่คนโท
(X+Y,0) นํ้าทั้งสองใบมีน้ าํ รวมกันน้อยกว่าหรื อเท่ากับ 4 ลิตร
10. (X,Y: X+Y <= 3^X > 0) -> เทนํ้าจากคนโทใบแรกใส่ใบที่สอง โดยที่คนโทนํ้าทั้ง
(0,X+Y) สองใบมีน้ าํ รวมกันน้อยกว่าหรื อเท่ากับ 3 ลิตร 11
ข้ อสั งเกตในการกําหนดนิยามของปัญหา
1. การเขียนกฎมีองค์ประกอบพื้นฐานอย่างน้อย 2 ส่ วนคือ
• ส่ วนที่ใช้ตรวจสอบเงื่อนไข (condition)
• ข้อสรุ ป (conclusion)
ส่ วนเงื่อนไข -> ส่ วนข้อสรุ ป
เช่น (X,Y: X < 4) -> (4,Y)
ภายใต้เงื่อนไขของ X และ Y ที่มี X น้อยกว่า 4 ลิตร (X,Y: X < 4) จะ
สรุ ปว่ามีน้ าํ อยู่ 4 ลิตรในคนโทใบแรกและมีน้ าํ ไม่ทราบจํานวนใน
คนโทใบที่สอง (4,Y)
• กฎการผลิต (Production rule)
12

ข้ อสั งเกตในการกําหนดนิยามของปัญหา (ต่ อ)
2. การกําหนดค่า X และ Y จะต้องครอบคลุมถึงความเป็ นไปได้
ทั้งหมดซึ่ งค่าของ X และ Y เรี ยกว่าสถานะ (state)
เช่น X = 0, 1, 2, 3, 4 และ Y = 0, 1, 2, 3
3. ในการกําหนดขั้นตอนต่างๆของการแก้ปัญหาเรี ยกว่าห้วงสถานะ
(state space) ซึ่ งกําหนดว่าห้วง (space) หนึ่งๆอย่างน้อยต้องมี
2 สถานะคือ สถานะเริ่ มต้น (initial state) และสถานะ
เป้ าหมาย (goal state หรื อ final state)
เช่น (0,0) เป็ นสถานะเริ่ มต้น และ (2,n) เป็ นสถานะเป้ าหมาย
13
ขั้นตอนการเลือกกฏแสดงด้วยโครงสร้างต้นไม้
สถานะเริ่ มต้น
การหาเหตุผลแบบเดินหน้ า (Forward Reasoning)
14

ตัวอย่ างการแก้ ปัญหาคนโทนํา้
ระบบการผลิต (production system)
ลําดับที่ คนโทนํ้าใบแรก คนโทนํ้าใบที่สอง กฏข้อที่ สถานะ
1. 0 0 - สถานะเริ่ มต้น
2. 0 3 2
3. 3 0 9
4. 3 3 2
5. 4 2 7
6. 0 2 5
7. 2 0 9 สถานะสิ้ นสุ ด
15
ตัวอย่ าง: ปัญหา 8-Puzzle

ปัญหา 8-Puzzle ประกอบด้วยถาดขนาด 3x3 ซึ่ งภายในบรรจุแผ่น
ป้ ายขนาด 1x1 จํานวน 8 แผ่นในแต่ละแผ่นจะมีหมายเลขแสดง
และมีช่องว่างอยูห่ นึ่งช่องที่แผ่นป้ ายสามารถเลื่อนเข้ามาแทนที่ได้
ปัญหาคือให้เลื่อนแผ่นป้ ายเหล่านี้จากตําแหน่งเริ่ มต้นให้เป็ น
ตําแหน่งสุ ดท้ายซึ่ งเป็ นคําตอบ
ตําแหน่งเริ่ มต้น ตําแหน่งสิ้ นสุ ด

16

การกําหนดนิยามของปัญหา 8-Puzzle
• กําหนดจุดเริ่ มต้นและสิ้ นสุ ดการแก้ปัญหา
- สถานะเริ่ มต้น [2,4,1; 8,5,6; 3, ,7]
- สถานะสิ้ นสุ ด [1,2,3; 8, ,4; 7,6,5]
• กฏที่อธิ บายปัญหานั้นๆ (Operators)
– แผ่นป้ ายหนึ่งๆจะเลื่อนมาที่ช่องว่างได้ถา้ อยูต่ ิดกับ
ช่องว่าง และสถานะจะเปลี่ยนจากสถานะเดิมไปยัง
สถานะใหม่ซ่ ึงตําแหน่งของแผ่นป้ ายสลับที่กบั ตําแหน่ง
ของช่องว่าง
17
การกําหนดนิยามของปัญหา 8-Puzzle (ต่ อ)

1. ด้านบนของช่องว่างมีแผ่นป้ าย -> สลับตําแหน่งของช่องว่างกับแผ่นป้ าย
2. ด้านขวาของช่องว่างมีแผ่นป้ าย -> สลับตําแหน่งของช่องว่างกับแผ่นป้ าย
3. ด้านล่างของช่องว่างมีแผ่นป้ าย -> สลับตําแหน่งของช่องว่างกับแผ่นป้ าย
4. ด้านซ้ายของช่องว่างมีแผ่นป้ าย ->สลับตําแหน่งของช่องว่างกับแผ่นป้ าย
18

องค์ ประกอบของการแก้ ปัญหา
ด้ วยวิธีการค้ นหาแบบห้ วงสถานะ (State Space)
1. รู ปแบบโครงสร้างข้อมูลที่ใช้ในการค้นหา
2. การกําหนดทิศทางสําหรับการค้นหา
3. การแสดงความรู ้
4. กระบวนการในการเลือกกฏ
5. การค้นหา (Search)
19
1. รูปแบบโครงสร้ างข้ อมูลทีใ่ ช้ ในการค้ นหา

โครงสร้ างกราฟ คือเซ็ตของโหนด (nodes) และ เส้นเชื่อม (edge) ที่ใช้
เชื่อมระหว่างโหนดเข้าด้วยกัน แต่ละโหนดจะมีชื่อประจําโหนดเพื่อแยก
ความแตกต่างระหว่างโหนดออกจากกัน ในเส้นเชื่อมอาจมีคาํ อธิบายหรื อค่า
เพื่อบ่งบอกถึงคุณสมบัติของเส้นเชื่อมนั้นๆ เช่น ค่า cost ของเส้นทางที่เชื่อม
ระหว่างโหนด เส้นเชื่อมอาจมีการระบุทิศทาง (directed) จะเรี ยกกราฟที่มี
เส้นเชื่อมระบุทิศทางว่า กราฟระบุทิศทาง (directed graph)
A D E
Nodes = {A,B,C,D,E} B C
Arcs = {(A,B),(C,B), (C,D), (D,A), (E,C), (E,D)} 20

รูปแบบโครงสร้ างข้ อมูลทีใ่ ช้ ในการค้ นหา(ต่ อ)
โครงสร้ างต้ นไม้ คือกราฟต่อเนื่อง (connected) ที่ไม่มีวฏั จักร (acyclic)
และไม่มีทิศทาง (undirected graph) ต้นไม้จดั เป็ นโครงสร้างข้อมูลแบบ
ลําดับชั้น (hierarchical data structure) ที่ประกอบด้วยโหนด (node)
จํานวน n โหนด โดย n เป็ นจํานวนเต็มใดๆที่มีค่ามากกว่าหรื อเท่ากับ
ศูนย์ และเมื่อ n มีค่าเป็ นศูนย์ เรี ยกต้นไม้ดงั กล่าวว่า ต้นไม้วา่ ง (empty
tree)
A
B C D
E F 21
2. การกําหนดทิศทางสํ าหรับการค้ นหา

ในการแก้ไขปัญหาหนึ่งในระบบห้วงสถานะนั้น เราจะมีสถานะเริ่ มต้น
ของปั ญหาจากนั้นจึงใช้วิธีการต่างๆเพื่อเปลี่ยนสถานะให้นาํ ไปสู่เป้ าหมาย
ของความสําเร็ จทิศทางการเปลี่ยนสถานะเพื่อแก้ปัญหาทําได้ 2 ทิศทาง
สถานะเริ่ มต้น
1. Forward reasoning
A B C
–จุดเริ่ มต้น+ การใช้กฏ-> เป้ าหมาย
E เป้ าหมาย เป้ าหมาย
2. Backward reasoning A B C
เป้ าหมาย+ การใช้กฏ-> จุดเริ่ มต้น
E สถานเริ่ มต้น 22

3. การแสดงความรู้
• แสดงความรู ้ให้อยูใ่ นรู ปที่สามารถสื่ อให้มนุษย์เข้าใจได้ และ

คอมพิวเตอร์กเ็ ข้าใจได้เช่นกัน
• ปัญหาคนโทนํ้า
– (2,0)
– ตัวเลขแรกคือระดับนํ้าในคนโทใบแรก
– ตัวเลขที่สองคือระดับนํ้าในคนโทใบที่สอง
23
4. กระบวนการในการเลือกกฏ
การทําดัชนี (Indexing) จะเหมาะสมสําหรับการแสดงความรู ้ใน
ระบบการผลิต ที่วิธีการเปลี่ยนสถานะต่างๆได้ถูกกําหนดไว้เป็ น
เงื่อนไขไว้ก่อน
• หากฎทุกข้อที่มีส่วนของเงื่อนไขตรงกับเงื่อนไขที่วางเอาไว้ใน
สถานะปัจจุบนั แล้วดึงเอากฎทุกข้อนั้นออกมาเปรี ยบเทียบหา
คําตอบ
24

4. กระบวนการในการเลือกกฎ(ต่ อ)
25
5. การค้ นหา (Searching)

• การค้นหาวิธีการเปลี่ยนสถานะหรื อค้นหาคําตอบ
• แบ่งออกเป็ น 2 แบบ
– การแก้ปัญหาด้วยการค้นหา (Problem Solving by Searching)
– การแก้ปัญหาด้วยการค้นหาแบบฮิวริ สติก (Problem Solving by
Heuristic Search)
26

การค้ นหาแบบกว้ าง (Breadth-First Search)
- ทุกโหนดที่อยูใ่ นระดับเดียวกันของต้นไม้จะถูกตรวจสอบก่อนโหนดที่อยู่
ระดับถัดไป
- เริ่ มด้วยการสร้างโหนดให้กบั สถานะเริ่ มต้นก่อนและตรวจสอบหาโหนด
เป้ าหมาย ถ้าเจอก็ถือว่าการค้นหาสิ้ นสุ ด ถ้าไม่พบโหนดเป้ าหมายให้สร้างโหนด
ลูกต่อลงไป
B C
D E F G 27
Algorithm: Breadth-First Search

1. Create a variable called NODE-LIST and set it to the initial state
2. Until a goal state is found or NODE-LIST is empty:
(a) Remove the first element from NODE-LIST and call it E. If
NODE-LIST was empty, quit.
(b) For each way that each rule can match the state described in E do:
(i) Apply the rule to generate a new state,
(ii) If he new state is a goal state, quit and return this state.
(iii) Otherwise, add the new state to the end of NODE-LIST
28

Problem Solving by Searching
Block World Problem คือปัญหาที่จะต้องการจัดวางกล่องให้
เรี ยงลําดับกันอยูบ่ นโต๊ะดังตัวอย่างข้างล่างนี้สาํ หรับ
เงื่อนไขก็คือ
1. กล่อง X ที่ไม่มีกล่องอื่นทับอยูส่ ามารถนํามาวางบนโต๊ะได้
2. กล่อง X และ Y ไม่มีกล่องอื่นทับ สามารถนํา X มาทับบน
Y ได้
A
A B
C B C
สถานะเริ่ มต้น สถานะเป้ าหมาย 29
Breadth-First
1
Search (ตัวอย่ าง)
A
CB
2 3 A 4
C
ACB CB A
B
B B C C B
AC AC AB AB A
5 6 7 8 9 C
C A
B B
A C
10 11
(Goal)
30

การค้ นหาแบบลึก (Depth-First Search)
คือวิธีการที่วิเคราะห์และสร้างโหนดลูกทางด้านซ้ายขึ้นมาก่อน จากนั้นจึง
ตรวจสอบว่าโหนดที่สร้างขึ้นมานั้นสามารถกระจายสร้างโหนดลูกได้อีก
หรื อไม่ จะสังเกตเห็นเป็ นการกระจายในแนวดิ่ง เราจึงเรี ยกว่า Depth-First
Search
31
Algorithm: Depth-First Search

1. If the initial state is a goal state, quit and return success.
2. Otherwise, do the following until success or failure is signaled:
(a) Generate a successor, E, of the initial state. If there are no more
successors, signal failure.
(b) Call Depth-First Search with E as the initial state.
(c) If success is returned, signal success. Otherwise continue in this
loop.
32

Depth-First Search (ตัวอย่ าง)
1 A
C B
2
A C B
A B
C B A C
3 5
B B
A A C 6
C
4
A
B (Goal)
C
33
ข้ อดีของ Breadth-First Search

• จะไม่ติด path ที่ลึกมากๆ โดยไม่พบคําตอบ
• ถ้ามีคาํ ตอบ รับรองว่าต้องพบอย่างแน่นอน
• ถ้ามีหลายคําตอบ จะได้คาํ ตอบที่มีข้นั ตอนการดําเนินการสั้นที่สุดก่อน
เนื่องจากเส้นทางที่ส้ นั กว่าจะถูกพิจารณาก่อน
34

ข้ อดีของ Depth-First Search
• ใช้หน่วยความจําน้อยกว่า Breadth-First Search เพราะใน current path
เท่านั้นที่ถูกเก็บ
• ถ้าโชคดี Depth-First Search จะพบคําตอบโดยไม่ตอ้ งค้นหา space มากเกิน
ความจําเป็ น แต่ถา้ เป็ น Breadth-First Search states ที่อยูใ่ นระดับ n จะต้อง
ค้นหาถูกกระจายออกมาให้หมดก่อนที่จะไปกระจายโหนดในระดับ n+1
35
แบบฝึ กหัด
มีพระ 3 รู ป และคนป่ า 3 คนมาถึงฝั่งแม่ นํา้ ต้ องการจะข้ ามไปยังฝั่ง
ตรงข้ าม โดยใช้ เรื อหนึ่งลํา แต่ ละรอบบรรทุกได้ ครั้ งละสองคน ซึ่ ง
ต้ องมีคนพายเรืออยู่หนึ่งคน ในแต่ ละฝั่งของแม่ นํา้ หากมีจํานวนคน
ป่ ามากกว่ าพระ พระจะถูกกิน จงหาวิธีข้ามแม่ นํ้าไปยังฝั่งตรงข้ าม
โดยให้ ท้งั หมดไปถึงและไม่ ให้ พระถูกคนป่ ากิน
36

สิ่ งทีต่ ้ องทําในการแก้ ปัญหา
1. นิยามปั ญหาอย่างชัดเจน แสดงสถานการณ์ปัจจุบนั
(initial situation), สถานการณ์สุดท้าย (final situation)
2. วิเคราะห์ปัญหา
3. หาความรู ้ที่ใช้ในการแก้ปัญหาว่ามีอะไรบ้าง
4. เลือกเทคนิคแก้ปัญหาที่เหมาะสม
37
Q&A
38

Heuristic Search /
Informed Search
• Hill-Climbing
• Best-First Search
• A*
Heuristic Search เป็ นเทคนิคที่ใช้ เพิ่มประสิทธิภาพของกระบวนการ Search

โดยยอมให้ ขาดความสมบูรณ์ (Completeness) คือ อาจไม่พบคําตอบก็ได้
หากความรู้ที่ใช้ ในการแก้ ปัญหาไม่สมบูรณ์
องค์ ประกอบของ Heuristic Search

Heuristic Function เป็ นฟั งก์ชนั ที่แสดงว่า โหนดไหนเป็ นโหนดที่น่า เป็ นโหนดที่เข้ า
ใกล้ โหนดเป้าหมายมากที่สดุ (ค่ายิ่งมากเท่าไรยิ่งมีโอกาสจะเปลี่ยนเป็ น goal state มาก
เท่านัน้ ถ้ ากําหนดว่าค่ามากคือค่าที่ดี)
- ถ้ า Heuristic Function ดี จะไม่กระจายโหนดที่ไม่นําไปสู่ goal state ออกมา

ถ้ า Heuristic Function ไม่ดีก็อาจให้ การค้ นหาผิดทิศทางได้
Heuristic Function ใช้ ความรู้ในในปั ญหานันเพื

้ ่อเป็ นแนวทางในการให้ คา่ ความดี
ของโหนดต่างๆ (แต่เป็ นเพียงการคาดเดาเท่านัน)
้

ตัวอย่าง Heuristic Function: Block World Problem
1
A A
A B CB
C B C
-1 -1 A -1
C
ACB CB A
B
B B C C B
AC AC AB AB
h1: Heuristic Function คือ บวก 1 แต้ม
A
C
-1 1 -3 -3 -1
ให้กบั ทุก Block ที่วางอยูบ่ นสิ่ งที่ C A
มันควรอยู่ และลบหนึ่งแต้มถ้าไม่ใช่ B
A
B
C
-3 3
(Goal)
Hill Climbing
อัลกอริ ทมึ นี ้จะเปรี ยบเทียบการปี นเขา โดยมีแนวคิดว่าโหนดใหม่ที่จะ

ถูก generate จะต้ องมีคา่ Heuristic ที่ดีกว่าโหนด
ปั จจุบนั
HILL

ALGORITHM: Hill Climbing
1. Evaluate initial state
IF initial state = goal state THEN คืนค่า initial state และ quit
ELSE current state := initial state
2. UNTIL พบ goal state หรื อ ไม่มี operator ที่ใช้เปลี่ยน current state ได้ DO
2.1 เลือก operator ที่ยงั ไม่ได้ใช้กบั current state เพื่อผลิต new state
2.2 Evaluate new state
IF new state = goal state THEN คืนค่า new state และ quit
ELSE IF ค่า heuristic ของ new state ดีกว่า
THEN current state := new state
ELSE IF ค่า heuristic ของ new state ไม่ดีกว่า THEN ทําต่อ (ไปทําข้อ
2.1 ต่อเพื่อสร้างโหนดใหม่ในระดับเดียวกัน)
5
Steepest-Ascent Hill-Climbing
การทํางานคล้ าย Hill-Climbing แต่ตา่ งตรงที่ steepest-ascent จะสร้ างโหนดลูก
ทุกตัวออกมาก่อน แล้ วค่อยเลือกตัวที่ดีที่สดุ ของลูกทังชุ
้ ด
1. ตรวจสอบสถานะเริ่ มต้ น ถ้ าสถานะเริ่มต้ นนี ้คือสถานะเป้าหมาย ให้ แสดง
คําตอบและยกเลิกการทํางาน แต่ถ้าสถานะเริ่มต้ นไม่ใช่สถานะเป้าหมาย
ให้ เปลี่ยนสถานะนี ้เป็ นสถานะปั จจุบนั และทําต่อข้ อ 2
2. ทําตามกระบวนการข้ างล่างนี ้จนกว่าจะพบคําตอบ หรื อจนกระทัง่ คาดว่า
ไม่สามารถหาคําตอบได้
2.1 ให้ BVAL เป็ นสถานะที่ไม่วา่ สถานะลูกใดๆที่เกิดใหม่จะต้ องดีกว่า
สถานะนี ้

Steepest-Ascent Hill-Climbing (ต่ อ)
2.2 สําหรับตัวดําเนินการที่จะใช้ กบั สถานะปั จจุบนั แต่ละตัวให้ ดําเนินการ
ดังนี ้
2.2.1 สร้ างสถานะใหม่จากสถานะปั จจุบนั
2.2.2 ตรวจสอบสถานะใหม่ ถ้ าเป็ นคําตอบให้ แสดงผลและเลิกการ
ทํางาน ถ้ าไม่ใช่ให้ เปรี ยบเทียบสถานะใหม่กบั BVAL ถ้ าสถานะใหม่
ดีกว่า ให้ สถานะใหม่นี ้เป็ น BVAL ถ้ าไม่ดีกว่าไม่ต้องทําอะไร
2.2.3 เปลี่ยนตัวดําเนินการตัวใหม่ ที่ยงั ไม่ได้ ใช้ งานและกลับไปทําข้ อ
2.2.1
2.3 ถ้ า BVAL ดีกว่าสถานะปั จจุบนั ให้ สถานะปั จจุบนั คือ BVAL
ลักษณะของ Hill-Climbing
อาจไม่พบคําตอบ เนื่องจาก Heuristic Function ไม่ดี
Local Maximum : อาจได้ path ที่ดีกว่าเส้ นทางรอบข้ างแต่ไม่ใช่ path ที่

ดีที่สดุ
Plateau: อาจพบกรณี Search space เป็ นพื ้นที่ราบสูง เช่นในกรณีที่

โหนดลูกทังหมดที
้ ่กําลังถูก evaluate มีคา่ เท่ากับโหนดของตัวมันเอง
Ridge: อาจพบกรณี Ridge (สันเขา) คือการเลือก Generate โหนดที่ให้

ค่า Heuristic ที่ดี ค่า heuristic นี ้ถูกคาดหวังว่าจะนําพาไปสูค่ ําตอบของ
การแก้ ปัญหา เมื่อสร้ างโหนดต่อไปเรื่ อยๆ ถึงจุดหนึง่ ปรากฏว่าไม่มีคา่ ที่
ดีกว่าอีกต่อไปและขณะนันก็ ้ ยงั ไม่พบคําตอบด้ วย ดังนัน้ จึงเป็ นเพียง
แค่การเดินไปในทางที่คาดว่าจะดีแต่ไม่พบเป้าหมาย อาจแก้ ไขได้ โดย
การสุม่ เลือกสร้ างโหนดเริ่มต้ นใหม่โดยไม่เลือกโหนดเดิมที่เคยถูกสร้ าง 8
มาแล้ ว

Best-First Search
- การทํางานคล้ ายๆ กับ Hill-climbing โดยมีข้อแตกต่างคือ
- ในกรณีของ Hill-climbing จะเลือก state ที่ดีที่สดุ และเดินทางไป
ทางนัน้ โดยที่ states อื่นๆ ที่ถกู สร้ างจาก parent state เดียวกันจะ
ถูกทิ ้งไป แต่ในกรณีของ Best-First Search จะเก็บค่า states
เหล่านี ้ไว้ เพื่อใช้ ในอนาคต เมื่อ path ที่เดินไปไม่ดีเท่ากับ states
เหล่านี ้
- Hill-climbing อาจจะหยุดเมื่อไม่พบค่าที่ดีขึ ้น (กรณีที่ไม่เลือกสุม่ โหนด
อื่นอีก) แต่ Best-First Search, state ที่มีคา่ Heuristic ที่
ดีที่สดุ ในปั จจุบนั จะถูกเลือกแม้ วา่ จะมีคา่ ไม่ดีเท่า states ที่เคยเลือกมาก็
ตาม
ALGORITHM: Best-First
Search
Best-First Search Algorithm
1. OPEN = {initial state}
2. UNTIL (พบ goal state หรื อ ไม่มี state อยูใ่ น OPEN ) DO
2.1 ดึง state ที่ heuristic ที่มีคา่ ดีที่สดุ ออกจาก OPEN
2.2 สร้ างโหนดลูกทุกโหนดของ state นัน้
2.3 สําหรับโหนดลูกแต่ละตัว
2.3.1 IF โหนดลูก ยังไม่เคยถูกสร้ างขึ ้นมาเลย THEN
เติม โหนดลูกนันใน ้ OPEN และจํา parent state ไว้
2.3.2 IF โหนดลูกนันเคยถู้ กสร้ างขึ ้นมาแล้ วและ path ใหม่นี ้ดีกว่าเดิม
THEN เปลี่ยน parent state และ update cost ใหม่
10

ตัวอย่าง: Best-First Search
A A A
step1
B 3 C 5 D 1 B 3 C 5 D 1
step2
step3 E 4 F 6
A A
B 3 C 5 D 1 B 3 C 5 D 1
step5
G 6 H 5 E 4 F 6 G 6 H 5 E 4 F 6
step4
I 2 J 1
11
A* Algorithm (A-Star Algorithm)
- Best-First Search เป็ น algorithm อย่างง่ายของ A*

- Heuristic Function ของ BFS คือ F(s) = h(s) คือความดีของ
state ปัจจุบนั ไปยัง goal state
-Heuristic Function ของ A*: ผสมเอาค่าความดีของเส้นทางจาก
initial state มายัง current state และ จาก current state ไป
ยัง goal state ด้วย F’(s) = g(s) + h’(s)
A* แตกต่างจาก Best-First Search การใช้ ฟังก์ชนั g ที่ไม่เพียงแค่ประมาณค่าจาก
จุดปั จจุบนั ไปยังเป้าหมาย หากยังเพิ่มการประมาณค่าจากจุดเริ่มต้ นมายังจุด
ปั จจุบนั ด้ วย โดยการใช้ g( ) state ที่ประมาณว่าใกล้ goal state มากที่สดุ อาจจะไม่
ถูกกระจายก็ได้
12

initial state current state (s) goal state
g h'
f'(s) = g(s) + h'(s) I

โดยที่ g คือฟั งก์ชนั ที่คํานวณค่า cost จาก g(s)
initial state ถึง current state
F’(s) = g(s) + h’(s)
h’ คือฟั งก์ชนั ที่ประมาณ(estimate) ค่า
cost จาก current state ถึง goal state
f’ คือ ฟั งก์ชนั ที่ประมาณค่า cost จาก
initial state ถึง goal state (state ที่ดีจะมี h’(s)
ค่า f’ น้ อย) F
13
A* Algorithm (cont’d)
1. ถ้า g(n) คือค่า cost ของทางเดินที่เหมาะสมจากโหนดเริ่ มต้นถึงโหนดปั จจุบนั (n)
ดังนั้นในภาวะเริ่ มต้น g(เริ่ มต้น) = 0 และให้ OPEN เป็ นรายการของโหนด ซึ่ ง
ในภาวะเริ่ มต้นนี้จะมีเฉพาะโหนดเริ่ มต้นเท่านั้นให้หาค่า h’(เริ่ มต้น)
2. เลือกโหนด N ที่อยูใ่ นรายการของ OPEN ที่มีค่าของ [g(n) + h’(n)] น้อยที่สุด ถ้า
N คือโหนดเป้ าหมาย ทางเดินของ N คือทางเดินเป้ าหมายที่เหมาะสม ซึ่ งมีค่า
cost เท่ากับ g(N) ถ้าหากว่าใน OPEN ไม่มีโหนดอยูเ่ ลยแสดงว่าไม่มีทางเดิน
เป้ าหมายในกราฟนี้
3. ย้าย N ออกจาก OPEN หาโหนดลูกทั้งหมดของ N แล้วเพิ่มเข้าไปในรายการ
ของ OPEN และสําหรับทุกๆโหนดของโหนดลูก (S) ให้หาค่า g(s) จาก
g(s) = g(N) + ค่า cost จาก N ถึง S
4. ย้อนกลับไปทําขั้นตอนที่ 2
14

A* มีคุณสมบัตนิ ี ้
1. h’(s) = 0 เมื่อ s คือ goal state

2. ถ้า h’ เป็ นฟังก์ชนั ที่ประมาณค่า cost ที่ไม่เกินค่า cost ของฟังก์ชนั h
(h คือฟังก์ชนั ที่หาค่า cost จาก current state ถึง goal state โดยที่ค่า
cost ที่ได้มานั้นเป็ นค่าที่นอ้ ยที่สุด) เราจะรับรองได้วา่ path ที่ได้จาก
ฟังก์ชนั f’() นั้นจะเป็ น Optimal path เสมอ
15
ตัวอย่ างการหาเส้ นทางการเดินทางจากเมืองหนึ่งไปยังอีกเมืองหนึ่งโดยใช้

ระยะทางที่สัน้ ที่สุด
Arad ไป Bucharest
Straight-line
Distance
การรับรองว่า h’(n) จะไม่เกินค่า h(n) ในที่น้ ี

จะใช้ Straight-line Distance คือทางตรงที่
ประมาณขึ้น
16

A* search example
ขั้นตอนการทํางานของ A* เริ่ มจากจุดเริ่ มต้นของเมืองคือ Arad
17
A* search example
การกระจายโหนดเพื่อเลือกการเดินทางจากเมือง Arad ไป Bucharest

A* คือ f(s) = g(s) + h’(s)
18

A* search example
Heuristic function ของ A* คือ f(s) = g(s) + h’(s) เมื่อ g คือระยะทางที่เดินผ่านมา

และ h’(n) คือระยะทางตรงที่ประมาณได้
19
A* search example
20

A* search example
21
A* search example
22

Q&A
23

การแสดงความรู้ ใ นปั ญญาประดิษฐ์
ขัน้ ตอนที่เ กี่ยวข้ อ งกับ ความรู้ ข องระบบปั ญญาประดิษฐ์
1.การ อ นุ ม าน คื อ กระบวนการของระบบปั ญ ญาประดิ ษ ฐ์ ในการ

พิจารณาความรู้ที่มีอยูใ่ นระบบเพื่อหาเหตุผลโดยใช้ การวิเคราะห์เพื่อหา
ค่าความจริ ง
2. วิธ ีก ารแสดงความรู้ คือวิธีการที่จะนํา เอาความรู้ ที่มนุษย์เข้ าใจ (ใน

ความเข้ าใจของแต่ละคน) มาแสดงในรูปแบบที่จะทําให้ มนุษย์(คนอื่น)
และคอมพิวเตอร์ ให้ สามารถเข้ าใจและประมวลผลกับความรู้นนได้ ั้
1
COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D.
วิธ ีก ารแสดงความรู้ ท างตรรกศาสตร์
Propositional Logic แสดงความรู ้โดย

Logical
Representation สัญลักษณ์ทางตรรกศาสตร์ โดยแสดงค่า
ความจริ ง และเท็จเท่านั้น สัญลักษณ์
Propositional Logic First-Order logic เหล่านี้ได้แก่ P,Q แทนประโยคทาง
หรื อ Predicate
Logic ตรรกศาสตร์, ตัวเชื่อม และเครื่ องหมาย
เพรดดิเคตลอจิก (Predicate Logic) วงเล็บ “( )” เช่น (P^Q) ->R
- เพิ่มเติมความสามารถของ Propositional
Logic โดยยอมให้มีตวั แปร และ ประโยคแสดง
ความสัมพันธ์ของวัตถุได้
- อธิบายความจริ งในโลกนี้ได้ดียงิ่ ขึ้น
เช่น Man(Marcus)
3
การแสดงความรู้ด้วย Propositional Logic

• แสดงค่าความจริ ง และเท็จเท่านั้น
• สัญลักษณ์เหล่านี้ได้แก่ P,Q แทนประโยคทางตรรกศาสตร์, ตัวเชื่อม
, , , ,  และเครื่ องหมายวงเล็บ “( )” เช่น (P^Q) ->R
•ลักษณะและข้อสังเกต
- แสดงค่าความจริ ง/เท็จ เท่านั้น
- สัญลักษณ์ P,Q แทนประโยคทางตรรกศาสตร์
- ลําดับของความหมายในประโยคถูกกําหนดด้วยวงเล็บ
- ประโยคที่ซบั ซ้อนถูกสร้างโดย นําเอาประโยคความเดียว หลายๆ
ประโยคมารวมกัน เช่น ( P  (Q  R))  (R  P)
2
Propositional logic: Syntax
• Propositional logic is the simplest logic – illustrates
basic ideas
• The proposition symbols S, S1 and S2 are sentences
– If S is a sentence, S is a sentence
– If S1 and S2 are sentences, S1  S2 is a sentence
– If S1 and S2 are sentences, S1  S2 is a sentence
– If S1 and S2 are sentences, S1  S2 is a sentence
– If S1 and S2 are sentences, S1  S2 is a sentence
BNF(Backus-Naur Form)
Sentence -> AtomicSentence
| ComplexSentence
AtomicSentence -> True | False | Symbol
Symbol -> P | Q | R | . . .
ComplexSentence ->  Sentence
| (Sentence Sentence)
| (Sentence  Sentence)
| (Sentence  Sentence)
| (Sentence  Sentence)
ไวยากรณ์ ของ propositional logic
3
Logical equivalence
ตัวอย่ าง
ตัวอย่างของประโยคทัว่ ไปที่แสดงเป็ นประโยคทางตรรกศาสตร์
This car is red P
This telephone is red Q
If the car is red and the telephone is red then I’m happy P^Q->R
•Tom is man P ข้ อ จํากัด

•John is man Q
•All men are strong R สาเหตุ
* ความรู้ถกู แสดงแยกจากกัน
-ตอบคําถามนี ้ได้ หรื อไม่ * ไม่สมั พันธ์กนั
-Tom ก็เป็ นผู้ชาย เช่นเดียวกับ John ใช่หรื อไม่?
-Tom เป็ นผู้ชายที่แข็งแรงหรื อไม่? 8
4
การตรวจสอบค่ าความจริงในการแสดงความรู้แ บบเพรดดิเ คต
การตรวจสอบค่ าความจริง
Propositional Logic Predicate Logic
Truth Resolution Unification +

Table Resolution
ภาพ แสดงการตรวจสอบค่าความจริงในการแสดงความรู้
แบบต่างๆ
9
ตารางค่าความจริ ง (Truth Table)
10
5
อํานาจจําแนก (Resolution)
winter  summer
~winter  cold
winter หรื อ ~winter เป็ นจริ งที่ใดที่หนึ่งเท่านั้น ลดรู ปได้ summer  cold
ถูกใช้เพื่อการหาค่าความจริ งของกลุ่มของประพจน์ในการแสดงความรู ้แบบ
Propositional Logic
มีข้ นั ตอนดังนี้
1. แต่ละประพจน์ของ F ( F เป็ นเซ็ตของประพจน์) จะต้องถูกทําให้อยูใ่ นรู ปของอนุ
ประโยค (Clause form)
Clause form คือ รู ปของประโยคที่เชื่อมกันด้วยเครื่ องหมาย “และ” หรื อ ”หรื อ” เช่น
P->Q ทําให้อยูใ่ นรู ป Clause form จะได้ ~PVQ
2. ทํา S ( S เป็ นประโยคที่ตอ้ งการทดสอบค่าความจริ ง) ให้เป็ นอนุประโยคและ
เปลี่ยนให้เป็ นค่า Negation (~S)
3. ทําตามขั้นตอนดังแสดงนี้
11
a  b  a  b
(p)  p
(a  b)  a  b
(a  b)  a  b
12
6
Conversion to clause form
α  β : B1,1  (P1,2  P2,1)
1. Eliminate , replacing α  β with (α  β)(β  α).

(B1,1  (P1,2  P2,1))  ((P1,2  P2,1)  B1,1)
2. Eliminate , replacing α  β with α β.

(B1,1  P1,2  P2,1)  ((P1,2  P2,1)  B1,1)
3. Move  inwards using de Morgan's rules and double-

negation:
(B1,1  P1,2  P2,1)  ((P1,2  P2,1)  B1,1)
4. Apply distributivity law ( over ) and flatten:

(B1,1  P1,2  P2,1)  (P1,2  B1,1)  (P2,1  B1,1)
13
ตัวอย่างของวิธี Resolution
ฐานความรู ้ ของ Propositional Logic
ลําดับ ประพจน์ รูปอนุประโยค
1 P P
2 (P^Q)->R ~P V ~Q V R
3 T->Q ~T V Q
4 T T ต้ องการพิสจู น์วา่ R เป็ นจริงหรื อไม่
โดยเปลี่ยนเป็ น ~R
~PV~QVR (2)
~R สมมติฐาน
~PV~Q resolvent
P (1)
~Q resolvent
~T V Q (3)
~T resolvent
T (4)
14
7
Q&A
15
8
การแสดงความรู้ ใ นปั ญญาประดิษฐ์
การแสดงความรู้ด้วย เพรดดิเคตลอจิก
การแสดงความรู้ด้วย เพรดดิเคตลอจิก
เนื่องจากการแสดงความรู้ด้วยวิธี Propositional Logic ไม่สามารถ
อธิบายความจริ งในโลกความเป็ นจริงได้ ทงหมด ั้ และยังไม่สามารถอธิบาย
ความสัมพันธ์ของสิง่ ต่างๆได้ ดังนันจึ
้ งมีการแสดงความรู้อีกแบบหนึง่ ที่ชื่อว่า
เพรดดิเคต
เพรดดิเคต หรื อ เพรดดิเคตลอจิก (Predicate Logic) หรื อ เพรดดิเค
ตแคลคูลสั (Predicate Calculus) หรื อ เฟริสท์ออร์ เดอร์ เพรดดิเคตลอจิก
(First-order Predicate Logic) หรื อ เฟริสท์ออร์ เดอร์ ลอจิก (First-order Logic)
หมายถึงวิธีการแสดงความรู้แบบเดียวกันหมด
ประโยคในภาษามนุษย์ ประโยคภาษาตรรกศาสตร์
เรี ยกว่า
ประพจน์ (Proposition)
2
1
การแสดงความรู้ด้ วยเพรดดิเ คตลอจิก
1. ชุดตัวอักษร (Alphabet)
- ค่าคงที่
- ตัวแปร
- ฟังก์ชนั (f,g,h) เช่น father(CHAD) พ่อของ CHAD,
mother(father(CHAD)) ย่าของ CHAD
2.เพรดดิเคต (Predicate) คือส่ วนแสดงความสัมพันธ์ของวัตถุต่างๆ เช่น
FATHER(SOMCHAI,SOMSRI)
3. ตัวเชื่อมในเพรดดิเคต (Connective Symbols) เช่นเครื่ องหมาย (, , , , )
หรื อ (V,^,->,=,~)
4. ตัวบ่งปริ มาณ (Quantifier) (, ) หรื อ (for all, for some)
3
การแสดงความรู้ด้ วยเพรดดิเ คตลอจิก
5. ภาษาในเพรดดิเคต เรากําลังพิจารณาว่าลักษณะของประโยค
ประพจน์แบบความเดียว (เอกถรรถประโยค หรื อ Atomic) และ ประพจน์
แบบความซ้อน (อเนกถรรถประโยค หรื อ Molecular)
• Atomic Sentence คือประโยคความเดียวโดยสร้างมาจาก Predicate Symbol ตาม
ด้วยเครื่ องหมายวงเล็บและภายในวงเล็บจะเป็ นลําดับของเทอมเช่น
BROTHER(RICHARD,JOHN)
• Molecular Sentence คือประโยคความรวมที่สร้างมาจากประโยคความเดียวมา
รวมกันโดยใช้ตวั เชื่อม
2
ตัวอย่ างการแสดงความรู้ในทางตรรกศาสตร์
1. Marcus was a man -> Man(Marcus)
2. Marcus was a Pompeian -> Pompiean(MARCUS)
3. Marcus was born in 40 AD. -> Born(Marcus,40)
4. All man are mortal -> x Man(x) => Mortal(x)
5. All Pompeian died when the vocalno erupted in 79 AD.
Erupted (Volcano,79)  x (Pompiean(x) => Dead(x,79))
6. No mortal lives longer than 150 years.
xt1t2 mortal(x)  born(x, t1)  gt(t2 - t1,150)  dead(x, t2)
7. It is now 1983. -> Now = 1983

5
BNF(Backus-Naur Form)
Sentence -> AtomicSentence
| Sentence Connective Sentence
| Quantifier Variable,... Sentence
|~ Sentence
| (Sentence)
AtomicSentence -> Predicate(Term,…)| Term = Term
Term -> Funtion(Term,…)
| Constant ไวยากรณ์ ข องเพรดดิเ คตลอจิก
| Variable
Connective-> => | and | or | <==>
Quantifier-> for all |  | for some | 
Constant-> A | X1 | John| …
Variable-> a | x | s | …
Predicate-> Before | HasColor | Raining | …
Function-> Mother | LeftLegOf | Saraly | …
6
3
Well-formed formula (wffs)
• รูปแบบที่ถกู ต้ องของการเขียนแสดงความรู้ด้วยเพรดดิเคต
• ดูรูปแบบการเขียนจาก Backus-Naur Form
• ข้ อสังเกต
– Atomic sentence ทุกตัวเป็ น wffs
– Molecular sentence เป็ น wffs ก็ตอ่ เมื่อ แต่ละองค์ประกอบเป็ น wffs เช่น
(~F), (F V G), (F^G), (F->G) เมื่อ F และ G เป็ นประโยคที่เป็ น wffs
– Function เป็ นเทอมใน Predicate ได้ แต่ Predicate ไม่เป็ นเทอมของ
Function
– Predicate ไม่เป็ นเทอมใน Predicate อื่น เช่น
Hotel(Expensive-than(PangSaunKaew, Maeping)) ไม่เป็ น wffs
การตรวจสอบค่ าความจริงในการแสดงความรู้แ บบเพรดดิเ คต
การตรวจสอบค่ าความจริง
Propositional Logic Predicate Logic
Truth Resolution Unification +

Table Resolution
ภาพ แสดงการตรวจสอบค่าความจริงในการแสดงความรู้
แบบต่างๆ
8
4
ยูน ิฟิ เคชัน (Unification)
• ตัวแปรเหมือนกัน อาจมีความหมายไม่เหมือนกัน เช่น Man(x) และ
~Man(x)
• และ ตัวแปร สามารถแทนที่ให้เป็ นค่าคงที่ได้ เช่น
Brother(x,John) กับ Brother(Richard,John)
• ดังนั้น จึงต้องการแทนที่ ตัวแปรด้วยค่าคงที่ เพื่อการพิสูจน์ผล
• เพรดดิเคต P(x,f(y),B) อาจมีรูปเป็ นแบบอื่นๆ ได้อีก เช่น P(z,f(w),B)
หรื อ P(C,f(A),B)
ดังนั้นเราจะรู ้ได้อย่างไรว่า เพรดดิเคตเหล่านี้คือสิ่ งเดียวกัน
9

Unification คือการทําให้เพรดดิเคตที่มีรูปร่ างของตัวแปรและฟังก์ชนั ที่
แตกต่างกัน ทําให้เข้ากันได้ (ปรับให้เป็ นรู ปเดียวกัน) โดยการ
แทนที่ดว้ ยข้อมูลอื่น การแทนที่สามารถแสดงได้ดว้ ยเซ็ตของ
คู่ลาํ ดับที่นาํ มาแทนที่ เช่น s = {t1/v1, t2/v2,…} โดยที่คู่ลาํ ดับ ti,vi
หมายถึง term ti ถูกนําไปแทนค่าให้กบั ตัวแปร vi
ให้ s1 = {z/x, w/y} s2 = {C/x, A/y}
P(z,f(w),B) = P(x,f(y),B) s1
P(C,f(A),B) = P(x,f(y),B) s2
10
5
ตัวอย่าง
Hate(x,y)
Hate(MARCUS,z)
ต่อไปนี ้คือ Unification
s1 = {Marcus/x, z/y}
s2 = {Marcus/x,y/z}
s3 = {Marcus/x, Caesar/y, Caesar/z}
11
ขั้นตอนการแปลง Complex Sentence ให้ เป็ น Clause form

การหาค่าความจริ งในการแสดงความรู ้แบบเพรดดิเคต โดยใช้ Resolution ร่ วมกับ
Unification ให้ F เป็ นกลุ่มของถ้อยแถลงที่ให้มา
S เป็ นถ้อยแถลงที่ตอ้ งการพิสูจน์
Algorithm
1. ทําให้ทุกถ้อยแถลงใน F เป็ น clause form
2. ทําให้ S เป็ น clause form จากนั้นจึงทําให้เป็ น ~S และรวมเข้าไว้ใน เซ็ต clause ที่ได้
จาก 1
3. ทําตามขั้นตอนต่อไปนี้จนเกิดการขัดแย้ง หรื อ เสร็ จ หรื อไม่พบความเปลี่ยนแปลง
3.1 เลือก 2 clauses (ที่จะสามารถ resolve กันได้) ให้เป็ น parent clause
3.2 คํานวณ Resolvent ของ T1 และ T2 เรี ยก Resolvent นั้นว่า T12
3.3 เพิ่ม T12 นั้นเข้าไปในเซ็ต F
12
6
การแปลง Complex Sentence ให้ เ ป็ น Clause form
Predicate ที่ให้ มา
(x) { P(x)  { (y) [P(y)  P(f(x,y))] ^ ~(y)[Q(x,y)  P(y)]}}
1. Eliminate implication symbols: เปลีย่ นรูปของ x  y เป็ น ~x V y
(x) { ~P(x) V { (y) [~P(y) V P(f(x,y))] ^ ~(y)[~Q(x,y) V P(y)]}}
2. Reduce scope of negation symbols
(x) { ~P(x) V { (y) [~P(y) V P(f(x,y))] ^ (y)[Q(x,y) ^ ~P(y)]}}
3. Standardize variables: เปลีย่ นชื่อของตัวแปร ตาม scope ของ quantifiers
(x) { ~P(x) V { (y) [~P(y) V P(f(x,y))] ^ (w)[Q(x,w) ^ ~P(w)]}}
4. Eliminate existential quantifiers: แทนค่าตัวแปรด้ วย Skolem function
(x) { ~P(x) V { (y) [~P(y) V P(f(x,y))] ^ [Q(x,g(x)) ^ ~P(g(x))]}}
13
การแปลง Complex Sentence ให้ เ ป็ น Clause form (ต่ อ )

5.Convert to prenex form: ย้ าย universal quantifers ทุกตัวมาอยู่
หน้ าสุด และ form ที่ได้ นี ้เรี ยกว่า prenex form
(x) (y) { ~P(x) V {[~P(y) V P(f(x,y))] ^ [Q(x,g(x)) ^ ~P(g(x))]}}
6. Put prenex form in conjunctive normal form: form ที่ทกุ นิพจน์
เชื่อมกันด้ วยเครื่ องหมาย ^
(x) (y) {[~P(x) V ~P(y) V P(f(x,y))]
^ [~P(x) V Q(x,g(x))]
^ [~P(x) V ~P(g(x))]}
14
7
การแปลง Complex Sentence ให้ เ ป็ น Clause form (ต่ อ )
7. Eliminate universal quantifier: เราสามารถตัด universal
quantifier ทิ ้งได้ เลยเพราะรู้วา่ ตัวแปรทุกตัวเป็ นของ universal
quantifier
8. Eliminate ^ symbols: แทน (X1^X2^…^Xn) ด้ วยเซ็ต {X1,X2, ...,Xn} โดยที่
Xiใดๆ เป็ น disjunction of literal หรื อ clause จากตัวอย่างจะได้ 3 clauses
(1) ~P(x) V ~P(y) V P(f(x,y)) (2) ~P(x) V Q(x,g(x))
(3) ~P(x) V ~P(g(x))
9. Rename variables: ไม่ให้ variables หนึง่ ๆ ปรากฏในหลายๆ clauses
(1) ~P(x1) V ~P(y) V P(f(x1,y)) (2) ~P(x2) V Q(x2,g(x2))
(3) ~P(x3) V ~P(g(x3))
15
ตัวอย่างการใช้ Resolution ร่ วมกับ Unification

ให้ ค วามรู้ ม าดังนี ้
1. Man(Marcus)
2. Pompeian(Marcus)
3. ~Pompeian(x1) V ROMAN(x1)
4. Ruler(Caesar)
5. ~Roman(x2) V Loyalto(x2,Caesar) V Hate(x2,Caesar)
6.Loyalto(x3,f1(x3))
7. ~Man(x4) V ~ Ruler(y1) V ~Tryassassinate(x4,y1) V ~Loyalto(x4,y1)
8. Tryassassinate(Marcus,Caesar)
สรุปว่า Hate(Marcus,Caesar) ; Marcus เกลียด Caesar จริงหรื อไม่ 16
8
ตัวอย่างการใช้ Resolution ร่ วมกับ Unification (ต่ อ )
~ Hate(Marcus,Ceasar) 5
Marcus/x2
3 ~Roman(Marcus) V Loyalto(Marcus,Caesar)
Marcus/x1
~Pompeian(Marcus) V Loyalto(Marcus,Ceasar) 2
7 Loyalto(Marcus,Caesar)
Marcus/x4, Caesar/y1
1 ~Man(Marcus) V ~ Ruler(Caesar) V~Tryassassinate(Marcus,Caesar)
~Ruler(Caesar) V ~ Tryassassinate(Marcus,Caesar) 4
~ Tryassassinate(Marcus,Caesar) 8
17
Q&A
18
9

COS3109 Artificial Intelligence (AI)

Uploaded by

Copyright:

Available Formats

COS3109 Artificial Intelligence (AI)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

COS3109 Artificial Intelligence (AI)

Uploaded by

Copyright:

Available Formats

COS3109

Artificial Intelligence (AI)

What is Artificial Intelligence?

• Intelligence is the ability to understand

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 1

What is Artificial Intelligence?

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 2

Turing Test (cont’d)

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 3

Turing Test (cont’d)

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 4

Turing Test (cont’d)

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 5

ปัญญาประดิษฐ์ คอื อะไร

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 6

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 7

การประยุกต์ ใช้ ปัญญาประดิษฐ์ ในศาสตร์ แขนงอืน่ ๆ

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 8

อาซิโม(ASIMO) หุ่นยนต์เลียนแบบมนุษย์ของบริ ษทั ฮอนดาสามารถเดิน

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 9

งานทีเ่ ป็ นแบบแผน (FORMAL TASK)

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 10

องค์ ประกอบและโครงสร้ างการทํางานของระบบผู้เชี่ยวชาญ

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 11

การประมวลผลภาษาธรรมชาติ เป็ นการติดต่อสื่ อสารระหว่างผูใ้ ช้

ตัวอย่ างซอฟต์ แวร์

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 12

คอมพิวเตอร์ โครงข่ ายใยประสาท (Neural Computing)

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 13

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 14

COS3109 Artificial Intelligence อ.ดร.อัจฉรา มหาวีรวัฒน์ 15

เทคนิคในการแก้ ปัญหาของ Formal task

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 1

• ปัญหามีสถานะจุดเริ่ มต้นที่แน่นอนหรื อสามารถกําหนดได้วา่ จุดใด

วิธีการแก้ ปัญหาแบบห้ วงสถานะ

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 2

ขั้นตอนการแก้ ปัญหาแบบห้ วงสถานะ

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 3

ใบแรก ความจุ 4 ลิตร ใบที่สอง ความจุ 3 ลิตร ใบแรก มีน้ าํ จุ 2 ลิตร

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 4

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 5

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 6

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 7

ตัวอย่ าง: ปัญหา 8-Puzzle

ตําแหน่งเริ่ มต้น ตําแหน่งสิ้ นสุ ด

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 8

การกําหนดนิยามของปัญหา 8-Puzzle (ต่ อ)

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 9

1. รูปแบบโครงสร้ างข้ อมูลทีใ่ ช้ ในการค้ นหา

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 10

2. การกําหนดทิศทางสํ าหรับการค้ นหา

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 11

• แสดงความรู ้ให้อยูใ่ นรู ปที่สามารถสื่ อให้มนุษย์เข้าใจได้ และ

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 12

5. การค้ นหา (Searching)

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 13

Algorithm: Breadth-First Search

COS3109 Artificial Intelligence Atchara Mahaweerawat, Ph.D. 14

สถานะเริ่ มต้น สถานะเป้ าหมาย 29