1

So I am looking to solve the problem stated below and I am having problems and what to actually look for as I can not describe the problem in simple terms. I am hoping someone may be able to shed some light on the correct Algorithm or path I should take to solve it.

The problem(simplified):

so lets say I have a multiple people objects.

Person1
Person2
Person3

Now lets say I have 6 slots

Slot1
Slot2
Slot3
Slot4
Slot5
Slot6

Each person has rules associated with them such as

  • Person1 can not use a slot with an odd number and must be in 3 different slots.
  • Person2 Can only go into slots from 2 up and must be in 2 slots
  • Person3 can only go into 1 prime number slot.

so we end up with 

 Slot1 - Person3
 Slot2 - Person1
 Slot3 - Person2
 Slot4 - Person1
 Slot5 - Person2
 Slot6 - Person1

I know this will require use of A.I/Machine learning and I have done some research into the area but I cannot find what algorithm I should be using for a problem like or even how to search for this. The only way I have found of doing this in some way is through as regression tree but it seems to me like that way seems like the wrong path to take.

Note: I will be using c# to solve this problem and hopefully some framework like Encog.

Improve this question
2
  • The problem you're trying to solve belongs to a wide family of problems named Constraint Satisfaction Problems (CSP). Please see: en.wikipedia.org/wiki/Constraint_satisfaction_problem Commented Sep 20, 2016 at 22:24
  • Thanks for the information sorry for the wide berth of the question but I was trying to keep the example simple as I just needed the area to look into as I have to research it for a final year project proposal Commented Sep 20, 2016 at 22:30

3 Answers 3

Reset to default
2

Actually I think you can solve this problem with Maximum Matching with a simple modification. In the standard Maximum Matching each node is only matched with one other node but here a Person can have multiple matches. By creating multiple instances of Person you can reduce this problem to Maximum Matching. For example:

Person1 cannot use a slot with an odd number and must be in 3 different slots.

Create 3 nodes for Person1 and connect them to even number slots.

Person 2 Can only go into slots from 2 up and must be in 2 slots

Create 2 nodes of Person2 and connect them to slots with number bigger than 2.

Person 3 can only go into 1 prime number slot.

Create 1 node for Person3 and connect it to slot1, slot2, slot3, and slot5.

Perform Maximum Matching on the resulted graph and you will find the answer.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Actually this problem is standard discrete optimization problem. You may want to look at coursera discrete optimization course. In its first week, it has a workshop named Simple Puzzles. It gives a similar problem to yours and shows how to solve it in their platform mini-zinc.

After you understand how this type of problems solved, you may want to look a c# solution from List of optimization software.

Improve this answer

4 Comments

It's helpful to name the problem, but it's not technically an answer to the question.
That is true but question is very general.
It's annoying to find I'd need to enrol in a Melbourne Uni course to see more... you need to summarise external links, otherwise like @SamDufel said all you've done is name the problem. Please share a solution.
Thanks for your answer and if the course does enable me to answer this ill make sure to return and accept.
0

The pairing between Person and Slot is a scheduling problem which requires knowledge to solve it. The knowledge is described in rules like "Person1 can not use a slot with an odd number and must be in 3 different slots." The algorithm to solve the problem uses the rules and the given ressources (three persons and six slots) to generate all possible solutions. Computerscience has the task to formalize the knowledge into machine readable code. There are many programming languages out there e.g. PDDL, Prolog or object-oriented languages. In classical "AI Planning and scheduling" which is discussed at the ICAPS Conference the PDDL language would be the prefered choice for modelling the knowledge. The algorithm itself to solve a given domain is in most cases backtracking, monte-carlo-tree-search or simply brute-force. That is called "problem solving as search".

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.