Stable roommates problem
The stable roommates problem is like when you and your friends want to live together in a house, but you need to decide who will share rooms with whom. The problem is to find a way to divide the rooms among you all so that everyone is happy and no one wants to switch rooms.
Imagine you have four friends, named A, B, C, and D. They are looking for a 2-bedroom apartment to live in. The apartment has two bedrooms, each the same size. But everyone has a preference for whom they want to share a room with. A wants to share with B, B with A, C with D, and D with C.
One way to solve this problem is that A and B get one room and C and D get the other. And everyone is happy with their roommate. This is a stable solution because no one wants to switch rooms. But it's not the only solution.
Another way to divide the rooms is that A and C share one room, and B and D share the other. But this is not a stable solution because A may wish to switch and share the room with B instead, and B also complies to do so. In this case, C may also want to switch to share the room with D instead. As you can see, this can create a lot of confusion and arguments, which is not fun.
So, the stable roommates problem is about finding a way to divide a set of people into pairs so that everyone is happy with their roommate and no one wants to switch. It's a challenging problem that requires complex algorithms to find the best solution.
Imagine you have four friends, named A, B, C, and D. They are looking for a 2-bedroom apartment to live in. The apartment has two bedrooms, each the same size. But everyone has a preference for whom they want to share a room with. A wants to share with B, B with A, C with D, and D with C.
One way to solve this problem is that A and B get one room and C and D get the other. And everyone is happy with their roommate. This is a stable solution because no one wants to switch rooms. But it's not the only solution.
Another way to divide the rooms is that A and C share one room, and B and D share the other. But this is not a stable solution because A may wish to switch and share the room with B instead, and B also complies to do so. In this case, C may also want to switch to share the room with D instead. As you can see, this can create a lot of confusion and arguments, which is not fun.
So, the stable roommates problem is about finding a way to divide a set of people into pairs so that everyone is happy with their roommate and no one wants to switch. It's a challenging problem that requires complex algorithms to find the best solution.