“ปัญหาเลือกคู่”

“ปัญหาเลือกคู่” (marriage problem หรือ secretary problem) หรือรู้จักในชื่อทั่วไปคือ optimal stopping problem คือสมมุติว่าเรามีโอกาสคบคนทั้งหมด n คน โดยที่ต้องคบทีละคน และต้องเลิกคบกับคนปัจจุบันก่อนที่จะไปคบคนต่อไป เมื่อเลิกคบกับใครแล้วห้ามกลับไปคบกับเขาอีก แล้วต้องตัดสินใจว่าจะเลือกใครเป็นคู่ โดยหวังว่าจะเลือกคนที่ดีที่สุดใน n คนนี้

ปรากฎว่ามีวิธีที่ทำให้เรามีโอกาสประมาณ 37% ที่จะเลือกคนที่ดีที่สุดได้ ไม่ว่าจำนวน n จะเป็น 3, 10, 100, หรือ 1 ล้าน คือให้คบคนไป n/e คนก่อน โดยที่ e เป็นค่าคงที่ 2.71828… เรียกว่าค่าอีหรือค่าคงที่ของออยเลอร์) อย่าพึ่งเลือกคนเหล่านี้ จากนั้นให้เลือกคนแรกที่ดีกว่าคนที่เคยคบมา (หรือเลือกคนสุดท้ายเมื่อไม่เหลือใครแล้ว) ยกตัวอย่างเช่นถ้าเราคิดว่าคงมีเวลาคบคน 10 คน ค่า n ของเราก็คือ 10 ดังนั้นให้เราคบไป 10/e = 10/2.71828… = 3.6787.. เท่ากับประมาณ 4 โดยที่เรายังไม่ตัดสินใจเลือกใครใน 4 คนนี้ ต่อไปเราคบกับคนที่เหลือทีละคน แล้วเลือกคนแรกที่ดีกว่าคนที่เราเคยคบมา ถ้าหาไม่ได้ก็เลือกคนสุดท้าย

เราเขียนโปรแกรมให้คอมพิวเตอร์ทดลองหลายๆครั้งให้เราดูว่าวิธีนี้ทำให้หาคู๋ที่ดีที่สุดได้่บ่อยแค่ไหนดังนี้:

In [1]:
import math
import random

def try_n_over_e_dating(n_dates, n_trials):
    """
    ทดลองหาคู่ด้วยวิธีิ n/e ดูว่าเจอคนที่ดีที่สุดบ่อยแค่ไหน
    n_dates = จำนวนคนที่เราอาจจะคบด้วยได้
    n_trials = จำนวนครั้งที่ทดลอง
    """
    successes = 0
    for trial in range(n_trials):
        n_explore = round(n_dates/math.e) #จำนวนคนที่เราจะลองคบแต่ไม่เลือก 
                                      #เพื่อให้มีไอเดียว่าคุณภาพคู่ของเราเป็นอย่างไรได้บ้าง

        candidates = [random.random() for i in range(n_dates)] #คะแนนคนที่เราอาจคบ
        max_score = max(candidates) #คะแนนสูงสุดที่เป็นไปได้
        max_explore = max(candidates[:n_explore]) #คะแนนสูงสุดของคนที่ลองคบแต่ไม่เลือก

        for c in candidates[n_explore:]: #วนค้นหาคนที่เหลือว่ามีใครคะแนนสูงกว่าที่ลองคบไหม
            if c > max_explore:          #ถ้าเจอ ก็เลือกคนนั้น
                chosen_score = c
                found_mate = True
                break
        else:
            chosen_score = candidates[-1] #ถ้าวนจนถึงคนสุดท้ายแล้วยังไม่พบคะแนนสูงกว่าที่ลองคบ ก็ต้องเลือกคนสุดท้าย
    
        if chosen_score == max_score: #ถ้าคนที่เลือกเป็นคนที่ดีที่สุดแปลว่าประสบความสำเร็จ
            successes += 1
            
    #ส่งค่า n_dates คือจำนวนคนที่เราอาจคบด้วย
    # n_explore คือจำนวนคนที่เราจะลองคบแต่ไม่เลือก 
    # n_trials คือจำนวนครั้งที่ให้คอมพิวเตอร์ทดลองหาคู่ด้วยวิธี n/e
    # ความน่าจะเป็นที่พบคนที่ดีท่ี่สุดคือเลขตัวสุดท้าย = successes/n_trials
    return(n_dates, n_explore, n_trials, successes/n_trials)
In [2]:
#สมมุติว่าคบได้ 10 คน ให้คอมพิวเตอร์ทดลองดู 1,000 ครั้งว่าได้คนที่ดีที่สุดบ่อยแค่ไหน
#ให้ดูตัวเลขตัวสุดท่้าย จะเป็นความน่าจะเป็นตั้งแต่ 0 ถึง 1

try_n_over_e_dating(10,1000)
In [3]:
#ลองคบได้ 3, 5, 10, 20, 50, 100, 1000 คน
#ให้คอมพิวเตอร์ลอง 10,000 ครั้ง

for n_dates in [3, 5, 10, 20, 50, 100, 1_000]:
    print(try_n_over_e_dating(n_dates, 10_000))
(3, 1, 10000, 0.4898)
(5, 2, 10000, 0.4338)
(10, 4, 10000, 0.3939)
(20, 7, 10000, 0.3814)
(50, 18, 10000, 0.3765)
(100, 37, 10000, 0.3685)
(1000, 368, 10000, 0.3648)
In [4]:
#ใช้ f-string พิมพ์ผลให้มนุษย์อ่าน

n_trials = 10_000
print(f"ให้คอมพิวเตอร์ทดลอง {n_trials:,} ครั้ง")
for n_dates in [3, 5, 10, 20, 50, 100, 1_000]:
    n, n_explore, trials, prob = try_n_over_e_dating(n_dates, n_trials)
    print(f"คนคบได้: {n:,} คน, ทดลองคบแต่ไม่เลือก:{n_explore} คน, สำเร็จ {100*prob:.0f}%")
ให้คอมพิวเตอร์ทดลอง 10,000 ครั้ง
คนคบได้: 3 คน, ทดลองคบแต่ไม่เลือก:1 คน, สำเร็จ 50%
คนคบได้: 5 คน, ทดลองคบแต่ไม่เลือก:2 คน, สำเร็จ 43%
คนคบได้: 10 คน, ทดลองคบแต่ไม่เลือก:4 คน, สำเร็จ 40%
คนคบได้: 20 คน, ทดลองคบแต่ไม่เลือก:7 คน, สำเร็จ 38%
คนคบได้: 50 คน, ทดลองคบแต่ไม่เลือก:18 คน, สำเร็จ 38%
คนคบได้: 100 คน, ทดลองคบแต่ไม่เลือก:37 คน, สำเร็จ 37%
คนคบได้: 1,000 คน, ทดลองคบแต่ไม่เลือก:368 คน, สำเร็จ 38%
In [ ]: