Assignment problems

Write recursive code to implement the N-Queen problem by using depth-first search. Make your code general enough to handle any arbitrary N. For testing purposes you might want to try N = 4, which is the smallest non-trivial problem.

Now use N = 8. Print out all the possible solutions. How many are there?

Modify your code to stop as soon as one solution is found. Run with N = 9, 10, 11, etc...

Write code to implement the N-Queen problem by using greedy search. Make your code general enough to handle any arbitrary N. The code should terminate as soon as one solution is found.

For testing purposes you might want to try N = 4, which is the smallest non-trivial problem. Run with ever increasing N.

(From Wikipedia, the free encyclopedia)

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized.

If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the Linear assignment problem. Commonly, when speaking of the Assignment problem without any additional qualification, then the Linear assignment problem is meant.

Formal mathematical definition

The formal definition of the assignment problem (or linear assignment problem) is

Given two sets, A and T, of equal size, together with a weight function C : A × T → R. Find a bijection f : A → T such that the cost function:

is minimized.

Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:

The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

The problem can be expressed as a standard linear program with the objective function

subject to the constraints

for ,

for ,

for .

The variable xij represents the assignment of agent i to task j, taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is totally unimodular. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent

Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.

(From Wikipedia, the free encyclopedia)

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

The Gale-Shapley algorithm involves a number of "rounds" (or "iterations") where each unengaged man "proposes" to the most-preferred woman to whom he has not yet proposed, and she accepts or rejects him based on whether she is already engaged to someone she prefers. If she is unengaged, or engaged to a man lower down her preference list than her new suitor, she accepts the proposal (and in the latter case, the other man becomes unengaged again). Note that only women can switch partners to increase their happiness.

Algorithm

function stableMatching {

Initialize all m M and w W to free

while free man m who still has a woman w to propose to {

w = m's highest ranked such woman

if w is free

(m, w) become engaged

else some pair (m', w) already exists

if w prefers m to m'

(m, w) become engaged

m' becomes free

else

(m', w) remain engaged

}

}

Using this algorithm to guarantee that:

• Everyone gets married: Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have to have said yes.

• The marriages are stable: Let Alice be a woman and Bob be a man. They are each paired/partnered/married, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.