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
Implementation and testing of an FPT-algorithm for computing the h+ heuristic
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems.
2017 (English)Independent thesis Basic level (degree of Bachelor), 10,5 credits / 16 HE creditsStudent thesisAlternative title
Implementering och testning av en FPT-algoritm för beräkning av h+-heuristiken (Swedish)
Abstract [en]

We have implemented and benchmarked an FPT-algorithm, that has two input parameters, k and w besides the input problem instance, which is a planing instance, in this thesis. The algorithm has an exponential running time as a function of these two parameters. The implemented algorithm computes the heuristic value h^+(s) of a state s that belongs to a state space, which originates from a strips instance. The purpose of the project was to test if the algorithm can be used to compute the heuristic function h^+, i.e. the delete-relaxation heuristic, in practice. The delete-relaxation heuristic value for some state is the length of the optimal solution from the state to a goal in the delete-relaxed-instance, which is the original instance without all its negative effects. Planning instances was benchmarked with the search algorithm A^* to test the algorithms practical value. The heuristic function blind was benchmarked together with A^* with the same instances so that we could compare the quality of the benchmark result for the implemented algorithm. The conclusion of the project was that the implemented algorithm is too slow to be used in practise.

Place, publisher, year, edition, pages
2017. , p. 39
Keywords [en]
FPT, hplus, heuristic
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-142050ISRN: LIU-IDA/LITH-EX-G–17/077–SEOAI: oai:DiVA.org:liu-142050DiVA, id: diva2:1151572
Subject / course
Computer science
Supervisors
Examiners
Available from: 2017-10-24 Created: 2017-10-23 Last updated: 2017-10-24Bibliographically approved

Open Access in DiVA

fulltext(428 kB)39 downloads
File information
File name FULLTEXT01.pdfFile size 428 kBChecksum SHA-512
cbe63cd95f669609a0a9689de4d8a3ded9c56d753a1c5b3a41c3c4269b466088ce8111dfe1e4e67a6ae1cdc7c29b277b3e08553a16ac3476491e7f902eca8fb3
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Jonsson, Niclas
By organisation
Artificial Intelligence and Integrated Computer Systems
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 39 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

urn-nbn

Altmetric score

urn-nbn
Total: 157 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