Interpretation of Backtracking Algorithm Problem - weighted matching

Question

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 ...?

Answer 1

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)$.