Dueckrewrite规则

rewrite规则  时间:2021-01-12  阅读:()
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.

稳爱云(26元),香港云服务器 1核 1G 10M带宽

稳爱云(www.wenaiyun.com)是创建于2021年的国人IDC商家,主要目前要出售香港VPS、香港独立服务器、美国高防VPS、美国CERA VPS 等目前在售VPS线路有三网CN2、CN2 GIA,该公司旗下产品均采用KVM虚拟化架构。机房采用业内口碑最好香港沙田机房,稳定,好用,数据安全。线路采用三网(电信,联通,移动)回程电信cn2、cn2 gia优质网络,延迟低,速度快。自行封装的...

ZJI(月付480元),香港阿里云专线服务器

ZJI是成立于2011年原Wordpress圈知名主机商—维翔主机,2018年9月更名为ZJI,主要提供香港、日本、美国独立服务器(自营/数据中心直营)租用及VDS、虚拟主机空间、域名注册业务。本月商家针对香港阿里云线路独立服务器提供月付立减270-400元优惠码,优惠后香港独立服务器(阿里云专线)E3或者E5 CPU,SSD硬盘,最低每月仅480元起。阿里一型CPU:Intel E5-2630L...

HostKvm($4.25/月),俄罗斯CN2带宽大升级,俄罗斯/香港高防限量5折优惠进行中

HostKvm是一家成立于2013年的国外VPS服务商,产品基于KVM架构,数据中心包括日本、新加坡、韩国、美国、俄罗斯、中国香港等多个地区机房,均为国内直连或优化线路,延迟较低,适合建站或者远程办公等。本月,商家旗下俄罗斯、新加坡、美国、香港等节点带宽进行了大幅度升级,俄罗斯机房国内电信/联通直连,CN2线路,150Mbps(原来30Mbps)带宽起,目前俄罗斯和香港高防节点5折骨折码继续优惠中...

rewrite规则为你推荐
美国虚拟主机美国虚拟主机购买具体注意什么。。域名注册商最具权威的域名注册商域名空间代理哪里的域名空间商比较好?免费国外空间哪些免费的国外空间最好?速度快.功能大?免费vps服务器如何免费搭建自己的vps服务器香港虚拟空间最稳定香港虚拟主机空间在哪里?asp网站空间什么是ASP空间?万网虚拟主机万网免费虚拟主机和收费虚拟主机有什么区别虚拟主机mysql如何连接虚拟主机中的MYSQL论坛虚拟主机虚拟主机禁止放论坛
西安虚拟主机 vps代理 服务器配置技术网 t楼 Hello图床 suspended ibox官网 admit的用法 789电视网 美国免费空间 cdn加速是什么 国外ip加速器 登陆空间 畅行云 阿里云邮箱登陆地址 镇江高防服务器 时间服务器 linux服务器系统 装修瓦工招聘 招聘瓦工 更多