|
Size: 1453
Comment: Connected Maximum-density Still Life added
|
← Revision 9 as of 2013-03-18 10:32:46 ⇥
Size: 2812
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| #acl EditorsGroup:read,write,admin,delete ChristianDrescher:read,write All:read |
|
| Line 3: | Line 5: |
| <<TableOfContents>> | |
| Line 14: | Line 15: |
| grid with a maximally dense still life, i.e., a maximum number of live cells. | given region of the grid with a maximally dense still life, i.e., a maximum number of live cells. |
| Line 16: | Line 17: |
| criterion is dropped.) We here consider square shaped grids. The size n of the grid is provided by an instance of the predicate size/1. Cells connect horizontally, vertically, and diagonally. |
criterion is dropped.) |
| Line 20: | Line 19: |
| If a still life exists, a witness containing live cells encoded in the predicate lives/2 has to be provided. lives(X,Y) means the grid cell with the unsigned integer coordinates X,Y (=< n) is a live cell. |
|
| Line 32: | Line 28: |
| We here consider square shaped regions. The size n of the region is provided by an instance of the predicate {{{size/1}}}. Cells connect horizontally, vertically, and diagonally. |
|
| Line 35: | Line 35: |
| If a still life exists, a witness containing live cells encoded in the predicate {{{lives/2}}} has to be provided. {{{lives(X,Y)}}} means the grid cell with the unsigned integer coordinates X,Y (=< n) is a live cell. == Cost function == The cost function is given as the number of ''non-living'' cells. This value has to be minimized (consequently maximizing the number of living cells). |
|
| Line 38: | Line 45: |
| The first example encodes the region size three by {{{size(3)}}}. The maximum density of a connected still life on a region with size three is six live cells. Thus, a sample output is: {{{ lives(1,2). lives(1,3). lives(2,1). lives(2,3). lives(3,1). lives(3,2). }}} The second example encodes the region size four by {{{size(4)}}}. The maximum density of a connected still life on a region with size four is eight live cells. Thus, a sample output is: {{{ lives(1,3). lives(1,4). lives(2,2). lives(2,4). lives(3,1). lives(3,3). lives(4,1). lives(4,2). }}} On the other hand, the following output does not represent a still life. In fact, this configuration brings cells outside the region to live, e.g., {{{lives(0,2)}}} and {{{lives(2,0)}}}. {{{ lives(1,1). lives(1,2). lives(1,3). lives(1,4). lives(2,1). lives(2,4). lives(3,1). lives(3,4). lives(4,1). lives(4,2). lives(4,3). }}} Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/still_life-sample.zip|download]] |
|
| Line 43: | Line 74: |
| '''Complexity''': NP | '''Complexity''': Beyond NP |
| Line 46: | Line 77: |
| * Feb 8th, 2013 - Problem Description updated | |
| Line 52: | Line 83: |
Connected Maximum-density Still Life
Problem Description
A still life is a set of connected live cells from a grid that is fixed under the transition function of John Horton Conway 1970's Game of Life: 1. Any cell with 3 neighbours becomes a live cell. 2. Any live cell with 2-3 live neighbours lives on. 3. Any live cell with <2 or >3 live neighbours dies. The Connected Maximum-density Still Life problem is the task of fitting a given region of the grid with a maximally dense still life, i.e., a maximum number of live cells. (Most work has only looked at pseudo still lifes where the connectedness criterion is dropped.)
Predicates
Input: size/1
Output: lives/2
Input format
We here consider square shaped regions. The size n of the region is provided by an instance of the predicate size/1. Cells connect horizontally, vertically, and diagonally.
Output format
If a still life exists, a witness containing live cells encoded in the predicate lives/2 has to be provided. lives(X,Y) means the grid cell with the unsigned integer coordinates X,Y (=< n) is a live cell.
Cost function
The cost function is given as the number of non-living cells. This value has to be minimized (consequently maximizing the number of living cells).
Example(s)
The first example encodes the region size three by size(3). The maximum density of a connected still life on a region with size three is six live cells. Thus, a sample output is:
lives(1,2). lives(1,3). lives(2,1). lives(2,3). lives(3,1). lives(3,2).
The second example encodes the region size four by size(4). The maximum density of a connected still life on a region with size four is eight live cells. Thus, a sample output is:
lives(1,3). lives(1,4). lives(2,2). lives(2,4). lives(3,1). lives(3,3). lives(4,1). lives(4,2).
On the other hand, the following output does not represent a still life. In fact, this configuration brings cells outside the region to live, e.g., lives(0,2) and lives(2,0).
lives(1,1). lives(1,2). lives(1,3). lives(1,4). lives(2,1). lives(2,4). lives(3,1). lives(3,4). lives(4,1). lives(4,2). lives(4,3).
Additional sample instances: download
Problem Peculiarities
Type: Optimization Competition: Both Complexity: Beyond NP
Notes and Updates
- Feb 8th, 2013 - Problem Description updated
Author(s)
- Author: Christian Drescher
- Affiliation: NICTA, University of New South Wales, Australia