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.

justhost:“第4次VPS测评”,8.3元/月,200M带宽,不限流量,KVM虚拟,4个俄罗斯机房应有适合你的

justhost.ru官方来消息说已经对网络进行了比较全面的优化,针对中国电信、联通、移动来说,4个机房总有一个适合中国用户,让站长进行一下测试,这不就有了这篇有关justhost的VPS的第四次测评。本帖主要关注的是网络,对于其他的参数一概不管! 官方网站:https://justhost.ru 最低配VPS:8.3元/月,KVM,512M内存,5G硬盘,200M带宽,不限流量 购买链接:...

酷番云78元台湾精品CN2 2核 1G 60G SSD硬盘

酷番云怎么样?酷番云就不讲太多了,介绍过很多次,老牌商家完事,最近有不少小伙伴,一直问我台湾VPS,比较难找好的商家,台湾VPS本来就比较少,也介绍了不少商家,线路都不是很好,有些需求支持Windows是比较少的,这里我们就给大家测评下 酷番云的台湾VPS,支持多个版本Linux和Windows操作系统,提供了CN2线路,并且还是原生IP,更惊喜的是提供的是无限流量。有需求的可以试试。可以看到回程...

桔子数据58元/月 ,Cera美西云服务器 2核4G 50G数据盘 500M带宽 1000G流量

桔子数据(徐州铭联信息科技有限公司)成立于2020年,是国内领先的互联网业务平台服务提供商。公司专注为用户提供低价高性能云计算产品,致力于云计算应用的易用性开发,并引导云计算在国内普及。目前公司研发以及运营云服务基础设施服务平台(IaaS),面向全球客户提供基于云计算的IT解决方案与客户服务,拥有丰富的国内BGP、双线高防、香港等优质的IDC资源。 公司一直秉承”以人为本、客户为尊、永...

rewrite规则为你推荐
vpsVPS是什么?免费vps服务器请推荐一个免费的云服务器?香港虚拟空间最稳定香港虚拟主机空间在哪里?免备案虚拟空间备案退两次了。哪里有免备案空间虚拟主机用?asp网站空间什么是ASP空间?jsp虚拟主机虚拟主机不能支持JSP的吗虚拟主机试用购买虚拟主机为什么商家会让你试用和测试?免费域名怎么申请免费个人域名?域名邮箱域名是干什么的?域名邮箱和自己注册的邮箱有什么不一样吗?买域名在那里买域名 多少钱一年? 在线等 。。。!!!!!!!
虚拟主机控制面板 免费cn域名注册 a2hosting bluehost 韩国空间 韩国电信 免费名片模板 免费ftp站点 小米数据库 idc资讯 泉州电信 静态空间 无限流量 台湾google 大化网 web是什么意思 ipower 服务器是什么意思 大硬盘补丁 ddos攻击器 更多