0
$\begingroup$

I am attempting to resolve the following problem using Backtracking:

Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P_{ij}$ is the preference of the man $i$ for the woman $j$ and $Q_{ij}$ is the preference of the woman $i$ for the man $j$.

  1. Depict an algorithm that follows the Backtracking technique to find the pairs of men and women whose sum of the products of the preferences are the highest possible.

  2. With help from the matrices $P = \begin{bmatrix} 1 & 3 & 2 & 0 \\ 2 & 4 & 3 & 1 \\ 0 & 3 & 1 & 2 \\ 3 & 4 & 2 & 1 \\ \end{bmatrix} $ and $Q = \begin{bmatrix} 0 & 1 & 2 & 3 \\ 4 & 3 & 2 & 1 \\ 4 & 2 & 3 & 1 \\ 3 & 1 & 4 & 2 \\ \end{bmatrix} $ and represent the exploration tree of the exploration of the search space of the solution. Indicate:

    • How will you represent the solution and based on that, what are the restrictions of the problem and how will you calculate the value of the objective function.

    • In the process of ramification, what will represent the levels and how will you generate the children of each node.

  3. Analyze the time complexity of the algorithm.

I have the basic ideas of how backtracking works but I am having trouble interpreting the problem. What does it mean by ... the sum of the products of the preferences ...?

$\endgroup$
1
$\begingroup$

Suppose man $i$ is paired with woman $w(i)$, for $1\le i\le n$.

"The sum of the products of the preferences" is the following number.

$$ P_{1,w(1)}Q_{w(1), 1} + P_{2,w(2)}Q_{w(2), 2} + \cdots + P_{n,w(n)}Q_{w(n), n} $$

One can imagine that each individual product $P_{i,w(i)}Q_{w(i),i}$ quantifies how preferred is the pairing between man $i$ and woman $w(i)$.

$\endgroup$
  • $\begingroup$ And do you think you can assist me with a possible solution for this using backtracking? I have no idea how to proceed. $\endgroup$ – Omari Celestine Nov 1 '18 at 11:51
  • $\begingroup$ This problem looks like quite some undertaking, although it is not that hard in each step. If you have no idea how to proceed, you will need some substantial interactive time with someone such as your instructor, your TA or some knowledgeable friend of yours. $\endgroup$ – Apass.Jack Nov 1 '18 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.