Clever Geek Handbook

Distribution / Availability Algorithm

I am wondering if anyone knows of an Algorithm that I could use to help me solve the following problem:

Allocate people (n) to certain events (m), m can only have one person and it must be randomized every time (same person is allowed if only one option (n) is available). n has properties such as available time and available day. For n to match m, available time and available day must match both n and m. There may be a multiple of n that matches the times of m, but it should be the best fit so the rest of m can be allocated. The diagram below will most likely explain this better (sorry). n can be allocated more than one m, but must be satisfied enough so that one n does not have all available m enter image description here

As you can see, Person A can be bound to event A, but due to the need to have all of them matched (best attempt at matching), it is bound to event B to allow Person C to be allocated to event A and person B to event C.

I'm just wondering if anyone knows the name of this type of problem and how I can solve it, I am coding a program in Java

+3


source to share


3 answers


This is a variant of the Max Flow Problem . There are many algorithms designed to solve maximum flow problems, including the Ford-Fulkerson Algorithm or its refinement, the Edmonds-Karp Algorithm . Once you are able to change your problem into a maximum flow problem, the solution is quite simple. But what is the maximum flow problem?

The problem takes a weighted directed graph and asks the question "What is the maximum amount of flow that can be directed from a source (a node) to a sink (another node)?". There are several limitations that make logical sense when we think of a graph as a network of water flows.

  • The amount of flow through each edge must be less than or equal to the "capacity" (weight) of that edge for each edge on the graph. They must also be non-negative numbers.
  • The volume of the stream in each node must equal the volume of the stream, leaving that node forever node, excluding the source and destination. There is no limit on the amount of thread passing through a node.

Consider the following graph: s

as a source and t

as a destination.

enter image description here

A solution to the maximum flow problem would be a total flow of 25, with the following flow rates:

enter image description here

Just turn your problem into a max flow problem. Assuming your inputs are:



  • N

    people, and related information about when a person p_i

    is available time and date.
  • M

    events with time and place.

Create a graph with the following properties:

  • Super source s

  • N

    custom nodes p_1 ... p_n

    with container edge infinity

    connecting s

    to p_i

    for everyone i in 1 ... n

    .
  • Super sink t

  • M

    event nodes e_1 ... e_m

    with tank edge 1

    connecting e_i

    to t

    for alli in 1 ... m

  • For each combination of person and event, an (p_i, e_j)

    edge with capacity infinity

    connecting p_i

    to e_j

    iff p

    can successfully attend the event e

    (otherwise there is no edge binding p_i

    and e_j

    ).

Plotting these specifications has O(1) + O(N) + O(N) + O(M) + O(M) + O(1) + O(NM) = O(NM)

a runtime.

For your example, the plotted graph would look like this (with unlabeled edges with unlimited bandwidth):

enter image description here

You correctly noticed that there is Max for this example. stream with a value 4

, and any max stream will return the same value. Once you can do this conversion, you can run any maximum flow algorithm and solve your problem.

+1


source


Create an AllocatePerson class that has Person and an event list as an lsInnerEvents attribute (you must first define the Person class and Events class as with the Time and Day list).

In the AllocatePerson constructor, you write Person and a list of events, the constructor will loop over the events and add only the one that matches the Person parameter to the internal list.

The main code will create an AllocatePerson for each Person (1 at a time) implementing the following logic:



if the new "objAllocatePerson" object has a list of lsInnerEvents with size = 1, you remove the element contained in lsInnerEvents from the list of events to be allocated and run a procedure called MaintainEvents (Events deletedEvents), which dispatches the selected event (one inside lsInnerEvents).

The MaintainEvents function will loop through the current AllocatePersons array and remove "deletedEvents" from its lsInnerEvents, if after that the size of lsInnerEvents is = 1, it will recursively call MaintainEvents () with new removed events and remove new lsInnerEvents from the main event list for placement.

At the end of execution, you will have the entire association simply by looping through the AllocatePersons array, where the lsInnerEvents size is 1

0


source


The approach you might consider is as follows:

  • Create Java objects for Face and Event .
  • Put all Events in a pool (Java build)
  • For each Person, select an Event from the pool. Since each person can only select events on certain days, create an Event subset to be in the selection pool from Face .

Add the required attributes to Events to make sure it can only be selected once by the Person

0


source






More articles:


All Articles