ต่อไป »

[sisi]

สมมุติว่า มี แผนที่ ขนาด 1000x1000 ตาราง ภายในแผนที่มีตำแหน่งของ ขุมทรัพย์อยู่ 7 อัน (เราไม่รู้ว่ามันอยู่ตรงไหนมั่ง)

ถาม : ช่วยคิดหลักการหน่อยครับว่า เราควรจะเขียนโปรแกรมยังไงให้มันหาตำแหน่งของขุมทรัพย์ทั้ง 7 ให้ได้โดยเร็วที่สุด


พอดี อ. เค้าให้โจยท์มาคิดหน่ะครับ ยังคิดวิธีที่ดีที่สุดไม่ได้เลย เลยอยากจะมาขอความเห็นพี่ในนี้หน่อย เผื่อจะมีแนวคิดแปลกๆ ให้ผมเอาไปเขียนโปรแกรมต่อไป


ขอบคุณมากครับ

[EThaiZone]

นึกไม่ค่อยออกแฮะ

แต่ลองเป็นว่า

1. สร้างอาเรย์ข้อมูลเลียนแบบตาราง 1000*1000 ไว้เก้บค่าว่าเราตรวจช่องไหนไปแล้ว
2. สุ่มค่าระหว่าง 1 ถึง 1000 ออกมา 2 ค่า ใช้อ้างอิงแทนแกน X กับ Y ของตาราง
3. สั่งตรวจสอบตารางด้วยค่า X กะ Y จากข้อ 2  แล้วถ้าไม่เจอก็เก็บลงอาเรย์
ถ้ามีการตรวจแล้ว ก็ไม่ต้องตรวจ  ถ้าเจอก็เก็บแยกลงลิสว่าเจอช่องไหน

เพียงแต่เราก็ต้องมาคิดด้วยว่า
ใช้สุ่มแบบข้างบน กะ ไล่ตรวจเลย อย่างไหนจะดีกว่า

ไล่ตรวจแบบรันตามเลข ข้อดีคือไม่ต้องตรวจว่ามีการตรวจแล้วหรือเปล่า
แต่กลับกัน การสุ่ม ก็สร้างโอกาสการเข้าถึงข้อมูลได้เร็วกว่า

ถ้านึกบ้านๆ ระหว่าง RAM กับ HD ที่ใช้วิธีการเข้าถึงข้อมูลต่างกัน
แบบไหนเร็วกว่ากัน  :

(ผมไม่ได้เรียนด้านสถาปัตยกรรมคอมพิวเตอร์มา เลยบอกแบบฟันธงไม่ได้ครับ)

[ColdMoney]

แล้วมีข้อกำหนดไงบ้างล่ะครับ เช่นว่า ต้องหาได้ทีล่ะ 1 ช่อง และช่องต่อไปต้องติดกันไหม เป็นรูปแบบของการเดินหาสมบัติป่ะครับ หรือว่าสามารถหาพร้อมๆกันได้ทีล่ะหลายช่อง แล้วขุมทรัพท์แต่ล่ะจุดเนี่ย กว้างยาวเท่ากับ 1x1 ป่ะครับ 

[sisi]

แล้วมีข้อกำหนดไงบ้างล่ะครับ เช่นว่า ต้องหาได้ทีล่ะ 1 ช่อง และช่องต่อไปต้องติดกันไหม เป็นรูปแบบของการเดินหาสมบัติป่ะครับ หรือว่าสามารถหาพร้อมๆกันได้ทีล่ะหลายช่อง แล้วขุมทรัพท์แต่ล่ะจุดเนี่ย กว้างยาวเท่ากับ 1x1 ป่ะครับ 

ขุมทรัพย์เป็นแบบ 1x1 ช่องครับ รูปแบบจริงๆ อาจารย์เค้าบอกว่า เลียนแบบการ์ตูนเรื่อง ดราก้อนบอลหน่ะครับ ที่ต้องหาลูกแก้ว ทั้ง 7 ลูก บนพื้นพิภพนี้ให้ได้โดยไวที่สุด ถ้าเจอแล้วก็ให้บอกมาเป็นพิกัด x*y หน่ะครับ

นึกไม่ค่อยออกแฮะ

แต่ลองเป็นว่า

1. สร้างอาเรย์ข้อมูลเลียนแบบตาราง 1000*1000 ไว้เก้บค่าว่าเราตรวจช่องไหนไปแล้ว
2. สุ่มค่าระหว่าง 1 ถึง 1000 ออกมา 2 ค่า ใช้อ้างอิงแทนแกน X กับ Y ของตาราง
3. สั่งตรวจสอบตารางด้วยค่า X กะ Y จากข้อ 2  แล้วถ้าไม่เจอก็เก็บลงอาเรย์
ถ้ามีการตรวจแล้ว ก็ไม่ต้องตรวจ  ถ้าเจอก็เก็บแยกลงลิสว่าเจอช่องไหน

เพียงแต่เราก็ต้องมาคิดด้วยว่า
ใช้สุ่มแบบข้างบน กะ ไล่ตรวจเลย อย่างไหนจะดีกว่า

ไล่ตรวจแบบรันตามเลข ข้อดีคือไม่ต้องตรวจว่ามีการตรวจแล้วหรือเปล่า
แต่กลับกัน การสุ่ม ก็สร้างโอกาสการเข้าถึงข้อมูลได้เร็วกว่า

ถ้านึกบ้านๆ ระหว่าง RAM กับ HD ที่ใช้วิธีการเข้าถึงข้อมูลต่างกัน
แบบไหนเร็วกว่ากัน 

(ผมไม่ได้เรียนด้านสถาปัตยกรรมคอมพิวเตอร์มา เลยบอกแบบฟันธงไม่ได้ครับ)

คิดเหมือนผมเลยอ่ะ ผมว่าถ้าไล่ตรวจนี่ มันแน่นอนเลยครับว่าเจอแน่ๆ แต่ว่ามันกินเวลานานมาก

[EThaiZone]

แล้วมีข้อกำหนดไงบ้างล่ะครับ เช่นว่า ต้องหาได้ทีล่ะ 1 ช่อง และช่องต่อไปต้องติดกันไหม เป็นรูปแบบของการเดินหาสมบัติป่ะครับ หรือว่าสามารถหาพร้อมๆกันได้ทีล่ะหลายช่อง แล้วขุมทรัพท์แต่ล่ะจุดเนี่ย กว้างยาวเท่ากับ 1x1 ป่ะครับ 

ขุมทรัพย์เป็นแบบ 1x1 ช่องครับ รูปแบบจริงๆ อาจารย์เค้าบอกว่า เลียนแบบการ์ตูนเรื่อง ดราก้อนบอลหน่ะครับ ที่ต้องหาลูกแก้ว ทั้ง 7 ลูก บนพื้นพิภพนี้ให้ได้โดยไวที่สุด ถ้าเจอแล้วก็ให้บอกมาเป็นพิกัด x*y หน่ะครับ

แสดงว่าเป็นการเข้าค้นหา ณ ช่วงเวลานั้นๆ ได้ 1 ครั้ง ?

งั้นคงต้องเลือกเอาละครับ ระหว่าง ไล่ค้นหา กับสุ่มค้นหา
เพราะโจทย์ไม่ได้บอกอะไรมากนักเลย

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

[sisi]

รบกวนพี่ๆช่วยดูอันนี้หน่อยนะครับ พอดีวันนี้อาจารย์เปิดวิธีการหาให้ดู (อันนี้จำลองมานะ)

วิธี A


วิธี B



วิธี A ที่ผมไม่ค่อยสงสัยเท่าไหร่ เพราะให้วิธีวนหาแบบ ถึก ตามแบบธรรมดาทั่วไป

แต่ B นี่ดิครับ ผมงงว่าการเดินของมันเป็นแบบนั้นได้ยังไง มันคิดยังไงถึงเดินออกมาได้แบบนั้น

[paradox_073]

น่าจะ บวกเป็นเท่าๆทั้งแกน x และ y ไปเรื่อยๆ แล้วพอถึงจุดที่ต้องการ ก็ให้ คงที่ array ตัวใดตัวหนึ่งอะครับ  :
มาแบบมั่วๆ 

[sisi]

น่าจะ บวกเป็นเท่าๆทั้งแกน x และ y ไปเรื่อยๆ แล้วพอถึงจุดที่ต้องการ ก็ให้ คงที่ array ตัวใดตัวหนึ่งอะครับ  :
มาแบบมั่วๆ 

แต่ปัญหามันอยู่ที่ว่า  ความจริงเราไม่รู้ไงครับว่า ไอ่จุดแดงนั่นมันอยู่ที่ไหนของตาราง

[EThaiZone]

วิธี B มันทำให้ผมนึกถึงว่าลูกศรคือโงกุนครับ

คือยังไง คือมันเดินไปแล้วย้อนกลับไปจุดแนวต้นในแกนนั้นๆ ได้

ทางที่จะเดินแล้วโงกุนมองได้ทั่วพิภพ เอ้ย กระดาน
คือการเดินแนวทะแยงไปเลย แล้ว... อธิบายยาก เลยทำภาพประกอบมาคร่าวๆ



คือมันไปเริ่มที่จุด 1
แล้วไล่ทีละช่องตรวจลงมาจนถึงจุด 2
แล้วถ้าไม่เจอ ก็เดินย้านกลับไปจุด1
แล้วเดินไล่ตรวจทีละช่องไปจนถึงจุด 3
ถ้าไม่เจอก็เริ่มต่อจากจุด 4 เลย
แล้วก็ทำแบบนั้นไปเรื่อยๆ จนเจอ

แนวคิดเหมือนกับการแผ่รากของต้นไม้อะ
แต่ผมแค่คาดเดาจากภาพที่ได้มาอะน่ะ
เพราะยังไง โจทย์คงเป็นการทำงานแบบ 1 process ในเวลานั้นๆ

[ColdMoney]

น่าจะ บวกเป็นเท่าๆทั้งแกน x และ y ไปเรื่อยๆ แล้วพอถึงจุดที่ต้องการ ก็ให้ คงที่ array ตัวใดตัวหนึ่งอะครับ  :
มาแบบมั่วๆ 

แต่ปัญหามันอยู่ที่ว่า  ความจริงเราไม่รู้ไงครับว่า ไอ่จุดแดงนั่นมันอยู่ที่ไหนของตาราง

ถ้าเลียนแบบมาจาก dragon บอลคุณก็ต้องมี radar ด้วยนะครับ 

ปล: ถ้าไม่รู้ตำแหน่งเลย ยังไงๆ ก็ต้องค้นทุกจุดครับ ไม่น่าจะเป็นโจทย์ที่อาจารย์คุณจะให้ทำนะ แต่ถ้าโจทย์บอกว่าตำแหน่งถูกสุ่มแบบมั่วๆ และให้หาเส้นทางที่ใกล้ที่สุด อันนี้น่ะค่อยน่าคิดหน่อย

[EThaiZone]

ปล: ถ้าไม่รู้ตำแหน่งเลย ยังไงๆ ก็ต้องค้นทุกจุดครับ ไม่น่าจะเป็นโจทย์ที่อาจารย์คุณจะให้ทำนะ แต่ถ้าโจทย์บอกว่าตำแหน่งถูกสุ่มแบบมั่วๆ และให้หาเส้นทางที่ใกล้ที่สุด อันนี้น่ะค่อยน่าคิดหน่อย

ถ้าเป็นแบบนั้น สงสัยจะเป็นการเขียน AI แทนแล้วครับ 

[payu]

เอ่ .. คุ้นๆนะเนี่ยะ ..

ถ้าไม่รู้จุดขุมทรัพย์ (ไม่มีเงื่อนไขเลย) และไม่รู้จุดเริ่มต้น
ก็ต้องใช้วิธี random ครับ เก็บค่าที่ตรวจแล้ว ถ้าไม่เจอก็ไปเช็คจุดต่อไป ..
ซึ่งความเป็นไปได้ของจำนวนครั้งในการค้นหา = 1 ถึง WxH ครั้ง ครับ (อันนี้เรื่อง probability แล้วล่ะ)

แต่ที่เคยเจอ ก็จะเป็น algorithm ในการหาทางออกจากเขาวงกตซึ่งเส้นทางการเดินจะมีเงื่อนไข ..
มี algorithm หลายแบบมาก (ยากๆทั้งนั้นเลย) ... 

[chuanguru]

แล้วแบบ B จะได้ผลลัพธ์ไวกว่าแบบ A เหรอครับ ถ้าคุณ EThaiZone อธิบายคือ มันต้องเดินย้อนกลับไปจุดเดิมอีกอ่ะครับผมว่าจะเสียเวลามากกว่าแบบเดินไปทางเดียว งง เหมือนกัน ที่ผมคิดได้คือ ผมคิดว่าให้มีโงกุนและผองเพื่อนจำนวนพันคนวิ่งไปทางเดียว(แกน x หรือ y ก็แล้วแต่) แล้วจะพบขุมทรัพย์เร็วที่สุดครับ (โจทย์ไม่ได้บอกอะไรมากมายอ่ะ อิอิ)  
ดังรูป


ให้เขียนเป็นโปรแกรมเหรอครับ ผมเขียนไม่เป็นหรอก แหะๆๆ

[EThaiZone]

วิธี B ไม่ใช่การเดินย้อนกลับครับ

แต่เป็นการกลับไปยังจุดเริ่มของระนาบนั้นๆ

ในจุด 1 ก็คือ x=1 y=-1
แต่พอจุด 4 จะเป็น x=2 y=-2

คือมันคำนวณได้อยู่แล้วว่า x+1 ส่วนy-1 ไล่ทุกระนาบแล้วทะแยงไป

มันก็เหมือนวิธี A แต่อาศัยว่าต้องกลับไปตั้งต้น ณ ระนาบนั้นๆ
ถ้าไม่มีก็ขึ้นระนาบใหม่ 

ต้องลองเทสแล้วเขียนระบบจับเวลาดูครับ น่าจะได้คำตอบดีที่สุด

[paradox_073]

แล้วแบบ B จะได้ผลลัพธ์ไวกว่าแบบ A เหรอครับ ถ้าคุณ EThaiZone อธิบายคือ มันต้องเดินย้อนกลับไปจุดเดิมอีกอ่ะครับผมว่าจะเสียเวลามากกว่าแบบเดินไปทางเดียว งง เหมือนกัน ที่ผมคิดได้คือ ผมคิดว่าให้มีโงกุนและผองเพื่อนจำนวนพันคนวิ่งไปทางเดียว(แกน x หรือ y ก็แล้วแต่) แล้วจะพบขุมทรัพย์เร็วที่สุดครับ (โจทย์ไม่ได้บอกอะไรมากมายอ่ะ อิอิ) 
ดังรูป


ให้เขียนเป็นโปรแกรมเหรอครับ ผมเขียนไม่เป็นหรอก แหะๆๆ

ตั้งใจทำจิงๆ 

[icez]

จากรูปนี่แสดงว่ารู้ตำแหน่งอยู่แล้วนี่ครับว่าไอ้ลูกบอลนั่นอยู่ตรงไหนบ้าง
ทีนี้ กรณีรู้ตำแหน่งต้นทาง และปลายทางแล้ว และต้องการเดินให้ "สั้นที่สุด"
ใช้ pathfinding algorithm ครับ ค้นหาใน google ได้เลย มีทุกภาษา
แม้กระทั่ง php ที่ไม่รู้ใช้ทำไรก็ยังมีได้

ไปลอกๆ เอาจาก บอทเกมไหนก็ได้ฮะ บอทพวกนี้มีทั้งนั้นแหละ pathfinding algorithm น่ะ
ส่วนกรณีที่ไม่รู้เลย ว่าลูกบอลอยู่ตรงไหน วิธีที่เร็วที่สุดจะเป็นการเดินไปเรื่อยๆ ครับ
เพราะไม่สามารถ random ได้