Dalarna University's logo and link to the university's website

du.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Optimal Path Searching through Specified Routes using different Algorithms
Högskolan Dalarna, Akademin Industri och samhälle, Datateknik.
2009 (engelsk)Independent thesis Advanced level (degree of Master (Two Years))Oppgave
Abstract [en]

To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes. To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook

sted, utgiver, år, opplag, sider
Borlänge, 2009. , s. 37
Emneord [en]
Routing problem, Shortest Path, Greedy Algorithm, Simulated Annealing, Exhaustive Search, Travelling Salesman Problem, Combinatorial Optimization
Identifikatorer
URN: urn:nbn:se:du-4530OAI: oai:dalea.du.se:4530DiVA, id: diva2:518793
Uppsök
Technology
Veileder
Tilgjengelig fra: 2010-02-11 Laget: 2010-02-11 Sist oppdatert: 2025-10-09bibliografisk kontrollert

Open Access i DiVA

fulltekst(646 kB)1024 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 646 kBChecksum SHA-512
f16e4a3b1b1b001ca1415c5c2b04d2868e47c93eba35f52bd0e96ad3d930d363fc9f0985fad6bf54fa1dcfd7dbcc72e8fada670328970c9973d2545a6689af95
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 1026 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 1171 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf