3
$\begingroup$

I have read about the N-queens problem and I don't understand the following objective function:

$O(board)=N^2/2-L$

$N$ ... number of queens $L$ ... number of pairs of queens that attack each other

Why they use $N^2/2$? They wrote that it is the number of pairs of queens but I don't understand that can someone maybe explain it to me maybe with visualization

$\endgroup$
1
$\begingroup$

The objective function you describe satisfies two properties:

  1. It is maximized at a solution.
  2. It is non-negative.

One can think of many other functions satisfying these two properties, for example $\binom{N}{2} - L + C$ for every $C \geq 0$. The exact choice is not so important – indeed, they chose $N^2/2$ whereas they could have chosen $\binom{N}{2} = N(N-1)/2$.

$\endgroup$
4
  • $\begingroup$ So it would also be possible to use $O(board)=L$ and minimize the function? and what is the advantage of using such objective functions $O(board)=(N2)−L+C$, $O(board)=N2/2−L$ instead of my example? - maybe it is a stupid question $\endgroup$ Aug 29 '16 at 14:48
  • 1
    $\begingroup$ I have no idea on what algorithm you are using, but generally speaking, you could minimize $L$, or $L^2$, or $e^L$, or maximize $1/L$; these objectives are all equivalent. A given algorithm might make use of the actual value of the objective function, and then which function you use could make a difference. $\endgroup$ Aug 29 '16 at 14:49
  • $\begingroup$ A sorry I totally forgot to say that the paper I read uses the Hill Climbing algorithm $\endgroup$ Aug 29 '16 at 14:51
  • $\begingroup$ I answered your question as stated. If you have any further questions, please ask another one, and provide all details that seem relevant. In particular, hill climbing is a meta-algorithm with many possible implementations. $\endgroup$ Aug 29 '16 at 14:52

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.