Two Sub-Optimal Algorithms for an NP-Hard Dance Choreography Problem Comparison of Genetic and Greedy Process Implementations

Abstract

We apply the concepts behind Genetic and Greedy Algorithms to solve the dance choreography problem. Both these algorithms use novel adaptations to maximize the probability of yielding optimal solutions to this problem. The performances of both these implementations are compared for solution quality and time complexity. Thus, timings, average ratings, and standard deviation of results are measured with respect to amalgamation length and figures selected. Results indicate the feasibility, and limitations, of these two sub-optimal algorithms in this domain.