Difference between revisions of "Help:Trolls on wheels!"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
m (Trampin' all the way moved page TADM2E 1.6 to Help:Trolls on wheels!)
 
(7 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
One counter-example consists of a series of subsets that increase in size exponentially, plus 2 additional subsets that each cover half of the elements. Example:
+
Counter-example 1:
  
−
<math>S_1 = \{1, 2\}</math>
+
<math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math>
 
<br/>
 
<br/>
−
<math>S_2 = \{3, 4, 5, 6\}</math>
+
<math>S_1 = \{1, 2, 4, 6, 8, 10, 12, 14\}</math>
 
<br/>
 
<br/>
−
<math>S_3 = \{7, 8, 9, 10, 11, 12, 13, 14, 15, 16 \}</math>
+
<math>S_2 = \{3, 5, 9, 11\}</math>
 
<br/>
 
<br/>
−
<math>S_4 = \{1, 2, 3, 4, 5, 6, 7, 8 \}</math>
+
<math>S_3 = \{7, 13\}</math>
 
<br/>
 
<br/>
−
<math>S_5 = \{9, 10, 11, 12, 13, 14, 15, 16 \}</math>
+
<math>S_4 = \{1, 2, 3, 4, 5, 6, 7\}</math>
 +
<br/>
 +
<math>S_5 = \{8, 9, 10, 11, 12, 13, 14\}</math>
 +
 
 +
There is an optimal solution: <math>S_4, S_5</math> (2 subsets).
 +
<br/>
 +
A greedy algorithm will choose <math>S_1, S_2, S_3</math> (3 subsets):
 +
<br/>
 +
1. <math>S_1</math> since it contains 8 uncovered elements (more than any other subset)
 +
<br/>
 +
2. <math>S_2</math> since it then contains 4 uncovered elements (more than any other subset)
 +
<br/>
 +
3. <math>S_3</math> since it then contains 2 uncovered elements (more than any other subset)
 +
 
 +
 
 +
Counter-example 2:
 +
 
 +
<math>U = \{1, 2, 3, 4, 5\}</math>
 +
<br/>
 +
<math>S_1 = \{1, 2, 3\}</math>
 +
<br/>
 +
<math>S_2 = \{1, 2, 4\}</math>
 +
<br/>
 +
<math>S_3 = \{4, 5\}</math>
 +
 
 +
There is an optimal solution <math>S_1, S_3</math>.
 +
<br/>
 +
But the greedy algorithm might choose <math>S_2, S_3, S_1</math>.
 +
 
 +
Counter-example 3:
  
−
The greedy algorithm will choose <math>S_3, S_2, S_1</math>, while the optimal solution is simply <math>S_4, S_5</math>
+
<math>U = \{1, 2, 3, 4, 5, 6\}</math>
 +
<br/>
 +
<math>S_1 = \{2, 3, 4, 5\}</math>
 +
<br/>
 +
<math>S_2 = \{1, 2, 3\}</math>
 +
<br/>
 +
<math>S_3 = \{4, 5, 6\}</math>
 +
 
 +
There is an optimal solution: <math>S_2, S_3</math> (2 subsets).
 +
<br/>
 +
A greedy algorithm will choose <math>S_1, S_2, S_3</math> (3 subsets)

Latest revision as of 07:31, 15 April 2019

Counter-example 1:

$ U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\} $
$ S_1 = \{1, 2, 4, 6, 8, 10, 12, 14\} $
$ S_2 = \{3, 5, 9, 11\} $
$ S_3 = \{7, 13\} $
$ S_4 = \{1, 2, 3, 4, 5, 6, 7\} $
$ S_5 = \{8, 9, 10, 11, 12, 13, 14\} $

There is an optimal solution: $ S_4, S_5 $ (2 subsets).
A greedy algorithm will choose $ S_1, S_2, S_3 $ (3 subsets):
1. $ S_1 $ since it contains 8 uncovered elements (more than any other subset)
2. $ S_2 $ since it then contains 4 uncovered elements (more than any other subset)
3. $ S_3 $ since it then contains 2 uncovered elements (more than any other subset)


Counter-example 2:

$ U = \{1, 2, 3, 4, 5\} $
$ S_1 = \{1, 2, 3\} $
$ S_2 = \{1, 2, 4\} $
$ S_3 = \{4, 5\} $

There is an optimal solution $ S_1, S_3 $.
But the greedy algorithm might choose $ S_2, S_3, S_1 $.

Counter-example 3:

$ U = \{1, 2, 3, 4, 5, 6\} $
$ S_1 = \{2, 3, 4, 5\} $
$ S_2 = \{1, 2, 3\} $
$ S_3 = \{4, 5, 6\} $

There is an optimal solution: $ S_2, S_3 $ (2 subsets).
A greedy algorithm will choose $ S_1, S_2, S_3 $ (3 subsets)

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=Help:Trolls_on_wheels!&oldid=622"