On the recognition of structural features: Some general problems illustrated by hamiltonian paths in polyhexes
Tóm tắt
Human and machine recognition skills are discussed, though not comprehensively reviewed, and some of the difficulties are illustrated by algorithms written to search for Hamiltonian paths in polyhexes. The most successful strategy for this is based upon the “branching graph”, a recently introduced graph-theoretical device which can aid the recognition of edges that arenot part of a Hamiltonian path. Another, more widely applicable approach that is interesting, although in this preliminary form only a little better than random methods, uses the metaphor of biological evolution, and tries to “breed” and “grow” paths subjected to “natural selection”.
Tài liệu tham khảo
E.C. Kirby, J. Math. Chem. 1 (1987)175.
E.C. Kirby, J. Math. Chem. 4 (1990)31–46.
R.B. Mallion, private communication (12th April 1989).
J. Gayoso and A. Boucekkine, Comp. Rend. Acad. Sci. (Paris) C272 (1971)184.
R. McWeeny, Mol. Phys. 1 (1959)311.
N.L. Biggs, E.K. Lloyd and R.J. Wilson,Graph Theory 1736–1936 (Clarendon Press, Oxford, 1976).
The Shorter Oxford Dictionary, 3rd ed. (Guild Publ., London, 1988).
Charles R. Darwin,On the Origin of Species by Means of Natural Selection (1859).
J. Bronowski,The Ascent of Man (British Broadcasting Corporation Publ., London, 1973).
G.G. Hall and J.R. Dias, J. Math. Chem. 3 (1989)233.
M. Randić, Theor. Chim. Acta 62 (1983)485.
T. Okuyama, Y. Miyashita, S. Kanaya, H. Katsumi, S. Sasaki and M. Randić, J. Comput. Chem. 9 (1988)636.
W.C. Herndon and S.H. Bertz, J. Comput. Chem. 8 (1987)367.
P.G. Mezey, J. Math. Chem, 2 (1988)299.
M.A. Johnson, J. Math. Chem. 3 (1989)117.
D. Bonchev, V. Kamenska and O. Mekenyan, Int. J. Quant. Chem. 37 (1990)135.
F. Harary and P.G. Mezey, J. Math. Chem. 2 (1988)377.
G.M. Downs, V.J. Gillet, J.D. Holliday and M.F. Lynch, J. Chem. Inf. Comput. Sci. 29 (1989)172.
R.C. Read, J. Chem. Inf. Comput. Sci. 23 (1983)135; 25(1985)116.
J. Graham Kerr, Trans. N.E. Coast Inst. Eng. and Shipbuilders 35 (1919)256; Nature 149(1942)221; Naut. Mag. (1942) June 22.
M.A. Boden,Artificial Intelligence and Natural Man (Harvester Press, 1984).
C. Longuet-Higgins, Nature 343 (1990)214.
J.D. Searle, BBC Reith Lectures (1984);Minds, Brains and Science (Penguin Press, London, 1989).
M. Randić, J. Chem. Phys. 60 (1974)3920.
J.B. Hendrickson and A.G. Toczko, J. Chem. Inf. Comput. Sci. 23 (1983)171.
J.V. Knop, W.R. Müller, K. Szymanski and N. Trinajstić,Computer Generation of Certain Classes of Molecules (SKTH/Kemija u industriji, Zagreb, 1985).
J. Cioslowski, J. Comput. Chem. 8 (1987)906.
M. Randić, Croat. Chem. Acta 59 (1986)327, and references therein.
D.W. Sumners, J. Math. Chem. 1 (1987)1, and references therein.
T.P. Kirkman, Roy. Soc. London 146 (1856)413 (cited in ref. [6]).
I. Gutman and E.C. Kirby, MATCH 26(1991), in press.
H. Hosoya and T. Yamaguchi, Tetrahedron Lett. (1975)4659.
N. Ohkami, A. Motoyama, T. Yamaguchi, H. Hosoya and I. Gutman, Tetrahedron 37 (1981)1113.
S. El-Basil, P. Krivka and N. Trinajstić, Croat, Chem. Acta 57 (1984)339.
T.G. Schmalz, G.E. Hite and D.J. Klein, J. Phys. A, Math. Gen. 17 (1984)445.
J.R. Dias, Nouv. J. Chim. 9 (1985)125.
J.V. Knop, W.R. MÜller, K. Szymanski and N. Trinajstić, J. Comput. Chem. 7 (1986)547.
E.C. Kirby, Comput. Chem. 9 (1985)155.
R. Dawkins,The Blind Watchmaker (Longman, 1986; Penguin Books, London, 1988).
G. Wilson,The life and times of cellula automata, New Scientist (8th October, 1988), p. 44.
I. Gutman and S.J. Cyvin,Introduction to the Theory of Benzenoid Hydrocarbons (Springer, Berlin, 1989).
J.V. Knop, W.R. Müller, K. Szymanski, S. Nikolić and N. Trinajstić, in:Computational Chemical Graph Theory, ed. D.H. Rouvray (Nova, New York, 1990).
N. Trinajstić, J. Math. Chem. 5 (1990)171.
J.R. Dias,Handbook of Polycyclic Hydrocarbons (Elsevier, Amsterdam-New York, Part A 1987; Part B 1988).
E.C. Kirby, J. Chem. Soc. Faraday Trans. 86 (1990)447.