creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
พิสูจน์ว่ามี Gray code ขนาด n-bit ด้วยการพิสูจน์ว่ามี Hamiltonian cycle ของ hypercube n มิติ

เริ่มจากปัญหาข้อหนึ่งในหนังสือ Are You Smart Enough to Work at Google? ของ William Poundstone (เราไม่ชอบชื่อหนังสือนี่เลย)



เราโพสต์บน fb ว่า สำหรับนักเรียนวิศวะ (โดยเฉพาะคอมพิวเตอร์ อิเล็กทรอนิกส์ กลุ่มนี้) ไม่ควรใช้เวลาเกิน 2 นาทีนะ :P เพราะวิธีที่ใช้สร้างลำดับสามารถแสดงได้ด้วย Gray code แล้วเราพูดแค่ว่ามี n-bit Gray code ก็จบ

อธิบายโจทย์เล็กน้อย สมมติมี 2 คน A, B

เขียน [...] แทน "..." อยู่ในห้อง

ตัวอย่าง [A]B เท่ากับ A อยู่ในห้อง, B อยู่นอกห้อง

possible combination ก็จะมี []AB, [A]B, [B]A, [AB] ถูกใช่มั้ย

ถ้าเราจัดลำดับของ move คือ []AB, [A]B, [AB], [B]A เราก็จะได้ลำดับของ move ที่มี possible combination ทั้งหมด 1 ครั้ง

แต่ถ้าเป็น 3 คน ลำดับต่อไปนี้จะไม่ครอบคลุมทุก possible combination และถ้าหากอยากให้ครอบคลุมทั้งหมด จะต้องมีบาง combination ที่เกิดขึ้นมากกว่า 1 ครั้ง

[]ABC, [A]BC, [AB]C, [ABC], [BC]A, [C]AB, [CA]B เห็นว่าเราขาด [B]AC และถ้าจะทำให้เกิด [B]AC โดยเริ่มจาก [CA]B มันจะต้องซ้ำกับ [C]AB หรือ [A]BC ใน move ถัดไป

(แต่ถ้าเราจัดลำดับใหม่ดี ๆ กรณี A B C ก็สามารถทำได้ ไม่ยาก)

คำถามคือ สำหรับ คนนอกห้อง N คนใด ๆ และเริ่มจากห้องว่าง เราสามารถสร้างลำดับที่มีครบทุก possible combination และแต่ละ combination ปรากฎเพียง 1 ครั้ง ได้มั้ย

มันเชื่อมโยงกับ Gray code ตรงที่เราสามารถเขียนแทนสถานะการอยู่นอกหรือในห้องตามโจทย์ด้วย 0 กับ 1 แล้วใช้ลำดับของ binary string ที่แตกต่างกันแค่บิตเดียวถ้า string 2 ตัวใด ๆ ในลำดับนั้นอยู่ติดกัน และลำดับของ binary string ดังกล่าวก็คือรหัส Gray

ตัวอย่าง รหัส Gray 3 บิต 000, 001, 011, 010, 110, 111, 101, 100 ถ้าให้สถานะ 0 กับ 1 สามบิตนั้นแทนนอกและในห้องของ ABC ตามลำดับ 000 (ทั้ง 3 คนอยู่นอกห้อง), 001 (C เข้าห้อง), ... ก็จะเป็นลำดับของคำตอบ

ทีนี้เราจะพิสูจน์ได้อย่างไรว่ามี Gray code ขนาด n บิตสำหรับ n ใด ๆ ที่มากกว่า 2 อยู่เสมอ วิธีที่ง่ายวิธีหนึ่งคือ พิสูจน์ว่ามี Gray code ขนาด n-bit ด้วยการพิสูจน์ว่ามี Hamiltonian cycle ของ hypercube n มิติ



นิยาม hypercube n มิติ (Hn) คือกราฟที่จุดโหนด (vertex) เป็นเซ็ตของ binary string ทั้งหมดที่ยาว n บิต และจุดโหนด 2 จุดใด ๆ เชื่อมกันด้วยเส้นเชื่อม (edge) ก็ต่อเมื่อจุดโหนด 2 จุดนั้นแตกต่างกันแค่ 1 บิต (ดูรูป)

นิยาม Hamiltonian cycle คือ cycle ในกราฟที่ลากผ่านทุกจุดโหนด 1 ครั้ง (ดูรูป เส้นหนาคือ Hamiltonian cycle)

เห็นว่า Hamiltonian cycle ก็คือ Gray code

เราจะพิสูจน์การมีอยู่ของ n-bit Gray code โดยพิสูจน์ว่ามี Hamiltonian cycle ใน Hn ด้วย induction บนค่าของ n ที่ base case คือ n = 2 (ดูตามรูป เป็น trivial case ถือว่าพิสูจน์แล้วโดยการสร้าง) ต่อมา ใน inductive step เราจะสมมติว่ามี Hamiltonian cycle ใน Hn แล้วแสดงให้เห็นว่า มันจะมี Hamiltonian cycle ใน Hn+1 ด้วย

ถ้าเราวาดกราฟ Hn+1 เราสามารถแบ่ง vertices ออกได้เป็น 2 กลุ่มคือกลุ่มที่ขึ้นด้วย 0 กับกลุ่มที่ขึ้นด้วย 1 นั่นคือในแต่ละกลุ่มสามารถถูกมองเป็นกราฟย่อย Hn ฉะนั้นในแต่ละกลุ่มมี Hamiltonian cycle และเราสามารถเชื่อม Hamiltonian cycle สองวงของสองกลุ่มนี้เข้าด้วยกันได้ง่าย ๆ โดยการตัดต่อ

สมมติเราตัดเส้นเชื่อมระหว่างโหนด 0x0y กับโหนด 0x1y (เมื่อ x และ y เป็น binary string ที่มีความยาวที่เป็นไปได้ตั้งแต่ 0 ถึง n-2 บิต และความยาวของ x รวมกับความยาวของ y เท่ากับ n-2 บิต) ที่อยู่บน Hamiltonian cycle ของกลุ่มที่หนึ่ง และตัดเส้นเชื่อมระหว่าง 1x0y กับ 1x1y ที่อยู่บน Hamiltonian cycle ของกลุ่มที่สอง แล้วเชื่อม 0x0y เข้ากับ 1x0y และเชื่อม 0x1y เข้ากับ 1x1y เราจะได้ Hamiltonian cycle วงเดียวของ Hn+1


Create Date : 16 พฤษภาคม 2558
Last Update : 16 พฤษภาคม 2558 11:18:47 น. 0 comments
Counter : 967 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.