1
$\begingroup$

We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$. All the circles have radius of $k$.

I want to find a subset of circles such that no circles in this subset intersect with each other, such that this subset is as large as possible.

I'm asked to find a way to solve this using a backtracking algorithm. Rather than to do it with brute force, is there a effective way to prune some of the branches?

$\endgroup$
  • $\begingroup$ 1. What have you tried? Where did you get stuck? We expect you to make a significant effort on your own before asking, and to show us in the question what you tried and where you got stuck. This is not a site where you can copy-paste your exercise problem and have us solve it for you. 2. What is the motivation for solving this with backtracking, as opposed to some other method? If this is an exercise from a class to help you practice backtracking, then asking us to solve the exercise for you won't help you learn -- you learn by struggling with these problems on your own. $\endgroup$ – D.W. Jan 5 '15 at 1:27
  • $\begingroup$ wow, thank you for editing! now i start to make sense out of it, I am sorry i am new to this community, although this is not for school, I guess you are right about the fact that I should think more before asking, thank you for your comment! and I will be very careful next time. $\endgroup$ – RandomStudent Jan 5 '15 at 14:06
  • $\begingroup$ btw is this a MDS or set packing problem? $\endgroup$ – RandomStudent Jan 5 '15 at 14:39
  • 1
    $\begingroup$ Thank you for editing @HenryHey, you are right I should have give my algorithm in the first place. It would be better. And thank you for your help, I successfully made this task. $\endgroup$ – RandomStudent Jan 12 '15 at 0:37
1
$\begingroup$

The way I can figure out of is using 3 invariant, 1 stores selected cycles, 1 stores unselected cycles, 1 with unchecked cycles, once you add a disk $n$ from unchecked to selected, you also add the disks overlap with $n$ into the unselected and remove them from checked list, that is a way to do pruning.

$\endgroup$
  • $\begingroup$ that's genius, how do you determine whether if you want to discard the changes though? $\endgroup$ – RandomStudent Jan 3 '15 at 15:19
  • 1
    $\begingroup$ I personally would prefer to check the list that stores the unchecked cycles, basically for each turn you wants the size of that list as small as possible, and return the one with smallest size. And I do agree with D.W. as he mentioned the linear programming is way better, his answer is pretty cool and he also edited the problem description in a better way, so if you wanna pick him, it is fine. Welcome to the computer science community. $\endgroup$ – HenryHey Jan 6 '15 at 10:56
  • 1
    $\begingroup$ I tested it, it actually works, thank you HenryHey! $\endgroup$ – RandomStudent Jan 6 '15 at 11:53
  • $\begingroup$ You are welcome, I am new here as well, hope we can help each other more often. $\endgroup$ – HenryHey Jan 12 '15 at 0:39
2
$\begingroup$

If it were me, I would encode this as an instance of ILP (integer linear programming) and let an off-the-shelf ILP solver deal with the backtracking and pruning.

Introduce $n$ variables $x_1,\dots,x_n$, where $x_i=1$ means that you include the $i$th circle in the subset and $x_i=0$ means you don't include it. Add the following constraints:

  • $0 \le x_i \le 1$, for each $i$: this forces each $x_i$ to be either 0 or 1.

  • $x_i + x_j \le 1$, for each pair $i,j$ of circles that intersect each other: this enforces that you cannot choose two overlapping circles.

Now maximize the value of $x_1+x_2+\dots+x_n$ (this is the objective function). Ask an ILP solver to find the optimal solution for you. Internally, the ILP solver will likely use backtracking, pruning, branch-and-bound, and other sophisticated methods.

This will be a very efficient use of your time: rather than trying to program up each of those methods and debug your implementation, you can rely upon an existing well-tested ILP solver. Also, given the amount of effort that has gone into optimizing ILP solvers, this approach might well perform better than any backtracking algorithm you're likely to come up with.

$\endgroup$
  • $\begingroup$ Wow, yes, I see, I just read about integer linear programming, thank you for your effort! This problem does look like a typical linear programming problem. now i am struggling, you helped me more than HenryHey did (sorry), but his answer also make sense. so i do not know which one should be the correct answer. XD $\endgroup$ – RandomStudent Jan 6 '15 at 10:47
  • $\begingroup$ thank you very much, you are truly a wonderful person. I picked HenryHey's answer because it works. But for anyone who is reading this post please follow @D.W. his answer should be the better way to solve this problem. $\endgroup$ – RandomStudent Jan 11 '15 at 22:19

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.