พิสูจน์ว่ามี 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 น.
Counter : 989 Pageviews.

0 comments
ตอนที่1วิกฤตไวรัสโควิช-19 จะนำมาซึ่งโอกาสดีเสมอ ธนูคือลุงแอ็ด
(21 มี.ค. 2563 18:02:45 น.)
面子上好看 Miànzi shàng hǎokàn ภายนอกดูดี Kavanich96
(19 มี.ค. 2563 04:44:46 น.)
เพลง "UEFA Champions League anthem" toor36
(13 มี.ค. 2563 00:04:57 น.)
(◕‿◕❀) Blogger Review :Tui Laksi ❤ T H ☆ N K - Y ♡U ❤ BlogGang.com และเพื่อนสมาชิกทุกท่าน Tui Laksi
(7 มี.ค. 2563 21:52:39 น.)
ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
 *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

Zol.BlogGang.com

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

[ดู Profile ทั้งหมด]
 ผู้ติดตามบล็อก : 85 คน [?]

บทความทั้งหมด