ปัญหากลุ่มพรรคพวกเป็นเอ็นพีบริบูรณ์เนื่องมาจากความเป็นเอ็นพีบริบูรณ์ของปัญหาเซตอิสระ เนื่องมาจากว่าถ้ามีกลุ่มพรรคพวกที่มีขนาด k ในกราฟ G จะมีเซตอิสระขนาด k ในกราฟ เสมอ เพราะฉะนั้นเราสามารถเห็นได้อย่างชัดเจนว่าปัญหากลุ่มพรรคพวกกับปัญหาเซตอิสระสามารถ ลดรูป ระหว่างสองปัญหาได้
ขั้นตอนวิธี
วิธีแก้ปัญหานี้แบบตรงไปตรงมาก็คือการพิจารณากราฟย่อยทุกรูปแบบของ G ที่ประกอบด้วย k จุด และตรวจสอบว่า กราฟย่อยนั้นเป็นกราฟบริบูรณ์หรือไม่ วิธีนี้ใช้เวลาการทำงานเป็นฟังก์ชันพหุนามกับ n หากเรามองว่า k เป็นค่าคงที่ แต่ในปัญหานี้ k ถูกกำหนดเป็นอินพุตด้วย เพราะฉะนั้นวิธีนี้ใช้เวลานานเกินกว่าจะรับได้หาก n มีค่ามากๆ และ k มีค่าประมาณครึ่งหนึ่งของ n
เราลองมาดูวิธีแก้ปัญหาแบบฮิวริสติกกันบ้าง วิธีฮิวริสติกที่เป็นไปได้แบบหนึ่งก็คือ เริ่มต้นจากกราฟ G มองว่าแต่ละจุดเป็นกลุ่มพรรคพวกที่มีขนาดเท่ากับ 1 เราจะรวมกลุ่มพรรคพวกA และ B เข้าด้วยกันเมื่อมีเส้นเชื่อมระหว่างทุกจุดใน A กับทุกจุดใน B และทำการรวมกลุ่มพรรคพวกที่สามารถรวมกันได้เข้าด้วยกันเรื่อยๆ จนกระทั่งไม่มีกลุ่มพรรคพวกที่สามารถรวมกันได้อีก เราสามารถเห็นได้ชัดเจนว่าด้วยวิธีนี้ เราจะได้ผลลัพธ์เป็นกลุ่มพรรคพวกที่เป็น maximal independent set แต่ไม่จำเป็นว่าจะต้องเป็นกลุ่มพรรคพวกที่ใหญ่ที่สุดบนกราฟ เพราะว่าที่บางขั้นตอนของฮิวริสติกอาจจะทำให้เรารวมกลุ่มสองกลุ่มที่ไม่ควรจะถูกรวมกันในคำตอบที่ดีที่สุด วิธีนี้สามารถทำได้อย่างมีประสิทธิภาพโดยการใช้ขั้นตอนวิธีแบบ union-find
อ้างอิง
Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0716710455. A1.2: GT19, pg.194.
สิงหาคม 04, 2021
ญหากล, มพรรคพวก, งกฤษ, clique, problem, เป, นหน, งในป, ญหากราฟท, เป, นเอ, นพ, บร, รณ, จน, โดยร, ชาร, คาร, ปในป, 2515, โดยท, กล, มพรรคพวก, clique, ภายในกราฟหมายถ, งเซ, ตของจ, ดท, ระหว, างค, ใดๆม, านเช, อมก, หร, อพ, ดอ, กอย, างก, กล, มพรรคพวกเป, complete, induce. pyhaklumphrrkhphwk xngkvs Clique problem epnhnunginpyhakrafthiepnexnphibriburn phisucnodyrichard kharpinpi 2515 odythiklumphrrkhphwk clique phayinkrafhmaythungestkhxngcudthirahwangkhuidmidanechuxmkn hruxphudxikxyangkkhux klumphrrkhphwkepn complete induced subgraph ihdutwxyangidinrup sungcaehnidchdecnwa rahwangcud 1 2 aela 5 midanechuxmthungknhmd inkrninieraeriykwathngsamcudniepnklumphrrkhphwkthimikhnadethakb 3pyhaklumphrrkhphwkkhux pyhathitdsinwakrafthikahndmiklumphrrkhphwkthimikhnad k displaystyle k hruxim erasamarthphisucnidimyaknkwapyhanixyuinexnphi ephraawathaerakahndcudthixyuinklumphrrkhphwkmaih erasamarthtrwcsxbidinewla O k 2 displaystyle O k 2 wacudthikahndmaihepnklumphrrkhphwkcringhruxim eraxaccaniyampyhaniidxikaebbinechingkhxng optimization problem kkhux ihhaklumphrrkhphwkthiihythisudinkrafthikahndpyhaklumphrrkhphwkepnexnphibriburnenuxngmacakkhwamepnexnphibriburnkhxngpyhaestxisra enuxngmacakwathamiklumphrrkhphwkthimikhnad k inkraf G camiestxisrakhnad k inkraf G displaystyle bar G esmx ephraachannerasamarthehnidxyangchdecnwapyhaklumphrrkhphwkkbpyhaestxisrasamarthldrup rahwangsxngpyhaidkhntxnwithi aekikhwithiaekpyhaniaebbtrngiptrngmakkhuxkarphicarnakrafyxythukrupaebbkhxng G thiprakxbdwy k cud aelatrwcsxbwa krafyxynnepnkrafbriburnhruxim withiniichewlakarthanganepnfngkchnphhunamkb n hakeramxngwa k epnkhakhngthi aetinpyhani k thukkahndepnxinphutdwy ephraachannwithiniichewlananekinkwacarbidhak n mikhamak aela k mikhapramankhrunghnungkhxng neralxngmaduwithiaekpyhaaebbhiwristikknbang withihiwristikthiepnipidaebbhnungkkhux erimtncakkraf G mxngwaaetlacudepnklumphrrkhphwkthimikhnadethakb 1 eracarwmklumphrrkhphwkA aela B ekhadwyknemuxmiesnechuxmrahwangthukcudin A kbthukcudin B aelathakarrwmklumphrrkhphwkthisamarthrwmknidekhadwykneruxy cnkrathngimmiklumphrrkhphwkthisamarthrwmknidxik erasamarthehnidchdecnwadwywithini eracaidphllphthepnklumphrrkhphwkthiepn maximal independent set aetimcaepnwacatxngepnklumphrrkhphwkthiihythisudbnkraf ephraawathibangkhntxnkhxnghiwristikxaccathaiherarwmklumsxngklumthiimkhwrcathukrwmkninkhatxbthidithisud withinisamarththaidxyangmiprasiththiphaphodykarichkhntxnwithiaebb union findxangxing aekikhRichard Karp Reducibility Among Combinatorial Problems Proceedings of a Symposium on the Complexity of Computer Computations 1972 Michael R Garey and David S Johnson 1979 Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman ISBN 0716710455 A1 2 GT19 pg 194 ekhathungcak https th wikipedia org w index php title pyhaklumphrrkhphwk amp oldid 4715189, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,