问题描述
PenPlotterProblemBeforetheadventofinkjetandlaserprinters,straightlinedrawingsusedtobeplottedbycolouredpensonlargesheetsofpaper:thepensmovedveryslowlysothiswasatime-consumingprocess.Sincetimeismoney,itwasimportanttodrawfiguresinanoptimalway,usingminimumtime.Inthisassignment,youwillimplementanA*searchprocedureforthepenplotterproblem(withonlyonecolouredpentomakeitsimple,thoughintherealproblem,therewouldbemultiplepenswhichwouldhavetobechangedmanually,costingevenmoretime).[Acontemporaryrelatedproblemisthatofabicyclecourierwhohastopickupmultiplepacketsanddeliverthemtotheirdestinationsaroundthecityinminimumtime,butthisisamuchharderproblemtosolve.]Inyourprogramdesign,makeuseoftheStrategypatterntosupplyaheuristictothesearchprocedure,anddon'tforgettoensurethatyourheuristicisadmissible.Thepapersheetisunderstoodtobelaidoutonagridwithboththex-axisandy-axisrunningfrom0uptoinfinity(notionally).Alldrawingsarefullycontainedinthisquadrantandcanbeassumedtofitonthepage.Linescanalwaysbeassumednottobecontainedinotherlines.Thepenalwaysstartsattheorigin(0,0)butcanfinishanywhere.Linesarespecifiedbythe(x,y)coordinates(inintegers)oftheirendpointsonthegrid.Thepencaneitherdrawalinebetweenanytwopointsormove(withoutdrawinganything)inastraightlinebetweenanytwopoints.Asshouldbeobvious,alinecanbedrawnineitherdirection.Sincewewanttominimizethetotaltimetodrawafigure,assumethepenmovesatconstantspeedsothatanoptimaldrawingisonethatminimizesthetotaldistancemovedbythepenwhilstnotdrawing.Allinputwillbeinafilewithasequenceoflinesofthefollowingform:Linebetween<x1><y2>and<x2><y2>#specifythatthedrawingcontainsalinebetweenthepoints(<x1,y1>)and(<x2>,<y2>)CallyourmainJavafilePenPlotter.java.ReadinputfromafilewhosenameispassedasanargumenttothemainmethodinthecalltojavaPenPlotterandprintoutputtoSystem.out.Formachinemarking,theoutputwillberedirectedtoatextfilethatwillbecomparedtotheexpectedoutput(sodonotprintoutextraspaces,etc.).Forthepurposesofmachinemarking,drawingswillbeusedforwhichthereisonlyoneoptimalsolution,thoughinthecaseofmultipleoptimalsolutions,yourprogramshouldproduceoneofthem.Tohandleinputfromatextfile,asinAssignment1,useJavacodesuchas:try{Scannersc=newScanner(newFileReader(args[0]));#args[0]isthefirstcommandlineargument}catch(FileNotFoundExceptione){}SampleInputForexample,thefollowinginputshoulddrawasimplestarshapedfigurewithsixlinesradiatingfromthepoint(4,4).Theformatandmeaningoftheinputisasfollows(commentsareforexplanationandwillnotappearintheactualinput):Linebetween41and44#thereisalinebetween(4,1)and(4,4)Linebetween44and47#thereisalinebetween(4,4)and(4,7)Linebetween26and44#thereisalinebetween(2,6)and(4,4)Linebetween44and62#thereisalinebetween(4,4)and(6,2)Linebetween66and44#thereisalinebetween(6,6)and(4,4)Linebetween22and44#thereisalinebetween(2,2)and(4,4)SampleOutputTheoutputcorrespondingtotheaboveinputisasfollows(thefirstlineintheoutputshouldindicatethenumberofnodesexploredinthesearch,whichofcoursewillvaryaccordingtotheheuristicused):<n>nodesexploredMovefrom00to22Drawfrom22to44Drawfrom44to66Movefrom66to47Drawfrom47to44Drawfrom44to41Movefrom41to62Drawfrom62to44Drawfrom44to26大意就是给定一些点，并告诉这些点之间哪些要用线连起来，用笔画线，是笔的移动距离最短跪求解题思路