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?

Improve this question
$\endgroup$
4
  • $\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, 2015 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, 2015 at 14:06
  • $\begingroup$ btw is this a MDS or set packing problem? $\endgroup$
    – RandomStudent
    Jan 5, 2015 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, 2015 at 0:37

2 Answers 2

Reset to default
2
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ that's genius, how do you determine whether if you want to discard the changes though? $\endgroup$
    – RandomStudent
    Jan 3, 2015 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, 2015 at 10:56
  • 1
    $\begingroup$ I tested it, it actually works, thank you HenryHey! $\endgroup$
    – RandomStudent
    Jan 6, 2015 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, 2015 at 0:39
3
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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