Pot, Derk Jan (2022) Analysing Redundant Exploration of Parallel Search Algorithms. Bachelor's Thesis, Computing Science.
|
Text
bCS_2022_PotDJ.pdf Download (929kB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
toestemming.pdf Restricted to Registered users only Download (121kB) |
Abstract
Using parallel search to solve CSPs may perform extra work compared to sequential search. Using sequential search algorithms, we can effectively prune nodes from the search space of an CSP before they are explored. With parallel search we may get assigned parts of the search space which would normally not be considered, and we cannot prune redundant nodes as easily without getting communication overhead between different threads. On the other hand, we may get to a solution much quicker, hereby exploring fewer nodes in total of the search space. We analyse several constraint satisfaction and constraint optimisation problems from the MiniZinc challenge 2021, using the Gecode solver, and analyse how many nodes are explored with a different number of threads. The results are unexpected at times, making it hard to draw concrete conclusions.
| Item Type: | Thesis (Bachelor's Thesis) |
|---|---|
| Supervisor name: | Degeler, V. and Medema, M. |
| Degree programme: | Computing Science |
| Thesis type: | Bachelor's Thesis |
| Language: | English |
| Date Deposited: | 08 Jul 2022 13:53 |
| Last Modified: | 08 Jul 2022 13:53 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/27674 |
Actions (login required)
 |
View Item |