Shortest Path

เขียนโดย webmaster เมื่อ . หัวข้อ สื่อการสอน, เทคโนโลยีสารสนเทศและการสื่อสาร

  • Views 0

คำนำ

           SHORTEST PATH เป็นขั้นตอนที่เกี่ยวกับทฤษฎีกราฟเพื่อหาระยะทางที่สั้นที่สุด ในการเชื่อมจุด แต่ละจุด บนระนาบที่เราสนใจ ยกตัวอย่างให้เข้าใจง่ายๆ เช่น ถ้าต้องการตัดถนนผ่านเมือง 5 เมือง เราจะ ต้องหาเส้นทางในการตัดถนนที่มีค่าใช้จ่ายน้อยที่สุด คือ ต้องเริ่มต้นตัดถนนจากเมืองใด แล้วผ่านไปยัง เมืองใดเป็นเมืองที่ 2  3 4 และ 5 ตามลำดับและกลับมายังเมืองเดิม โดยให้ถนนที่ตัดเสร็จแล้วสั้นที่สุด เพื่อให้ใช้วัสดุและเวลาในการทำงานน้อยที่สุด

 

วิธีการ

ในแผงสาธิตจะมีแท่งเหล็ก 10 แท่งซึ่งแทนเมืองแต่ละเมือง

ในการสาธิตเราสามารถกำหนดได้ว่า เราต้องการตัดถนนผ่านเมืองใดบ้างและผ่านกี่เมือง

ใช้เชือกคล้องผ่านแท่งเหล็กที่แทนเมืองที่เราจะตัดถนนผ่านตั้งแต่เมืองแรกจนถึงเมืองสุดท้ายและ วนกลับมาที่เมืองเดิม

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

 

   

 

รูปอุปกรณ์ช่วยในการสอนเรื่อง Shortest  Path


Tags: ,