Back to search

Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science

Applying deep convolutional neural networks to the dragon boat partition problem

Abstract

dc:description.abstract

We investigate approximating the Dragon Boat Partition problem, a practical real-worldvariant of the Partition problem. A team of dragon boat participants must be partitionedwith an approximately balanced arrangement with a preferable weight difference of 0. Wepresent two approaches that capture the participant characteristics. The first approach takesa heuristic route. The second approach applies Deep Convolutional Neural Networks to theproblem, with two versions. In our 10,000 episodes per experiment, our heuristic imple-mentation had an average episode runtime of 1.84ms, an average of 7.39 steps per episode,perfect left-right approximation rate of 98.53%, perfect front-back approximation rate of89.16%, and a perfect combined approximation rate of 90.15%. Whereas our best deeplearning model has an average episode runtime of 1.23ms, an average of 4.65 steps perepisode, perfect left-right approximate rate of 98.00%, perfect front-back approximationrate of 95.13%, and a perfect combined approximation rate of 94.28%.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Regnier, Brett
  • University of Lethbridge. Faculty of Arts and Science
Advisor dc:contributor.supervisor
  • Zhang, John Z.

Subjects

dc:subject × 13

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/6029

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Regnier, Brett; University of Lethbridge. Faculty of Arts and Science. Applying deep convolutional neural networks to the dragon boat partition problem. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2021. https://hdl.handle.net/10133/6029