Acompletealgorithmtosolvethegraph-coloringproblemHubertoAyaneguiandAlbertoChavez-AragonFacultaddeCienciasBasicas,IngenieriayTecnologia,UniversidadAutonomadeTlaxcala,CalzadadeApizaquitos/n,Apizaco,Tlaxcala,Mexico{hayanegui,albertochz}@gmail.
comAbstract.
TheGraphk-ColorabilityProblem(GCP)isawellknownNP-hardproblemwhichconsistinfindingthekminimumnumberofcolorstopainttheverticesofagraphinsuchawaythatanytwoverticesjoinedbyanedgehavealwaysdifferentcolors.
Manyyearsago,SimulatedAnnealing(SA)wasusedforgraphcoloringtaskobtaininggoodresults;howeverSAisnotacompletealgorithmanditnotalwaysgetstheoptimalsolution.
InthispaperGCPistransformedintotheSatisfiabilityProblemandthenitissolvedusingaalgorithmthatusestheThresholdAcceptingalgorithm(avariantofSA)andtheDavis&Putnamalgorithm.
Thenewalgorithmisacompleteoneandsoitgetsbetterqualitythattheclassicalsimulatedannealingalgorithm.
Keywords:graphcoloring,simulatedannealing,thresholdaccepting,davis&putnam.
1IntroductionLetG=(V,E)beagraphwhereVisasetofverticesandEisasetofedges.
Ak-coloringofGisapartitionofVintoksets{V1,…,Vk},suchthatnotwoverticesinthesamesetareadjacent,i.
e.
,ifv,wbelongtoVi,1ik,then(v,w)notbelongtoE.
Thesets{V1,…,Vk}arereferredtoascolors.
Thechromaticnumber,x(G),isdefinedastheminimumkforwhichGisk-colorable.
TheGraphk-ColorabilityProblem(GCP)canbestatedasfollows.
GivenagraphG,findx(G)andthecorrespondingcoloring.
GCPisaNP-hardproblem[1].
GCPisveryimportantbecauseithasmanyapplications;someofthemareplanningandschedulingproblems[2][3],timetabling[4],mapcoloring[5]andmanyothers.
SinceGCPisaNP-hardproblem,untilnowtherearenotknowndeterministicmethodsthatcansolveditinapolynomialtime[1].
Sonon-deterministicalgorithmshavebeenbuilttosolveit;oneofthemisSimulatedAnnealing(SA)[6]thathasbeenusedonGCPwithgoodresults[7][8].
However,SAisnotacompletealgorithmanditnotalwaysgetstheoptimalsolution.
TheapproachusedinthispaperistotransformGCPintoaSatisfiabilityProblem(orSATproblem)[12]andthenusethealgorithmproposedinthispaper.
WeproposetouseiterativelytheThresholdAccepting(TA)algorithm(avariantofSimulatedAnnealing)[9]andthenaDavisandPutnamalgorithm[10].
2SimulatedannealingandthresholdacceptingSimulatedannealing(SA)[6]isastochasticcomputationaltechniquederivedfromstatisticalmechanicstofindnearglobal-minimum-costsolutionstolargeoptimizationproblems.
Inmanyinstances,findingtheglobalminimumvalueofanobjectivefunctionwithmanydegreesoffreedomsubjecttoconflictingconstraintsisanNP-completeproblem,sincetheobjectivefunctionwilltendtohavemanylocalminimums.
Aprocedureforsolvingoptimizationproblemsofthistypeshouldsamplethesearchspaceinsuchawaythatithasahighprobabilityoffindingtheoptimaloranear-optimalsolutioninareasonabletime.
Overthepastdecade,SAhasproventobeapowerfultechniquethatmeetsthesecriteriaforawiderangeofproblems.
SAexploitsananalogybetweenthewayametalcoolandfreezesintoaminimumenergycrystallinestructure(theannealingprocess)andthesearchforaminimuminamoregeneralsystem.
SAmakesarandomsearchwhichnotonlyacceptschangesthatincreaseitscostfunctionf,butalsosomethatdecreaseit.
Forthisreason,SAusesacontrolparameterc,whichbyanalogywiththeoriginalapplicationisknownasthe"SystemTemperature",cstartsouthighandgraduallydecreases.
AdeterioratingrandommovefromsolutionSitoSjisacceptedwithaprobabilityexp-(f(Sj)-f(Si))/c.
Ifthismoveisnotdeteriorating(thenewsolutionSjisbetterthanthepreviousoneSi)thenitisacceptedandanewrandommoveisproposedagain.
Whenthetemperatureishigh,abadmovecanbeaccepted.
Asctendstozero,SAbecomesmoredemandingthroughacceptjustbettermoves.
Thealgorithmforminimizationisshownbelow:ProcedureSIMULATEDANNEALINGBeginINITIALIZE(Si=initial_solution,c=initial_temperature)k=0RepeatRepeatSj=PERTURBATION(Si)IfCOST(Sj)random[0,1)ThenSi=SjUntilstochasticequilibriumk=k+1c=COOLING(c)UntilthermalequilibriumEndTheINITIALIZEfunctionstartstheinitialsolutionSiandtheinitialtemperaturec.
ThePERTURBATIONfunctionmakesarandomperturbationfromSitogenerateaneighborhoodsolutionSj.
TheCOSTfunctiongetsthecostfromasolution.
TheINC_COSTfunctiongetsthedifferenceincostbetweenSjandSi.
Finally,theCOOLINGfunctiondecreasestheactualtemperatureparameterc.
AvariantofSimulatedAnnealing(SA)istheThresholdAcceptingmethod(TA).
ItwasdesignedbyDueck&Scheuer[9]inordertogetamoreefficientalgorithmthanSimulatedAnnealing.
Theprincipaldifference,betweenSAandTA,isthemechanismofacceptingthesolutionrandomlychosenfromthesetofneighborsofthecurrentsolution.
WhileSAusesaprobabilisticmodel(seeequation(1)),TAusesastaticmodel:ifthedifferencebetweenthecostvaluesofthechosensolutionSjandthecurrentoneSiissmallerthanathresholdT(ortemperature),TAacceptsmovingtothechosensolution.
Otherwiseitstaysatthecurrentsolution.
Again,thethresholdparameterTisapositivecontrolparameterwhichdecreaseswithincreasingnumberofiterationsandconvergestovaluenearto0.
Henceforth,ineveryiterationsomesolutiondeteriorationareallowed;thisdeteriorationdependsonthecurrentthresholdT(seeequation(2));inthiswayonlyimprovingsolutionswithalmostnonedeteriorationsolutionareacceptedattheendoftheprocess.
p(S1,S2)=exp(min{f(S1)-f(S2),0}/c)(1)COST(Sj)ThiscouldbebecauseTAdoesnotcomputetheprobabilisticfunction(1)anddoesnotexpendalotoftimemakingrandomdecisions.
TheThresholdAcceptingalgorithmforminimizationisthefollowing:ProcedureTHRESHOLDACCEPTINGBeginINITIALIZE(Si=initial_solution,T=initial_thresholdortemperature)k=0RepeatRepeatSj=PERTURBATION(Si)E=COST(Sj)–COST(Si)IfESALAusesSimulated-annealingapproachwithtwomainloops:internalloopnamedMetropolisCycleandexternalloopcalledTemperatureCycle.
Numberofiterationsininternalandexternalloopusuallyaretunedexperimentally[6],[9].
However,recentlyananalyticalmethodusingaMarkovmodelwasproposedtotuneTAsolvingSATproblems.
ExternalloopexecutedfromainitialtemperatureTiuntilafinaltemperatureTfandtheinternalloopbuildsaMarkovchainoflengthLkwhichdependsonthetemperaturevalueTk(krepresentsthesequenceindexinTemperaturecycle).
AstrongrelationexistsbetweenTkandLkinawaythat:IfTk,Lk0andifTk0,Lk.
(3)DuetoTAisappliedthroughaneighborhoodstructure,V,(PERTURBATIONfunctionmakesarandomperturbationfromSitogenerateaneighborhoodsolutionSj),themaximumnumberofdifferentsolutionsthatcanberejectedfromSiisthesizeofitsneighborhoods,|VSi|.
ThenthemaximumlengthofaMarkovchaininaTAalgorithmisthenumberofsamplesthatmustbetakeninordertoevaluateanexpectedfractionofdifferentsolutionsfromVSiatthefinaltemperatureTf,thisis:Lf=C|VSi|.
(4)whereCvariesfrom1C4.
6(explorationfrom63%until99%),LfisthelengthoftheMarkovchainatTf.
From(3),LkmustbeincrementedinasimilarbutinversewaythatTkisdecremented.
ThenforthegeometricreductioncoolingfunctionusedbyKirkpartick[6],andDueckandScheuer[9],Tk+1=Tk.
(5)theincrementalMarkovchainfunctionmustbe:Lk+1=Lk.
(6)where=exp((lnLf–lnLi)/n).
(7)Here,LiisthelengthoftheMarkovchainatTi,usuallyLi=1,andnisthenumberoftemperaturestepsfromTitoTfthrough(5).
Now,themaximumandminimumcostincrementproducedthroughtheneighborhoodstructureare:ZVmax=Max{COST(Sj)–COST(Si)}.
(8)ZVmin=Min{COST(Sj)–COST(Si)}.
(9)forallSjVSi,andforallSiSThenTiandTfmustbecalculatedas:Ti=ZVmax.
(10)TfZVmin.
(11)ThiswayofdeterminingtheinitialtemperatureenableTAtoacceptanypossibletransitionatthebeginningoftheprocess,sinceTiissetasthemaximumdeteriorationincostthatmaybeproducedthroughtheneighborhoodstructure.
Similarly,TfenablesTAtohavecontroloftheclimbingprobabilityuntilthealgorithmperformsagreedylocalsearch.
3Davis&PutnamMethodSatisfiablityProblem[12](orSAT)isveryimportantincomplexitytheory.
Letbeapropositionalformulalikeformula(12):F=F1&F2&…&Fn(12)whereeveryFiisadisjunction.
EveryFiisadisjunctionofpropositionalformulassuchasX1vX2v.
.
vXr.
EveryFiisaclauseandeveryXjisaliteral.
Everyliteralcantakeatruthvalue(0orfalse,1ortruth).
InSatisfiabilityproblemasetofvaluesfortheliteralsshouldbefound,insuchawaythattheevaluationof(12)betrue;otherwiseif(12)isnottrue,wesaythatFisunsatisfiable.
Besideswesaythat(12)isinConjunctiveNormalFormorCNF.
TheDavis&Putnammethodiswidelyregardedasoneofthebestdeterministicmethodsfordecidingthesatisfiability[12]ofasetofpropositionalclauses[10].
Itisalsoacompleteresolutionmethod.
Thisprocedurecallsitselfafterrewritingtheinputformulaaccordingtoanumberofrulesforgeneratingasmallerformulawiththesametruthvalue.
TherulesusedfortheDavis&Putnammethodare:Rule1:iftheinputformulahasnoclauses,thenitissatisfiableRule2:ifithasaclausewithnoliterals,itisunsatisfiableRule3:ifithasaclausewithexactlyoneliteral,thenmaketheliteraltrueandrewritetheformulaaccordinglyRule4:ifsomevariableappearonlypositivelyornegatively,thenpickonesuchvariableandassignavaluetoittomaketheliteraltrue,andrewritetheformulaaccordinglyIfnonerulecouldbeapplied,onepicksupanarbitraryvariableasabranchingpointandtwonewformulasarederivedbyassigning0and1tothisvariable.
Ifoneofthecallsreturnswiththepositiveanswertheinputissatisfiable;otherwise,itisunsatisfiable.
TheDavis&Putnamalgorithmisshownbelow:FunctionDAVIS-PUTNAM(Informula:clauseslist)BeginREDUCE(formula,vreduce)IfformulaisemptyThenReturnvreduceElseIfformulahasaclausewithnoliteralsThenReturnfailElseChoosealiteralVfromformulavaluation=DAVIS-PUTNAM(SUBSTITUTION(true,V,formula))Ifvaluation!
=failThenReturnADD(V=true,vreduce,valuation)valuation=DAVIS-PUTNAM(SUBSTITUTION(false,V,formula))Ifvaluation!
=failThenReturnADD(V=false,vreduce,valuation)ReturnfailEndifEndDAVIS-PUTNAMFunctionSUBSTITUTION(TF,V,formula)BeginForEachoneclauseCInformulaDoIf[CcontainVandTF=true]or[Ccontain~VandTF=false]ThendeleteCfromformulaElseIf[CcontainVandTF=false]or[Ccontain~VandTF=true]ThendeleteVfromCEndifEndforReturnformulaEnd_SUBSTITUTIONFunctionREDUCE(InOut:formula,vreduce)Beginvreduce=emptyWhileexistsclauseCInformulawithexactlyoneliteralLIfLispositivevariableVThenformula=SUBSTITUTION(true,V,formula)vreduce=CONS(V=true,vreduce)ElseIfLisnegativevariableVThenformula=SUBSTITUTION(false,V,formula)vreduce=CONS(V=false,vreduce)EndifEndwhileReturn(formula)End_REDUCETheDAVIS-PUTNAMfunctionisthemainfunctionanditselectsrandomlyaliteraltosetatrueagroupofvaluesinordertocreateunitaryclauses.
Ifthattruesetvaluesisnotthecorrectsolutionthecomplementsetoftruevaluesistried.
Ifthenewassignmentisneitherasatisfiablesolution,thentheformulaisunsatisfiable.
ThefunctionSUBTITUTIONmakesthepropagationofoneliteraloveralltheclausesinformula,deletingclauseswhereoccursthepositiveliteralLanditsvalueis1(true).
Thereforetheclauseswhere~Loccurscandeletethatliteral.
TheREDUCEfunctioncarriesoutthesearchofunitaryclauses,sothatitcanbepossiblepropagatethroughthefunctionSUBSTITUTION.
4GraphColoringthroughAcceptingandDavis&PutnamInformallycoloringagraphwithkcolorsorGraphk-ColorabilityProblem(GCP)isstatedasfollows:IsitpossibletoassignoneofkcolorstoeachnodeofagraphG=(V,E),suchthatnotwoadjacentnodesbeassignedthesamecolorIfanswerispositivewesaythatthegraphisk-colorableandkisthechromaticnumberx(G).
ItispossibletotransformGraphk-ColorabilityProblem(GCP)intoSatisfiabilityproblem(SAT);thatmeansthatforagivengraphG=(V,E)andanumberk,itispossibletoderiveaCNFformulaFsuchthatFissatisfiableonlyinthecasethatGisk-colorable.
TheformulationofGCPasSATismadeassigningXBooleanvariablesasfollow:1)TakeeverynodeandassignaBooleanvariableXijforeverynodeiandcolorj;thedisjunctionofallthesevariables.
Inthiswayeverynodewillhaveatleastonecolor.
Therefore,inthecaseoffigure1,wehavetheclauses:Node1:X11vX12vX13vX14Node2:X21vX22vX23vX24Node3:X31vX32vX33vX34Node4:X41vX42vX43vX442)Toavoidthefactthatanodehasmorethatonecolor,addtheformulaXij~Xik3)Inordertobesurethattwonodes(Vi,Vj)connectedwithanarchavedifferentcolors,addaclausesuchthatifVihascolork,Vjshouldnotbecolorwiththiscolor.
ThisclauseiswritingasXik~Xjk.
4)Inordertoknowwhichnodesareconnectedwithanedge,anadjacentmatrixAofthegraphisneeded;itselementsare:1ifiisconnectedwithjAij=0otherwiseFig.
1.
GraphcoloringexampleThereductionofagraphtotheConjunctiveNormalForm(CNF)generatessomanyclausesevenforsmallgraphs.
Forexample,forafullgraphwith7nodes(42edges),308clauseswith98literalscanbegenerated.
IfweuseDavis&Putnamalgorithmtocoloragraph,wecouldstartcoloringwithRcolors(thegraph'sdegreeorfromanumbergiven).
Ifitisnotpossibletocolorit,thenwecanincreaseRandtryagain.
Duetofindalargechromaticnumberx(G)isaveryhardtaskforacompletemethodasDavis&Putnam(itdemandsmanyresources),weneedanincompletemethodtohelpinthistask.
ForthisreasonwehavechosentheThresholdAcceptingmethod.
TAwillsearchthechromaticnumber,butasitisknownTAnotalwaysgettheoptimalsolution.
Bythisreason,thenumberfoundbyTAissendtoaDavis&Putnamprocedure,andthisonewillgettheoptimalsolution.
Thecompleteprocessisshowninthefigure2.
Fig.
2.
DescriptionofthecoloringprocessAnygraphcanbecoloredwithGmax+1colors,whereGmaxrepresentsthegraphdegree.
Forthisreason,TAwilltrycoloringwithGmaxcolors.
IfTAgetsasuccess,thenTAwilltrytocolorwithGmax-1,andsoon.
WhenTAfinishes,itsendstotheoutputtheminimumkofcolorsfounded.
Inothercase,whenTAcannotcolorwithGmaxcolors,thenitwillsendk=Gmax+1toDavis&Putnamprocedure.
Fig.
3.
BinarypartitionsDavis&Putnamwillattempttodecreasethevalueofkthroughbinarypartitions.
Thefirstattempt,Davis&Putnamwillchoosethenumberofcolorsgivenby(1+k)/2.
Ifthecoloringisright,itwillcolorwith(1+(1+k)/2)/2colors,i.
e.
,thelefthalf.
Otherwise,thealgorithmwillcolorwith((1+k)/2+k)/2colors,therighthalf.
ThisprocesscontinuesuntilDavis&Putnamcannotdecreasek.
So,thechromaticnumberwasfound.
Thissituationisshowninfigure2.
Thefigure3showsanexamplewhereTAfoundthenumbernineasitsbettersolutionanditissendtoDavis&Putnamprocedure.
WhenDavis&PutnamtakesthelastTAsolution,usingbinarypartitionsandotherrulestheoptimalsolutioniswaited.
Forexampleinthecaseofthefigure3,ifDavis&Putnamcannotcolorwithfivecolors,itmovestootheralternative,tryingwithsevencolors.
Finally,inthelastpartition,i.
e.
(7+9)/2,cannotcolorthegraphandsotheresultisachromaticnumberequaltonine.
5ConclusionInthispaperwepresentedanalgorithmbasedonThresholdAcceptingandDavis&Putnam,tosolvetheGraphk-ColorabilityProblem.
BecausethisproblemisanNP-hardproblemthereisnotaknowndeterministicefficient(polinomial)method.
Non-deterministicmethodsareingeneralmoreefficientbutanoptimalsolutionisnotguarantee.
Thismethodisanewalternativethatpromisestobemoreefficientthatthepreviousones.
Themaincontributionsofthispaperareenumeratedbelow.
1)Weproposedawaytotransformthegraphk-colorabilityproblemintoasatisfiabilityproblem.
2)InordertosolvetheformerproblemweproposedanewapproachwhichmakesuseofthethresholdacceptingandDavis&Putnamalgorithms.
3)Theresultingalgorithmiscompleteandusingitwecangetbetterresultsthatthewell-knownsimulatedannealingalgorithm.
References1.
Garey,M.
R.
andJohnson,D.
S.
,ComputersandInteractability:AGuidetotheTheoryofNP-Completeness,Freeman,SanFrancisco,1979.
2.
Stecke,K.
,DesignPlanning,SchedulingandControlProblemsofFlexibleManufacturing,AnnalsofOperationsResearch,Vol.
3,1985,pp.
3-12.
3.
Leighton,F.
T.
,AGraphColoringAlgorithmforLargeSchedulingProblems,J.
Res.
Nat.
Bur.
Standard,Vol.
84,No.
6,1979,pp.
489-506.
4.
Wood,D.
C.
,ATechniqueforColoringaGraphApplicabletoLargeScaleTimetableProblems,ComputerJournal,Vol.
12,1969,pp.
317-322.
5.
Brelez,D.
,NewMethodstoColorVerticesofaGraph,Comm.
ACM,Vol.
22,1979,pp.
251-256.
6.
Kirkpatrick,S,Gelatt,C.
D.
,Vecchi,M.
P.
,OptimizationbySimulatedAnnealing,Science,No.
220,1983,pp.
671-680.
7.
Chams,M.
,A.
HertzandD.
deWerra,SomeExperimentswithSimulatedAnnealingforColoringGraphs,EuropeanJournalofOperationalResearch,Vol.
32,1987,pp.
260-266.
8.
Johnson,D.
S.
,Aragon,C.
R.
,McGeoch,L.
A.
,Schevon,C.
,OptimizationbySimulatedAnnealing:AnExperimentalEvaluation;PartII:GraphColoringandNumberPartitioning,Oper.
Res.
,No.
39,1991,pp.
378-406.
9.
DueckGunter,ScheuerTobias,ThresholdAccepting:AGeneralPurposeOptimizationAlgorithmAppearingSuperiortoSimulatedAnnealing.
JournalofComputationalPhysics,No.
90,1990,pp.
161-175.
10.
M.
DavisandH.
Putnam,AComputingProcedureforQuantificationTheory.
JournaloftheAssociationforComputingMachinery,Vol.
7,No.
1,1960,pp.
201-215.
12.
ScienceandTechnologyCenterinDiscreteMathematicsandTheoreticalComputerScience,"SatisfiabilityProblem:TheoryandApplications",DimacsSeriesinDiscreteMathematicsandTheoreticalComputerScience,Editors:JunGu,PanosPardalos,Ding-Zhu.
物语云计算(MonogatariCloud)是一家成立于2016年的老牌国人商家,主营国内游戏高防独服业务,拥有多家机房资源,产品质量过硬,颇有一定口碑。本次带来的是美国圣何塞 Equinix 机房的高性能I9-10980XE大带宽VPS,去程CN2GIA回程AS9929,美国原生IP,支持解锁奈飞等应用,支持免费安装Windows系统。值得注意的是,物语云采用的虚拟化技术为Hyper-V,资源全...
美得云成立于2021年,是一家云产品管理服务商(cloud)专业提供云计算服务、DDOS防护、网络安全服务、国内海外数据中心托管租用等业务、20000+用户的选择,43800+小时稳定运行香港特价将军澳CTG+CN2云服务器、采用高端CPU 优质CN2路线 SDD硬盘。香港CTG+CN22核2G3M20G数据盘25元点击购买香港CTG+CN22核2G5M30G数据盘39元点击购买香港CTG+CN...
RAKsmart 商家我们肯定不算陌生,目前主要的营销客户群肯定是我们。于是在去年的时候有新增很多很多的机房,比如也有测试过的日本、香港、美国机房,这不今年有新增韩国机房(记得去年是不是也有增加过)。且如果没有记错的话,之前VPS主机也有一次磁盘故障的问题。
这不今天有看到商家新增韩国服务器产品,当然目前我还不清楚商家韩国服务器的线路和速度情况,后面我搞一台测试机进行...
rewrite规则为你推荐
域名注册公司公司域名注册在哪个网站上注册好独立ip主机独立IP虚拟主机的主机弊端vpsvps是什么?域名服务商比较专业的域名服务商有哪些?好的域名和域名服务商没关系吧?郑州虚拟主机请问郑州哪家公司可以做网站还有相应服务器服务的?apache虚拟主机linux操作系统Apache配置虚拟主机天津虚拟主机在天津哪个地方能买到较好的价格又实惠还可以送货上门的虚拟主机!虚拟主机mysql如何连接虚拟主机中的MYSQL东莞虚拟主机在东莞服务器租用怎么选择windows虚拟主机在windows上怎么安装虚拟机
已备案未注册域名 私服服务器租用 ibrs 湖南服务器托管 godaddy域名证书 河南m值兑换 169邮箱 酷番云 绍兴电信 架设邮件服务器 外贸空间 网购分享 备案空间 西安服务器托管 主机管理系统 畅行云 国外免费云空间 阿里dns 万网服务器 privatetracker 更多