ช่วยอธิบาย ขั้นตอนวิธีของพริม!!

chup_aa · #1 12 กันยายน 2006, 14:57

คือยังไม่ค่อยเข้าใจในขั้นตอนวิธีมากนัก
ช่วยอธิบายขั้นตอนวิธีที่ช่วยให้เข้าใจง่ายๆ ขึ้นมากกว่านี้หน่อยอ่ะค่ะ...

gon · #2 12 กันยายน 2006, 21:18

พริมนี่คือใครหรือครับ.

Mr.high · #3 12 กันยายน 2006, 22:01

ไม่แน่ใจว่าอันนี้เป็น minimal spanning tree หรือเปล่าครับ
minimal spanning tree คือการหาต้นไม้ที่เล็กที่สุดที่เป็น connected ทุก vertice ในกราฟ
(อยู่ในเรื่อง graph theory)
ถ้าหา minimal spanning tree เท่าที่ผมทราบมีอยู่สามวิธี
คือวิธี ของ พริม ครุสคาล และโบรัฟกา
ส่วนวิธีของพริมก็คือ
1. เราเลือกจุด u ใดๆในกราฟ และเราก็เลือกเส้นที่มีน้ำหนักน้อยสุดที่เชื่อมกับ จุด u มา
2. ทีนี้เราก็ได้กราฟย่อยที่มีสองจุด เราก็ทำการเลือกเส้นที่สั้นที่สุดที่เชื่อมกับสองจุดนี้ โดยที่ไม่ทำให้เกิด cycle
3. เราก็ทำเช่นนี้ไปเรื่อยๆจนได้ครบทุกจุด

ถ้าไม่เข้าใจลองไปดูที่
http://en.wikipedia.org/wiki/Prim%27s_algorithm

แต่ผมคิดว่าวิธีของ ครุสคาล น่าจะเข้าใจง่ายกว่านะครับ

gon · #4 12 กันยายน 2006, 22:21

อ้อ เข้าใจแล้วครับ ถ้าเป็น prim อย่างที่คุณ high กล่าวถึง ในหนังสือคณิตศาสตร์ ม.5 สาระการเรียนรู้เพิื่มเติม เล่ม 2 มีอธิบายด้วยครับ. (ถ้าเข้าใจไม่ผิด)

Mr.high · #5 13 กันยายน 2006, 18:18

เดี๋ยวนี้เค้ามีหลักสูตรแบบนี้ในม.ปลายด้วยหรอ ไม่เคยได้ยินเลย สงสัยจะแก่เกินวัยไปแล้ว 555