Spacecraft Design

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

A certain spacecraft requires n functions, each of which can be provided by various parts. For example, perhaps parts p11, p12, p13 may all individually accomplish function f1. No part can serve multiple functions however. Each part has a certain weight.

The parts for the various functions are not independent of one another. For example, it may be that part p11 can work with p22 or p23 but not with p24.

Your job is to create a design which accomplishes all functions, satisfies the contraints, and uses minimum weight. Please use a genetic algorithm.

You will be giving two tables
Part(id, function, weight) -- a part has a unique id, can support exactly one function, and has a weight.
Constraint(function1, function2, id1, id2) -- an acceptable combination of ids for function1 and function2 is id1 and id2 respectively.

So, an acceptable "design" is a set of part ids having the following properties

The architecture group will provide a verifier.