/ahc019

AtCoder Heuristic Contest 019

Primary LanguageC++MIT LicenseMIT

ahc019

AtCoder Heuristic Contest 019

Problem

https://atcoder.jp/contests/ahc019/tasks/ahc019_a

Input

  • D: integer
  • $f_1$ : $D \times D$ array representing the silhouette of $G_1$ in the $z$- $x$ plane
  • $r_1$ : $D \times D$ array representing the silhouette of $G_1$ in the $z$- $y$ plane
  • $f_2$ : $D \times D$ array representing the silhouette of $G_2$ in the $z$- $x$ plane
  • $r_2$ : $D \times D$ array representing the silhouette of $G_2$ in the $z$- $y$ plane

Formulation

  • Let $G_1$, $G_2$ be two (undirected) graph;

    • Each $G_i$ represents an assembling pattern whose silhouette matches $f_i$ and $r_i$.

  • $G_i$ is defined as

    • $V(G_i)$;
    • $E(G_i) = {{(x, y, z), (x+1, y, z)}\colon x \in [D-1]} \cup {{(x, y, z), (x, y+1, z)}\colon y \in [D-1]} \cup {{(x, y, z), (x, y, z+1)}\colon z \in [D-1]}$

  • I considered that each connected components of $G_1$ and $G_2$ as a piece of puzzle.

  • To maintain common components, I considered $G = G_1 \cup G_2$ as a union of two graph.

    • If two connected components $c_1 \subseteq G_1$ and $c_2 \subseteq G_2$ are common piece of the puzzle, then I defined $c = c_1 \cup c_2 \cup {{r, p}} \subseteq G$, where $r \in V(G_1)$ and $p \in V(G_2)$, as a connected components which represents the common piece.
    • Use an Union-Find to maintain connected components of $G$.

Approach

Basic Idea: a greedy approach

  1. Starts from a state with all vertices are isolated.
  2. Chose candidates of vertices $S_1 \in V(G_1)$, $S_2 \in V(G_2)$, axis of rotation (defined as axis), and degree (defined as unit) randomly.
  3. For all possible pair $(r, p) \in S_1 \times S_2$, *. run BFS starts from $(r, p)$. In the BFS step, I defined following rules:
    • In $G$, two pair of vertices $(r, p)$ and $(u, q)$ can be united if they hold following all conditions
      • ${r, u} \in E(G_1)$
      • ${p, q} \in E(G_2)$
      • $r, p, u, q$ are all isolated
  • $q$ is defined by a given axis, unit and difference of coordinates of $r$ and $u$.
  1. Take the best state as a new state, and go back to step 2.

First Improvement: a beam search

  • keep top $k$ states in each iteration.
    • But I didn't notice that I embeded a bug (it held one state every iteration = simple greedy!)

Second Improvement: calculate a hash value of a state

  • After bfs step, I noticed that almost states have same scores.
    • I supposed that same states can be generated by different choices of $(r, p, unit, axis)$.
    • I used a Zobrist hash to prevent to keep same states at same level of search.
      • When I computes a Zobrist hash of each states, I assigned a random number for each tuple of $(v, root(v))$, where $v$ is a vertex of $G$ and $root(v)$ is a root of $v$ in the Union-Find tree.
        • In order to keep reproducibility of the hash value, I modified my Union-Find implementation so that it always stores the smallest value of the set.

Third Improvement: performance improvement of computing score/hash

Since it was expensive to recalculate scores and hash values for every states in each iteration, I improved performaces for score&hash calculation as follows:

  • Basic idea (of score evaluation): compute for merged components and isolated vertices separatelly.

    1. In my algorithm, for each vertex, a merge operation will be done at most one time.
    2. It is sufficient to update scores only when bfs (and merge operation) has completed for designated $r$ and $p$.
    3. After bfs procedure, I updates the score for connected components by adding $10^6 \times \frac{1}{v_i}$ (I used a smaller constant than in official problem website because it can be overflowed in early stage).
    • During merge operation, I also maintained silhouettes made only by merged vertices.
    1. Finaly, I updates the remaining scores for isolated components.
    • In order to remember isolated vertices in $G_1$ and $G_2$, I prepared a set of vertices named fragment.

  • Basic idea(of hash calculation): compute only for merged components.

    1. As I mentioned, each vertex will be united at most one time.
    2. For each iteration, prepare a set of vertex dirty_vertex which maintains merged vertices.
    3. When bfs was stopped (i.e., one search procedure for specific $r \in V(G_1)$ and $p \in V(G_2)$ has completed), I update the hash value by using each $v$ in dirty_vertex,

Other features (but I'm not sure each of them has any effect..)

I changed following parameters depends on an input size $D$.

  1. Change the number of samples to be searched by bfs between early stage of search and later stage.
  • The value will be changed linearly from s_samplesize to e_samplesize.
  1. Parameterized width of beam search (defined as beamwidth)
  2. Restrict the depth of bfs by a maxdepth parameter.
  3. Switch the search algorithm depends on $D$
  • I tried all possible axis and unit for small $D$.
  • For large $D$, I choose axis and unit randomly.

I tried parameter tuning by optuna, but I couldn't get any good insight from the result.