The previous section involves a kind of search known as hill-climbing, where if you have several choices at any point, you calculate a numerical measure (a weight) for each, pick the best, and explore that, proceeding in the same way for all subsequent choices. In LINKS2, the weights were pre-calculated by me, and they have no obvious relevance to anything else. However, you can apply the same method to problems where the weights are not known in advance.
Consider the problem of synthesising some new wonder-compound, say interferon. There is usually more than one reaction that will produce a given compound. The chemical literature is full of lists of reactions, the circumstances under which they can be applied, and the chemical needs and costs of each. So - we start at interferon. We make a list of all reactions that can plausibly be used. Think of each as a path leading off from interferon. From general principles, we can then assign a weight to each. Some, such as the one where the reactants are so unstable that their molecules need to be isolated inside individual micro black holes, and the one that requires you to boil the reactants in a 50:50 hydrofluoric acid/liquid radium mixture inside a 10 cubic meter diamond reaction vessel, will be rather costly - i.e. high weight. Others, like the one where you distil the reactants from a kilo of fermented garden slugs, will be less so. Having assigned the weights, pick the lowest. That gives you the cheapest reaction. You then proceed in the same way with its starting materials, and so on. A similar procedure is in fact used in commercial programs for synthesis planning.
My first attempt at the
route predicate of
Supplement 5 worked in this way. At each square, it looked at all those
leading from it. It then worked out the distance of each to the
destination, picked the nearest, and then moved on to it as the next
square. Because of bends in the streets, this did not always give the
shortest path, but it was a good first approximation.