his.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Tillämpbarheten av Learning Backtracking Search Optimization Algoritmen vid Lösning av Sudoku-problemet
University of Skövde, School of Informatics.
2017 (Swedish)Independent thesis Basic level (degree of Bachelor), 20 credits / 30 HE creditsStudent thesisAlternative title
The Application of the Learning Backtracking Search Optimization Algorithm when Applied to the Sudoku Problem (English)
Abstract [sv]

Den här rapporten undersöker egenskaper hos en algoritm som är baserad på Learning Backtracking Search Optimization Algorithm (LBSA) som introducerades av Chen et. al. (2017). Undersökningen genomfördes genom att tillämpa algoritmen på Sudokuproblemet och jämföra lösningsgraden och diversiteten i den sista populationen med en algoritm som är baserad på Hybrid Genetic Algorithm (HGA) som introducerades av Deng och Li (2011). Resultaten visar att implementationen av den LBSA-baserade algoritmen har en lägre lösningsgrad än den HGA-baserade algoritmen för alla genomförda experiment, men att algoritmen håller en högre diversitet i den sista populationen för tre av de fem gjorda experimenten. Slutsatsen är att den LBSA-baserade algoritmen inte är lämplig för att lösa Sudokuproblemet på grund av en låg lösningsgrad och att implementationen har en hög komplexitet.

Abstract [en]

This report examines the properties of an algorithm based on the Learning Backtracking Optimization Algorithm (LBSA) introduced by Chen et. al. (2017). The examination was performed by applying the algorithm on the Sudoku problem and then comparing the solution rate and the diversity in the final population with an algorithm based on the Hybrid Genetic Algorithm introduced by Deng and Li (2011). The results show the implementation of the LBSA based algorithm have a lower solution rate than the HGA based algorithm for all executed experiments. But the LBSA based algorithm manage to keep a higher diversity in the final population in three of the five performed experiments. The conclusion is that the LBSA based algorithm is not suitable for solving the Sudoku problem since the algorithm has a lower solution rate and the implementation have a high complexity.

Place, publisher, year, edition, pages
2017. , 39 p.
Keyword [en]
Evolutionary Algorithm, Sudoku, Optimization Problems
Keyword [sv]
Evolutionär Algoritm, Sudoku, Optimeringsproblem
National Category
Computer Science
Identifiers
URN: urn:nbn:se:his:diva-14087OAI: oai:DiVA.org:his-14087DiVA: diva2:1138465
Subject / course
Informationsteknologi
Educational program
Computer Science - Specialization in Systems Development
Supervisors
Examiners
Available from: 2017-09-06 Created: 2017-09-05 Last updated: 2017-09-06Bibliographically approved

Open Access in DiVA

fulltext(660 kB)11 downloads
File information
File name FULLTEXT01.pdfFile size 660 kBChecksum SHA-512
fcf8c5869c4f40f69e5081153f7d12304dfd3f87712dfaccd6d550a673de77f123110c194e56f1897eba610a8089e7dbae2985b74ec2c108a66cd0ba57e26f61
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Sävhammar, Simon
By organisation
School of Informatics
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 11 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf