summaryrefslogtreecommitdiffstats
path: root/bfs.1
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2020-06-12 16:02:07 -0400
committerTavian Barnes <tavianator@tavianator.com>2020-06-16 09:02:11 -0400
commitbf063268ea9a11bc5413864626a4b945b1ecf80b (patch)
tree5b12dd6d045b6a7ea8df8e7845df9e7d2a675ba7 /bfs.1
parent8cf40eeaf953b1c2f5c097623572948c4630ee39 (diff)
downloadbfs-bf063268ea9a11bc5413864626a4b945b1ecf80b.tar.xz
Implement exponential deepening search
Diffstat (limited to 'bfs.1')
-rw-r--r--bfs.144
1 files changed, 32 insertions, 12 deletions
diff --git a/bfs.1 b/bfs.1
index 20e1c77..4c78bde 100644
--- a/bfs.1
+++ b/bfs.1
@@ -126,20 +126,21 @@ Turn on a debugging flag (see
.RS
Enable optimization level
.I N
-(default: 3)
+(default:
+.IR 3 ).
.TP
-\fB\-O\fI0\fR
+.BI \-O 0
Disable all optimizations.
.TP
-\fB\-O\fI1\fR
+.BI \-O 1
Basic logical simplifications.
.TP
-\fB\-O\fI2\fR
+.BI \-O 2
All
.BI \-O 1
optimizations, plus dead code elimination and data flow analysis.
.TP
-\fB\-O\fI3\fR
+.BI \-O 3
All
.BI \-O 2
optimizations, plus re-order expressions to reduce expected cost.
@@ -147,15 +148,34 @@ optimizations, plus re-order expressions to reduce expected cost.
\fB\-O\fI4\fR/\fB\-O\fIfast\fR
All optimizations, including aggressive optimizations that may alter the observed behavior in corner cases.
.RE
+.PP
+\fB\-S \fIbfs\fR|\fIdfs\fR|\fIids\fR|\fIeds\fR
+.RS
+Choose the search strategy.
.TP
-\fB\-S \fIbfs\fR|\fIdfs\fR|\fIids\fR
-Use
-.IR b readth- f irst/ d epth- f irst/ i terative
-.IR d eepening
-.IR s earch
-(default:
+.I bfs
+Breadth-first search (the default).
+.TP
+.I dfs
+Depth-first search.
+Uses less memory than breadth-first search, but is typically slower to return relevant results.
+.TP
+.I ids
+Iterative deepening search.
+Performs repeated depth-first searches with increasing depth limits.
+This gives results in the same order as breadth-first search, but with the reduced memory consumption of depth-first search.
+Tends to be very slow in practice, so use it only if you absolutely need breadth-first ordering, but
+.B \-S
+.I bfs
+consumes too much memory.
+.TP
+.I eds
+Exponential deepening search.
+A compromise between breadth- and depth-first search, which searches exponentially increasing depth ranges (e.g 0-1, 1-2, 2-4, 4-8, etc.).
+Provides many of the benefits of breadth-first search with depth-first's reduced memory consumption.
+Typically far faster than
.B \-S
-.IR bfs ).
+.IR ids .
.RE
.SH OPERATORS
.TP