<< Chapter < Page | Chapter >> Page > |
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:
Notification Switch
Would you like to follow the 'Data structures and algorithms' conversation and receive update notifications?