Best fit algorithm

Question

I am writing a planning program with a difficult programming problem. There are several events, each of which has several meetings. I need to find an agreement on the time of the meeting, so that each schedule contains any given event exactly once, using one of several events at a time.

Obviously, I could use brute force, but this is rarely the best solution. I guess this is a relatively basic computer science problem that I will learn about as soon as I can start computer science classes. In the meantime, I would prefer any links where I could read this, or even just a name that I could use Google.

Answer 1

I think you should use a genetic algorithm because:

• It is best suited for large instances of problems.
• This gives reduced time complexity at the price of an inaccurate answer (not the best)
• You can easily identify restrictions and preferences by adjusting fitness penalties for non-working people.
• You can specify time limits for program execution.

• The quality of the decision depends on how much time you intend to spend on the decision of the program.

  Definition of genetic algorithms

  Genetic Algorithm Tutorial

  Class Planning Project with GA

Answer 2

There are several ways to do this.

One approach is programming constraints. This is a special case of dynamic programming offered by feanor. It will be useful to use a specialized library that can perform restriction and branching for you. (Google for "gecode" or "comet-online" to search for libraries)

If you are mathematically inclined, you can also use integer programming to solve the problem. The main idea here is to translate your problem into a set of linear inequalities. (Google for “integer programming planning” to find many real-life examples and google for “Abacus COIN-OR” for a useful library)

My assumption is that constraint programming is the easiest approach, but integer programming is useful if you want to include real variables in your problem at some point.

Answer 3

Your description of the problem is not entirely clear, but if all you are trying to do is find a schedule that does not have overlapping events, then this is a simple two-way matching problem .

You have two sets of nodes: events and time. Draw an edge from each event to every possible meeting time. Then you can efficiently build the mapping (the greatest possible set of edges between nodes) using extended paths . This works because you can always convert a bipartite graph into an equivalent stream.

Sample code that does this is BIM . Standard graphics libraries such as GOBLIN and NetworkX also have bipartisan matches.

Answer 4

It seems like this could be a good candidate for a dynamic programming solution, in particular something similar to the interval planning task .

There are some visual effects here for the specific task of interval planning, which can make the concept understandable. Here is a good tutorial on dynamic programming in general.