How do spaceship search programs work?
-
- Posts: 1
- Joined: July 21st, 2020, 6:48 am
How do spaceship search programs work?
I'm fairly new to cellular automatons, but I've recently sparked an interest in them. I've found the spaceships to be really cool, and have come upon spaceship search programs. I've looked through the source code of qfind but was unable to understand the underlying algorithms. Sorry if this is a noob question, but I would appreciate it if someone could explain how it works to me!
Re: How do spaceship search programs work?
This post by wildmyron might be a good place to start. BFS = breadth-first search and DFS = depth-first search, and other basic terms used in that message, are not specific to CA or to spaceship search problems, so you can read up about them starting from a standard Google search.LivingJimbo wrote: ↑July 21st, 2020, 7:06 amI'm fairly new to cellular automatons, but I've recently sparked an interest in them. I've found the spaceships to be really cool, and have come upon spaceship search programs. I've looked through the source code of qfind but was unable to understand the underlying algorithms. Sorry if this is a noob question, but I would appreciate it if someone could explain how it works to me! :)
Re: How do spaceship search programs work?
qfind's algorithm is just gfind but the de Bruijn graphs are replaced by a large lookup table. gfind's algorithm is described in this paper by David Eppstein.LivingJimbo wrote: ↑July 21st, 2020, 7:06 amI've looked through the source code of qfind but was unable to understand the underlying algorithms.
zfind may be easier to understand than qfind or gfind. It works essentially the same way as qfind, but is completely depth-first (rather than breadth-first with depth-first look ahead). You may learn something from browsing the zfind discussion thread.
-Matthias Merzenich