ปัญหาการหาเส้นทางเดินของพนักงานขาย (Traveling Salesman Problem)

นิยามปัญหา

ปัญหาการเดินของพนักงานขายคือปัญหาที่มีผู้ที่ให้ความสนใจพอสมควรในวงการคอมพิวเตอร์ ปัญหาจะกำหนดด้วยกราฟเชื่อมโยงประกอบด้วยปม n ชื่อว่า 1,2,...,n ปมซึ่งเชื่อมกันด้วยเส้นเชื่อมที่มีน้ำหนัก เส้นเชื่อมจากปม i ไปยังปม j จะมีน้ำหนัก c i j > 0 {\displaystyle c_{ij}>0\,} ให้ทำการหาเส้นทางซึ่งเป็นวงที่สั้นที่สุดซึ่งผ่านทุกปมและกลับมาที่จุดเดิม

แนวทางการแก้ปัญหา

โดยไม่เสียนัยสำคัญทั่วไป ให้กราฟเป็นกราฟบริบูรณ์ ซึ่งจะมีบางเส้นเชื่อมที่มีน้ำหนักเป็น +∞ ให้ χ {\displaystyle \chi \,} เป็นเซตของวงจรที่ผ่านทุกปม และให้ S ( x ) {\displaystyle S(x)\,} เป็นความยาวของวงจร x ∈ χ {\displaystyle x\in \chi \,} ปมละหนึ่งครั้งตามเงื่อนไข เราสามารถแทนแต่ละวงจรใน Χ ได้ด้วยการเรียงสับเปลี่ยน(permutation) ของปม 1,2,...,n ซึ่งจริงๆแล้วเราสามารถให้วงจร x = x 1 , x 2 , x 3 , . . . , x n {\displaystyle x=x_{1},x_{2},x_{3},...,x_{n}\,} โดยที่ x 1 = 1 {\displaystyle x_{1}=1} ได้โดยไม่เสียนัยสำคัญทั่วไป เราสามารถแปลงปัญหาทางเดินของพนักงานขายได้เป็นสมการที่ (7) m i n x ( S ( x ) ) = m i n x ( ∑ i = 1 n − 1 c x i , x i + 1 + c x n , 1 ) {\displaystyle min_{x}(S(x))=min_{x}(\sum _{i=1}^{n-1}c_{x_{i},x_{i+1}}+c_{x_{n},1})} (7)

สังเกตว่าขนาดของสมาชิกใน χ {\displaystyle \chi \,} มีขนาดใหญ่มาก | χ | = ( n − 1 ) ! {\displaystyle |\chi |=(n-1)!\,}

จากสมการที่ (7) จะเห็นว่าปัญหาเป็นลักษณะของการหาค่าที่เหมาะสมที่สุดซึ่งสามารถแก้ไขได้ด้วยวิธีการครอส-เอนโทรปี แต่แทนที่จะเป็นลักษณะของการหาค่าที่มากที่สุดจะต้องเปลี่ยนเป็นปัญหาการหาค่าที่น้อยที่สุด โดยหากจะแก้ปัญหาด้วยวิธีการครอส-เอนโทรปีนั้นเราจะต้องกำหนด

1. จะสร้างเส้นทางแบบสุ่มอย่างไร?
2. จะทำการปรับปรุงพารามิเตอร์ในแต่ละรอบการทำงานอย่างไร?
   

ก่อนที่จะหาวิธีการสร้างและปรับปรุงดังกล่าว จะขอนิยามเซตใหม่ขึ้นมาก่อน ให้ χ ^ = ( x 1 , x 2 , . . . , x n ) : x 1 = 1 , x i ∈ 1 , 2 , . . . , n , i = 2 , 3 , . . . , n {\displaystyle {\widehat {\chi }}={(x_{1},x_{2},...,x_{n}):x_{1}=1,x_{i}\in {1,2,...,n},i=2,3,...,n}}

จะเห็นว่าการหาเส้นทางเดินตามเงื่อนไขบนเซตของเส้นทางเดินใน χ ^ {\displaystyle {\widehat {\chi }}\,} จะสมมูลกับปัญหาเส้นทางเดินของพนักงานขายเดิม และเพิ่มนิยาม S ^ ( x ) = S ( x ) {\displaystyle {\widehat {S}}(x)=S(x)} เมื่อ x ∈ χ ^ {\displaystyle x\in {\widehat {\chi }}} มิฉะนั้น S ^ ( x ) = ∞ {\displaystyle {\widehat {S}}(x)=\infty }
ก็จะสามารถเปลี่ยนปัญหาทางเดินของพนักงานขายได้เป็นหาค่าที่ต่ำที่สุดของ S ^ ( x ) {\displaystyle {{\widehat {S}}(x)}\,} บน x ∈ χ ^ {\displaystyle x\in {\widehat {\chi }}\,}

วิธีง่ายๆวิธีหนึ่งที่จะสร้างทางเดินสุ่ม X = ( X 1 , X 2 , . . . , X n ) ∈ χ ^ {\displaystyle X=(X_{1},X_{2},...,X_{n})\in {\widehat {\chi }}} คือการสร้างลูกโซ่มาร์คอฟ(Markov Chain) ของกราฟ G เริ่มต้นที่ปม 1 และหยุดหลังจากขั้นที่ n ให้ P = ( p i j ) {\displaystyle P=(p_{ij})} คือเมตริกซ์ nxn เพื่อเปลี่ยนสถานะไปหนึ่งขั้นสำหรับลูกโซ่มาร์คอฟนี้ หรือจะพูดให้เข้าใจง่ายขึ้นเป็นภาษาทั่วไปก็คือเมตริกซ์ P จะเป็นส่วนที่ใช้เก็บเส้นทางเดินนั่นเอง กำหนดให้ในสมาชิกตามแนวเส้นทแยงมุมของ P เป็น 0 และสมาชิกอื่นๆใน P เป็นจำนวนจริงบวก ความหนาแน่นของความน่าจะเป็น f ( − ; P ) {\displaystyle f(-;P)} ของ X {\displaystyle X} ที่ถูกจำกัดด้วยพารามิเตอร์เป็นเมตริกส์ P นิยามโดย

l n f ( x ; P ) = ∑ r = 1 n ∑ i , j I x ∈ χ ^ i j ( r ) l n ( p i j ) {\displaystyle lnf(x;P)=\sum _{r=1}^{n}\sum _{i,j}I_{x\in {\widehat {\chi }}_{ij}(r)}ln(p_{ij})} (8)
เมื่อ χ ^ i j ( r ) {\displaystyle {\widehat {\chi }}_{ij}(r)} เป็นเซตของเส้นทางทั้งหมดที่ "จำนวนครั้ง" ที่ต้องเดินระหว่างปม i ไปปม j เป็น r ครั้ง

หลังจากนี้จะเริ่มเป็นการคำนวณเชิงคณิตศาสตร์ที่ซับซ้อนหากผู้สนใจสามารถไปศึกษาเพิ่มเติมได้ตามแหล่งอ้างอิง[5]

หากจะสรุปเฉพาะใจความสำคัญให้เข้าใจอย่างสั้นๆสามารถสรุปได้ว่าในขณะนี้เราจะแทนการเปลี่ยนสถานะจากปมปัจจุบันไปยังปมใดๆไ้ด้ด้วยเมตริกซ์ซึ่งก็คือ P = ( p i j ) {\displaystyle P=(p_{ij})} นั่นเอง โดยเมตริกซ์นี้จะได้มาในแต่ละรอบที่ทำการสุ่มตัวอย่างและปรับปรุงพารามิเตอร์ ซึ่งทั้งสองขั้นตอนนี้สามารถทำได้โดย

1. ขั้นสุ่มตัวอย่าง สามารถสุ่มตัวอย่างให้ได้ x ต่างๆได้ตามสมการที่ 8
2. ขั้นปรับปรุง ปรับปรุงพารามิเตอร์ p i j {\displaystyle p_{ij}} ของสมการที่ 8 ได้ด้วยตัวประมาณค่าของ p i j {\displaystyle p_{ij}} ตามสมการที่ (9)

p ^ i j = ∑ k = 1 N I S ^ ( X k ) ≤ γ ∑ r = 1 n I X k ∈ χ ^ i j ( r ) ∑ k = 1 N I S ^ ( X k ) ≤ γ ∑ r = 1 n I X k ∈ χ ^ i ( r ) {\displaystyle {\widehat {p}}_{ij}={\frac {\sum _{k=1}^{N}I_{{\widehat {S}}(X_{k})\leq \gamma }\sum _{r=1}^{n}I_{X_{k}\in {\widehat {\chi }}_{ij}(r)}}{\sum _{k=1}^{N}I_{{\widehat {S}}(X_{k})\leq \gamma }\sum _{r=1}^{n}I_{X_{k}\in {\widehat {\chi }}_{i}(r)}}}} (9)

ซึ่งรายละเอียดการได้มาซึ่งสมการที่ 10 นั้นผู้สนใจสามารถไปค้นคว้าได้ตามแหล่งอ้่างอิงที่ได้ระบุไว้ข้างต้น

เมื่อเราสามารถนิยามว่าจะสุ่มตัวอย่างและปรับปรุงได้อย่างไรแล้วนั้น เราก็จะสามารถสร้างขั้นตอนวิธีเพื่อที่จะแก้ปัญหานี้ได้ดังรหัสเทียมด้านล่าง

รหัสเทียมสำหรับปัญหา

 1  ตั้งค่า                               P                      (            1            )                          =        P                      {\displaystyle P^{(1)}=P\,}   และ                               X                      1                          =        1                      {\displaystyle X_{1}=1\,}   2  t = 0 /*ตัวนับจำนวนรอบ*/ 3  ทำ 4        t = t + 1 5        ตั้งค่าในในหลักที่                               X                      t                                        {\displaystyle X_{t}\,}   ของ                               P                      (            t            )                                {\displaystyle P^{(t)}}   เป็น 0  6        ทำการทำค่าในแต่ละแถวของ                               P                      (            t            )                                        {\displaystyle P^{(t)}\,}   ให้เป็นมาตรฐาน(normalize) //เฉลี่ยค่าในแต่ละแถวให้รวมกันได้ 1  7        ใช้สมการที่ (8) สร้าง                               X                      t            +            1                                        {\displaystyle X_{t+1}\,}   ด้วยพารามิเตอร์                               P                      t                                        {\displaystyle P_{t}\,}   8        ทำการปรับปรุงค่าให้ได้                               P                      (            t            +            1            )                                        {\displaystyle P^{(t+1)}\,}   ในแต่ละแถว i และหลักที่ j ตามสมการที่ (9) 9  ระหว่างที่ t < n-1 // ถ้ายังสร้างลำดับของทางเดินไม่ครบทุกจุด10  คืนค่า                               P                      (            t            )                                        {\displaystyle P^{(t)}\,}