InternationalJournalofEmergingTechnologyandAdvancedEngineeringWebsite:www.
ijetae.
com(ISSN2250-2459,ISO9001:2008CertifiedJournal,Volume3,Issue9,September2013)365AnOverviewofUseofLinearDataStructureinHeuristicSearchTechniqueGirishPPotdar1,Dr.
RCThool21AssociateProfessor,ComputerEngineeringDepartment,P.
I.
C.
T,Pune,2Professor,DepartmentofInformationTechnology,SGGSIE&T,Nanded,Abstract—Searchproblemscanbeclassifiedbytheamountofinformationthatisavailabletothesearchprocess.
Whennoinformationisknownapriori,asearchprogrammustperformblindoruninformedsearch.
Whenmoreinformationthaninitialstate,operatorandthegoaltestisavailablethesizeofsearchspacecanusuallybeconstrained.
Thesemethodsareknownasinformedsearchmethods.
Theseoftendependonuseofheuristicinformation.
Aheuristicisaruleofthumb,strategy,trick,simplificationoranyotherkindofdevicewhichdrasticallylimitssearchforsolutionsinlargeproblemspaces.
Heuristicsdoesn'tguaranteeoptimalsolutions;infacttheydonotguaranteeanysolutionatall;theyoffersolutionswhicharegoodenoughmostofthetime.
Optimizationistheprocessoffindingthebestsolutionfromasetofsolutions.
Insomecasesoptimizationmaynotbepossibleorsimplynotefficientenoughtogeneratesolutionsintherequiredtime,soheuristicmaybeusedinstead.
Ifaproblemissolvedrepetitivelyandtheparameterschangeoften,heuristicsaremorelikelytofallapart.
Heuristicperformancemaybeimprovedbyincorporatingoptimizationalgorithms.
Bettersolutionsaregeneratedforabroaderrangeofparametersbyoptimizinginsidesomestepsoftheheuristicsearchalgorithm.
ThepaperexploredifferentheuristicsearchtechniquesandproposeaheuristicsearchmethodthataimstoovercomethedrawbacksofexistingtechniquesbymakingchangesinthedatastructuresusedinordertoachievebestpossiblesolutionandtoimprovetheperformanceefficiencyKeywords—MultiLevelLinkedList,A*algorithm,AO*algorithm,hillclimbing,Generalizedlinkedlist.
I.
INTRODUCTIONArtificialIntelligencetechniquesarebeingusedinanincreasingnumberofcomputerapplicationsincludingspeechrecognition,robotics,expertsystems,drugdesign,andmoleculesynthesis.
Almostallthesearchingalgorithmsgeneratethesearchtree.
ThesesearchingtechniquesarealsocalledastheHeuristicsearchingtechniques[1,12].
Aswebeginfromthestartstate,generatethesearchtree;selecttheavailableoptimalpathtillwegetthegoalstate.
Priorwegoaheadwiththediscussion,let'sdefinetheterm"Heuristic".
Heuristicmeanstodiscover.
Onecandefineheuristicsearch,as"Itisthesearchingprocesswhichtriestolocatethepredefinedstatebyapplyingheuristic.
"Theprogramstatements,whichrefertotheheuristic,arecalled"heuristicfunction".
Onemayidentifythefollowingconditionswhereinwemaymakeuseofheuristicsuchas:1.
Whenanuncertaintyinthestatespaceisforesighted.
2.
Whentheproblemspacedemandsit.
3.
Retrievalwithconstraintandreasoningisessential.
Thesearevariousheuristicsearchingtechniqueslike:BESTFIRSTSEARCH,A*algorithm[3,4,9].
Theaimhereistodesignanovelheuristicalgorithmwithadifferentdatastructurethantheconventionaloneandprovideheuristicsearchalgorithmresultsusingvariousmeasurementsparametersliketime,space,solutionquality,andsearcheffectiveness.
Generally,searchalgorithmscanbeclassifiedintothreegroups.
Theseare,constant-space,linear-space,andexponential-spacestrategies[7,8,9,10].
Inaconstant-spacesearchstrategy,anapplicableruleisselectedandappliedirrevocablywithoutleavinganymeansforreconsiderationatalaterpoint.
Theprocedurerepeatedlyexpandsnodes,inspectingnewlygeneratedsuccessorsandselectingforexpansionthebestamongthesuccessors,whileretainingnofurtherreferencetothefatherortheancestor.
Inlinear-spacesearchstrategies,iftheselectedruledoesn'tleadtoasolution,theintermediatestepsarediscardedandanotherruleisselectedinstead.
Linear-spacestrategiesareperfectlyadequateforproblemsrequiringsmallamountofsearch.
TheAIapplicationsthatusetheheuristictechniqueneed,andhencebuildtheirownheuristicfunctionwithintheapplicationconstraints.
Theexistenceofheuristicfunctionisbasicallytoevaluatethetwocosts,gandh'.
Whereingreferstothecostfromstartstatetothecurrentstate,andh'referstotheevaluatedcostfromcurrentstatetothegoalstate.
InternationalJournalofEmergingTechnologyandAdvancedEngineeringWebsite:www.
ijetae.
com(ISSN2250-2459,ISO9001:2008CertifiedJournal,Volume3,Issue9,September2013)366Sothetotalevaluatedcostfromtheheuristicfunctionf'isthesummationofthetwocostsgandh'.
Thatisf'=g+h'.
Thistotalevaluatedcostrefersto,howfarthegoalstateisfromthecurrentstate.
TheheuristicsearchingtechniqueslikeA*evaluatetheheuristiccostusingheuristicfunction,[2,3].
GRAPHSEARCHprocedure[1,9,10,11,16]usestwolists,OPENandCLOSED,inordertostoresearch-graphnodes.
NodesonOPENarethosetipnodesofthesearch-graphthathavenotbeenselectedforexpansion.
NodesinCLOSEDareeithertipnodesselectedforexpansionandgeneratednosuccessors,ornon-tipnodes.
NodesinOPENaretraversedbytheproceduresothatthe"bestnodeisselectedforexpansion.
Theselectioncanbebasedonavarietyofheuristicideas.
Wheneverthenodeselectedforexpansionisagoalnode,theprocessterminatessuccessfullyandthepathisdeterminedfromthestartnodetothefoundgoalbytracingbackthepointers.
Theprocessterminatesunsuccessfullywheneverthesearchtreehasnoremainingtipnodes(i.
e.
OPENisempty).
Inthiscasethegoalnodeisinaccessiblefromthestartnode.
Normally,Heuristicsearchalgorithmsuseaevaluationfunctionf--real-valuedfunctiontoselectnodesfromOPENforfurtherexpansion.
Thisevaluationfunctioniscomputedforanodeninthesearch-graphasfollows[5,11,14,15]:f(n)=wg(n)+(1-w)h(n)Whereg(n)isthecostofthemshortestpathfromthestartnodetothenoden,h(n)iscostoftheoptimalpathfromntoagoalnode,and0w1istheweightgiventotheestimatesgandh.
Indeterminingtheestimateh,werelyonheuristicinformationavailablefromtheproblemdomain.
Theestimatehiscalledtheheuristicfunction.
TheheuristicfunctionhissaidtobeadmissibleifitisalowerboundontheactualcostTheestimatehissaidtobeconsistentif,foreachpairofnodesnandm,h(m)-h(n)islessthanorequaltotheactualdistancebetweenthetwonodesnandm.
Anybest-firstheuristicsearchalgorithmthatusesanadmissibleheuristicfunctionalwaysterminatewiththeoptimalsolutionpath,ifsuchpathexists.
Suchalgorithmsarecalledadmissiblealgorithms[6,10].
Thememoryrequirementforaheuristicsearchalgorithmisprimarilymeasuredbytheaveragesizeofthesearch-graph.
ThisisequaltothesizeofthetwolistsOPENandCLOSED.
BasicideaTheideaofbehindthispaperistooptimizetheperformanceofheuristicsearchalgorithm.
Hereweproposeanewapproachbymakingchangesinthedatastructuresandmethodsusedinconventionalalgorithms.
NeedTherearemanyexistingheuristicsearchalgorithmslikehillclimbing,A*,AO*,simulatedannealing.
Hillclimbingsuffersfromproblemslikelocalmaximum,plateau,ridge.
ThegracefuldecayofadmissibilityisthemajordrawbackofA*algorithm.
AO*hasoverheadofexpandingthepartialgraphonestateatatimeandrecomputingthebestpolicyoverthegraphaftereachstep.
Mostoftheseexistingheuristicsearchalgorithmsmaintainlistswhichareentered,updatedandmanipulatedon.
Maintainingandmanagingtheselistssimultaneouslyistediousandcomplextask.
Toreducethiscomplexityweuseadatastructurethataimsatmakingagooduseofmemoryspacewithoutcompromisingonthecompletenessandoptimalityofthealgorithm[13].
ScopeThescopeoftheworkisrestricteduseheuristicsearchmethodusingMultiLevelLinkedList(MLL)toimprovetheperformanceofthesealgorithms.
Proposedworkistoimprovetheperformancebyoptimizinginsidethestepsofalgorithmbyremovingtheredundantlistswhichisthemaindrawbackofmostexistingalgorithms.
Thealgorithmmaybeappliedtoanygraphbasedrealtimeapplications.
II.
BLOCKSCHEMATICTheproposedworkcanbeseeninFig1.
Fig1.
Overviewofblockschematic.
InputmoduleHeuristicSystemProcessingUnitComparatorUnitTimeandspacemonitorDisplayUnitInternationalJournalofEmergingTechnologyandAdvancedEngineeringWebsite:www.
ijetae.
com(ISSN2250-2459,ISO9001:2008CertifiedJournal,Volume3,Issue9,September2013)367III.
DATADESCRIPTIONDataconsistsofdatarelatedtotheapplicationthealgorithmwillbeappliedon.
Thealgorithmifimplementedontravellingsalesmanproblemasanexample;wheredataconsistsofthedistancematrixandthestartingcity.
ThedataisorganizedintoMultilinkedlist(MLL)insteadoftheconventionalGeneralizedlinkedlist(GLL).
Fig2-DFDTheaboveDFDgivesdifferentpossiblemodulesthatcanbeusedwhileimplementingtheproposedworkandpossibledatainteractionbetweenthesemodules.
IV.
ARCHITECTURALDESIGNThefigure3describesthecompletemoduledescriptionforthecurrentwork.
Theuseofproposeddatastructurecanresultinsubstantialtimesavingforlargedataset.
Thesamemaybeappliedtographbasedapplicationssuchastravellingsalespersonproblem,graphpartionioningandmanysuchapplications.
Fig3.
ArchitecturalDesignV.
INTERNALSOFTWAREDATASTRUCTUREMultilinklist(MLL)isusedintheproposedalgorithm.
Itisadynamicallocationmethod.
MLLmaintainsaparentlistandsuccessorlist.
Everyparentnodemaintainsitslistofsuccessors.
AlltheseparentnodesarelinkedtogethertoformMLL.
Fig4.
MLLdatastructureInputModuleAcceptInputProcessInputHeuristicSearchSystemTime&SpaceMonitorGenerateoutput&measureperformanceComparetheResultsDisplayPanelResultGraphDataTimeandspaceparametersSolutionOrganizeddataInputModuleOuralgorithmmoduleAO*algorithmmoduleA*algorithmmoduleComparemoduleOutputModuleP1S1S2P2S1S2P3S1S2InternationalJournalofEmergingTechnologyandAdvancedEngineeringWebsite:www.
ijetae.
com(ISSN2250-2459,ISO9001:2008CertifiedJournal,Volume3,Issue9,September2013)368VI.
CONCLUSIONMLLcanbeprovedtobeverypowerfulstructure.
Iftheapplicationpermitsthenonecanusethereferencelistasthesupportinglist,thuscanavoidstoringthesamestatesagainandagain.
Thusweaimatconductingexperimentationdesignedtogiveresultsconcerningtheroleofheuristicsinachievingsearchefficiency.
ThisapproachusingMLLisidealforcommunicationapplications.
REFERENCES[1]EricHansen,RongZhou–"AnytimeHeuristicSearch",JournalofArtificialIntelligenceResearch28,2007.
[2]Davis,H.
,R.
PollackandD.
Golden,TowardsaDomainIndependentMethodforComparingSearchAlgorithmRun-times,Proceedingsofthe6thCanadianConferenceonAI,240-244(1986b).
[3]AnneL.
Gardner"Search:AnOverview",AImagazine,Volume2,Number1,Sept1980.
[4]ABDEL-ELAHAL-AYYOUB,FAWAZMASOUD"HeuristicSearchRevisited",JournalofSystemsandsoftware,Vol55,No2,2000,103-113[5]Hermankaindl,GerhardKainz–"BidirectionalHeuristicsearchreconsidered",JournalofArtificialIntelligenceResearch7,1997.
[6]AlokKumar,AnshulKumar,M.
Balkrihnan"HeuristicSearchasedApproachtoScheduling,AllocationandBindinginDataPathSynthesis"8thInternationalConferenceonVLSIdesign–Jan1995.
[7]JosephCMusto,LKenLauderbaugh"AHeuristicSearchAlgorithmForOnlineSystemIdentfication"IEEEInternationalsymposiumonIntelligentControl,August1991.
[8]Davis,H.
,R.
PollackandD.
Golden,ATechniqueforComparingSearchAlgorithmRuntimes,ProceedingsoftheFourteenthAnnualACMCSC-86,301-308(1986a).
[9]Dechter,R.
andJ.
Pearl,GeneralizedBest-FirstSearchStrategiesandtheOptimalityofA*,JournaloftheACM,Vol.
32,No.
3,505-536(1985).
[10]Korf,R.
,Depth-FirstIterativeDeepening:AnOptimalAdmissibleTreeSearch,ArtificialIntelligence,Vol.
27,97-109(1985).
[11]Bagchi,A.
andA.
Manhanti,SearchAlgorithmsUnderDifferentKindofHeuristics:AComparativeStudy,JournaloftheACM,Vol.
30,1-21(1983).
[12]Annev.
d.
LGardner"SearchanOverview",AIMagazineWinter81.
[13]StevenWalczak"Knowledge-BasedSearchinCompetitiveDomains"[14]LucaDiGasperoAndreaSchaerf"ATabuSearchApproachtotheTravelingTournamentProblem"[15]EugeneCharniakandDrewMcDermott,"IntroductiontoArtificialIntelligence".
AddisonWesley.
[16]NilsJNilsson,"PrincipalsofArtificialIntelligence"NarosaPublishingHouse.
青果网络QG.NET定位为高效多云管理服务商,已拥有工信部颁发的全网云计算/CDN/IDC/ISP/IP-VPN等多项资质,是CNNIC/APNIC联盟的成员之一,2019年荣获国家高薪技术企业、福建省省级高新技术企业双项荣誉。那么青果网络作为国内主流的IDC厂商之一,那么其旗下美国洛杉矶CN2 GIA线路云服务器到底怎么样?官方网站:https://www.qg.net/CPU内存系统盘流量宽带...
spinservers是Majestic Hosting Solutions LLC旗下站点,主要提供国外服务器租用和Hybrid Dedicated等产品的商家,数据中心包括美国达拉斯和圣何塞机房,机器一般10Gbps端口带宽,高配置硬件,支持使用PayPal、信用卡、支付宝或者微信等付款方式。目前,商家针对部分服务器提供优惠码,优惠后达拉斯机房服务器最低每月89美元起,圣何塞机房服务器最低每月...
妮妮云的来历妮妮云是 789 陈总 张总 三方共同投资建立的网站 本着“良心 便宜 稳定”的初衷 为小白用户避免被坑妮妮云的市场定位妮妮云主要代理市场稳定速度的云服务器产品,避免新手购买云服务器的时候众多商家不知道如何选择,妮妮云就帮你选择好了产品,无需承担购买风险,不用担心出现被跑路 被诈骗的情况。妮妮云的售后保证妮妮云退款 通过于合作商的友好协商,云服务器提供2天内全额退款,超过2天不退款 物...
graphsearch为你推荐
三星itunesformgraph支持ipad支持ipadipad连不上wifiipad无法加入网络怎么回事谷歌sbgoogle一下"SB",虽然显示的是baidu排第一,链接的不是baidu.谷歌sb在谷歌里搜SB为什么结果中第一个是百度迅雷下载速度迅雷下载快慢和什么有关苹果5.1.1越狱iphone5.1.1越狱老是越狱失败,说要抹掉数据,怎么抹掉数据不懂,接下来该怎么弄 求大神指教android5.1安卓5.1比4.4流畅很多吗
域名注册申请 外国虚拟主机 万网域名解析 息壤主机 国外bt 空间打开慢 免费网站监控 台湾谷歌地址 hinet 电信主机 免费网页申请 www789 服务器维护 购买空间 服务器硬件配置 杭州电信宽带 asp空间 新网dns 一句话木马 内存 更多