MỘT SỐ THUẬT GIẢI TTNT

Thuật giải tô màuBài toánCho đồ thị đơn vô hướng G = (V,E). Hãy tô mỗi đỉnh của G bằng một màu sao cho: (1) hai đỉnh kề nhau cómàu khác nhau và (2) tổng số lượng màu cần sử dụng là ít nhất.Lưu ý: đồ thị thường được cho dưới dạng hình vẽ hay ma trận kề.Ứng dụngBài toán tô màu đồ thị được ứng dụng đề biểu diễn cho các bài toán thoả mãn ràng buộc (CSP) như lập lịch,lập thời khoá biểu… (xem các bài tập đi kèm)....
Nội dung trích xuất từ tài liệu:
MỘT SỐ THUẬT GIẢI TTNTMỘTSỐTHUẬTGIẢITTNTThuậtgiảitômàuBàitoánChođồthịđơnvôhướngG=(V,E).HãytômỗiđỉnhcủaGbằngmộtmàusaocho:(1)haiđỉnhkềnhaucómàukhácnhauvà(2)tổngsốlượngmàucầnsửdụnglàítnhất.Lưuý:đồthịthườngđượcchodướidạnghìnhvẽhaymatrậnkề.ỨngdụngBàitoántômàuđồthịđượcứngdụngđềbiểudiễnchocácbàitoánthoảmãnràngbuộc(CSP)nhưlậplịch,lậpthờikhoábiểu…(xemcácbàitậpđikèm).Đểgiảicácbàitoántrên,trướctiêntacầnxácđịnhcácđịnhcácyếutốtrongbàitoántươngứngvớicácyếutốcủabàitoántômàuđồthịbằngcáchtrảlờicáchcâuhỏi:•Màucủađồthị–Cầnlàmviệcgì?:việccầnlàmtrongbàitoán(vdxếplịch)chínhlàhànhđộngtômàu,dođómàucủađồthịchínhlàyếutốcầnxácđịnh(đượcnêutrongđềbài).•Đỉnhcủađồthị–Hànhđộngcầnlàmtácđộnglêncáigì?:làthànhphầnđượctácđộnglên•Cung(cạnh)củađồthị–Cácđỉnhràngbuộcvớinhaunhưthếnào?Thuậtgiải:cóhaithuậtgiảichínhthườngđượcápdụngchobàitoántômàulàthuậtgiảitômàutheobậcvàtômàuthamlam(greedy).ThuậttoántômàutrênđồthịdựavàosốbậcLặplạicácbướcsauchođếnkhibậccủatấtcảcácđỉnhbằng0vàcácđỉnhđãđượctômàu:Bước1:TômàuichođỉnhcóbậclớnnhấtBước2:Hạbậc.+Bậccủađỉnhđượctômàuithì:Bậc=0+Bậccủađỉnhcóliênhệvớiđỉnhđượctômàuithì:Bậc=Bậc1Bước3:Cấmtômàuichocácđỉnhvừabịhạbậc.Vídụ:TômàuchobảnđồcácnướckhuvựclánggiềngvớiViệtNamMatrậnkề:matrậnvuôngAn(11x11)trongđó:A[i,j]=1khihaiđỉnhi,jcócạnhnốivà=0trongtrườnghợpngượclại(A[i,i]=0)Cáchtrìnhbàythuậtgiải:XácđịnhbậccủacácđỉnhĐỉnhTQVNLAOMIATHAICAMPHIMALBRUSINGINDOBậc33534304111TômàuDòng1:Bậcvàmàubịcấm(sốnhỏởdưới),đỉnhđượchọnđượctôĐỉnhTQVNLAOMIATHAICAMPHIMALBRUSINGINDOBậcMàu21210213121041111BậcMàu212102121210001010111BậcMàu01120112212100010101211BậcMàu011200120112000101012121BậcMàu000012001230001010123132411222ThuậtgiảitômàugreedyDùngmàuthứnhấttôchomộtđỉnhbấtkỳvàtấtcảcácđỉnhkháccóthểtôđược.Sauđódùngmàuthứhaitiếptụctôchocácđỉnhcònlạitheocùngnguyêntắc…chođếnkhitấtcảcácđỉnhcủađồthịđãđượctômàu.ĐỉnhTQVNLAOMIATHAICAMPHIMALBRUSINGINDOi=11xxx1x1x111i=212x21x12111i=312321x12111i=412321412111Bàitập1:BàitoángiaothôngHãyxácđịnhquytắcbậtcácđèngiaothôngtạimộtbồnbinhvới5tuyếnđườngnhưhìnhBàitập3:BàitoánhộithảoGiảsửcómộthộithảokhoahọcvới9chủđềkhácnhaukýhiệulàa,b,c,d,e,f,g,h,i.Mỗichủđềsẽdiễnratrong1buổivàcácchủđềsaukhôngđượcdiễnrađồngthời:ae,bc,cd,ed,abd,ahi,bhi,dfi,dhi,fgh.Hãybốtrícácchủđềtrênvàocácbuổisaochosốbuổidiễnralàítnhất.Cáctìmkiếmheuristictheonguyênlý“thamlam”Heuristicthamlamlàheuristicthườngđượcdùngđểgiảicácbàitoán“khó”(cácbàitoánkhôngthểvétcạn),vídụnhưbàitoánsau:Bàitoánngườidulịch(TravelingSalemanProblemTSP):Chonthànhphốtrongđóhaithànhphốbấtkỳđềucóđườngnốivớinhau.Hãyxácđịnhlộtrìnhchongườidulịch,xuấtpháttừthànhphốthứnhất,điquatấtcảcácthànhphốcònlại,trởvềthànhphốxuấtphátvớitổngđoạnđườnglànhỏnhất.ThuậtgiảiGTS1Bước1[Khởiđầu]:TOUR={},COST=0;v=1.Bước2[Thămtấtcảcácthànhphố]:Vớik=1đếnn,thựchiệnbước3.Bước3[Chọncạnhkế]:oChọn(v,w)làcạnhcóchiphínhỏnhấttínhtừvđếncácđỉnhchưasửdụngw.oGánTOUR=TOUR+{(v,w)},COST=COST+C(v,w).oSửdụngđỉnhwchobướckếtiếp:v=w.Bước4[Chuyếnđihoànthành]:GánTOUR=TOUR+{(v,1)}Bàitập3:Giảibàitoánngườidulịchvới5thànhphốnhưhình3,sửdụngthuậtgiảiGTS1.Chutrìnhtìmđượccótốtnhấthaykhông?ThuậtgiảiGTS2Nếukhôngbịràngbuộcbởithànhphốxuấtphát,bàitoánnàycóthểđượcgiảitốthơnbằngthuậtgiảiGTS2:xuấtpháttừP(1