forked from johannesgerer/jburkardt-f
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathpartial_digest.html
284 lines (241 loc) · 7.93 KB
/
partial_digest.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
<html>
<head>
<title>
PARTIAL_DIGEST - Recursive Solutions of the Partial Digest Problem
</title>
</head>
<body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">
<h1 align = "center">
PARTIAL_DIGEST <br> Recursive Solutions of the Partial Digest Problem
</h1>
<hr>
<p>
<b>PARTIAL_DIGEST</b>
is a FORTRAN90 program which
seeks solutions of the partial digest problem.
</p>
<p>
In the partial digest problem, we assume that there are <b>N</b>
objects arranged along a line. We denote the position of object <b>I</b>
by <b>X(I)</b>. The positions of the objects are unknown. Instead,
we have a list of the distances between every distinct pair of objects.
Note that the distances are not "tagged"; that is, if there is a 175
on the list of distances, we don't know which two objects are separated
by that distance. In the partial digest problem, we start with the
<b>(N*(N-1))/2</b> distances, and must come up with at least one
linear arrangement of <b>N</b> objects that corresponds to the distances.
</p>
<p>
In the algorithm used here, we begin by arbitrarily setting <b>X(1)</b>
to zero.
</p>
<p>
For our second step, we find the largest entry in the distance table, and
set <b>X(2)</b> to that value.
</p>
<p>
On each recursive step thereafter, we find the largest unused distance,
<b>D</b>, and note that this must represent the distance of the next
object from either <b>X(1)</b> or <b>X(2)</b>.
</p>
<p>
Starting with the first possibility,
we consider placing this next object at <b>X(K)=D</b>. We now must
search the distance table, and ensure that the distances
<b>|X(1)-X(K)|</b>
through <b>|X(K-1)-X(K)|</b> all show up. If so, then our tentative placement
of the object is "plausible", and we can proceed to the next step of recursion,
seeking the location of <b>X(K+1)</b>.
</p>
<p>
The second possibility to check on this recursive step is that we should
set <b>X(K)=X(2)-D</b>, since this would also explain the occurrence of
the distance <b>D</b>. The analysis of this case is otherwise the same
as for the first one.
</p>
<p>
This recursion is guaranteed to "encounter" every solution. (Of course,
there might be no solutions whatever.)
</p>
<p>
This approach has the advantage that recursion is relatively clean
and neat to program. Disadvantages include the fact that the amount
of memory required to store partial results will grow explosively
as the size of the problem increases. Also, it is difficult to intervene
or interrupt the recursive process. For instance, the calling program
never receives the computed solutions directly. Instead, the recursive
routine "realizes" that it has computed a solution, and can print it out.
</p>
<p>
For these reasons, it would be worth developing an equivalent version
of the routines that uses backtracking instead.
</p>
<p>
Note that this program used <b>integers</b> for the distances. While
this is somewhat unnatural, it is convenient when programming, since
we are searching the list of distances for values that we arrive at
by subtraction, and the slightest roundoff would mean that the algorithm
would fail. An alternative would be to allow floating point distances,
but to allow a very slight margin of error when looking for a distance
in the table that is equal to a difference calculated between two positions.
</p>
<h3 align = "center">
Licensing:
</h3>
<p>
The computer code and data files described and made available on this web page
are distributed under
<a href = "../../txt/gnu_lgpl.txt">the GNU LGPL license.</a>
</p>
<h3 align = "center">
Related Data and Programs:
</h3>
<p>
<a href = "../../f_src/cities/cities.html">
CITIES</a>,
a FORTRAN90 library which
carries out various
computations involving the locations or relative distances
of cities on a map.
</p>
<p>
<a href = "../../datasets/cities/cities.html">
CITIES</a>,
a dataset directory which
defines the locations or relative distances
of cities on a map.
</p>
<p>
<a href = "../../f_src/combo/combo.html">
COMBO</a>,
a FORTRAN90 library which
carries out various combinatorial computations.
</p>
<p>
<a href = "../../f_src/distance_to_position/distance_to_position.html">
DISTANCE_TO_POSITION</a>,
a FORTRAN90 program which
estimates the positions of cities based on a city-to-city distance table.
</p>
<p>
<a href = "../../f_src/geometry/geometry.html">
GEOMETRY</a>,
a FORTRAN90 library which
computes various geometric
quantities.
</p>
<p>
<a href = "../../f_src/grafpack/grafpack.html">
GRAFPACK</a>,
a FORTRAN90 library which
manipulates abstract
graphs.
</p>
<p>
<a href = "../../f77_src/knapsack/knapsack.html">
KNAPSACK</a>,
a FORTRAN77 library which
solves a variety of knapsack problems.
</p>
<p>
<a href = "../../f77_src/lamp/lamp.html">
LAMP</a>,
a FORTRAN77 library which
solves linear assignment and matching problems.
</p>
<p>
<a href = "../../f_src/subset/subset.html">
SUBSET</a>,
a FORTRAN90 library which
carries out various combinatorial computations.
</p>
<p>
<a href = "../../f_src/subset_sum/subset_sum.html">
SUBSET_SUM</a>,
a FORTRAN90 library which
seeks solutions of the subset sum problem.
</p>
<h3 align = "center">
Reference:
</h3>
<p>
<ol>
<li>
Pavel Pevzner,<br>
Computational Molecular Biology,<br>
MIT Press, 2000,<br>
ISBN: 0-262-16197-4,<br>
LC: QH506.P47.
</li>
</ol>
</p>
<h3 align = "center">
Source Code:
</h3>
<p>
<ul>
<li>
<a href = "partial_digest.f90">partial_digest.f90</a>, the source code.
</li>
<li>
<a href = "partial_digest.sh">partial_digest.sh</a>,
commands to compile the source code.
</li>
</ul>
</p>
<h3 align = "center">
Examples and Tests:
</h3>
<p>
<ul>
<li>
<a href = "partial_digest_prb.f90">partial_digest_prb.f90</a>,
a sample calling program.
</li>
<li>
<a href = "partial_digest_prb.sh">partial_digest_prb.sh</a>,
commands to compile and run the sample program.
</li>
<li>
<a href = "partial_digest_prb_output.txt">partial_digest_prb_output.txt</a>,
the output file.
</li>
</ul>
</p>
<h3 align = "center">
List of Routines:
</h3>
<p>
<ul>
<li>
<b>DELETE_MAX</b> extracts the maximum entry from an I4VEC.
</li>
<li>
<b>FIND_DISTANCES</b> determines if the "free" distances include every ||X(I)-Y||.
</li>
<li>
<b>I4VEC_PRINT</b> prints an I4VEC.
</li>
<li>
<b>PLACE</b> tries to place the next point for the partial digest problem.
</li>
<li>
<b>PARTIAL_DIGEST</b> searches for solutions to the partial digest problem.
</li>
<li>
<b>TIMESTAMP</b> prints the current YMDHMS date as a time stamp.
</li>
</ul>
</p>
<p>
You can go up one level to <a href = "../f_src.html">
the FORTRAN90 source codes</a>.
</p>
<hr>
<i>
Last revised on 28 November 2006.
</i>
<!-- John Burkardt -->
</body>
<!-- Initial HTML skeleton created by HTMLINDEX. -->
</html>