So sánh lý thuyết các chiến lược tìm kiếm trong thuật toán nhánh và rìa
Tóm tắt
Từ khóa
#thuật toán nhánh và rìa #tìm kiếm heuristic #tìm kiếm theo chiều sâu #tìm kiếm theo cách tốt nhất #tìm kiếm theo chiều rộngTài liệu tham khảo
N. Agin, “Optimum Seeking with Branch and Bound,”Manage. Sci. 13:B176-B185 (1966).
E. Balas, “A Note on the Branch-and-Bound Principle,”Oper. Res. 16:442–445 (1968).
E. Balas, “Discrete Programming by the Filter Method,”Oper. Res. 15:915–957 (1967).
M. Benichou, J. M. Gauthier, P. Girodet, G. Hentges, G. Ribiere, and O. Vincent, “Experiments in Mixed-Integer Linear Programming,”Math. Program. 1:76–94 (1971).
J. J. H. Forrest, J. P. H. Hirst, and J. A. Tomlin, “Practical Solution of Large Mixed Integer Programming Problems with umpire,”Manage. Sci. 20:736–773 (1974).
B. L. Fox and L. E. Schrage, “The Values of Various Strategies in Branch-and-Bound,” Technical Report, Graduate School of Business, University of Chicago (1972).
A. M. Geoffrion, “Integer Programming by Implicit Enumeration and Balas Method,”SIAM Rev. 9:178–190 (1967).
F. Glover, “A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem,”Oper. Res. 13:879–919 (1965).
S. W. Golomb and L. D. Baumert, “Backtrack Programming,”JACM 12:516–524 (1965).
P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimal Cost Paths,”IEEE Trans. Sys. Sci. Cybern. SSC-4:100–107 (1968).
T. Ibaraki, “A Generalization of Depth-First Search in Branch-and-Bound Algorithms,” Working Paper, Department of Applied Mathematics and Physics, Kyoto University (1974).
T. Ibaraki, “The Power of Dominance Relations in Branch-and-Bound Algorithms,” Working Paper, Department of Applied Mathematics and Physics, Kyoto University,JACM, to appear (1975).
T. Ibaraki, “On the Computational Efficiency of Branch-and-Bound Algorithms,” Working Paper, Department of Applied Mathematics and Physics, Kyoto University (1975).
W. H. Kohler and K. Steiglitz, “Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems,”JACM 21:140–156 (1974).
E. L. Lawler and D. E. Wood, “Branch-and-Bound Method: A Survey,”Oper. Res. 14:699–719 (1966).
L. G. Mitten, “Branch-and-Bound Method: General Formulation and Properties,”Oper. Res. 18:24–34 (1970).
N. J. Nilsson,Problem-Solving Methods in Artificial Intelligence (McGraw-Hill, New York, 1971).
I. Pohl, “First Results on the Effect of Error in Heuristic Search,” inMachine Intelligence 5, B. Meltzer and D. Michie, Eds. (Edinburgh University Press, 1969).
S. K. Sahni,“Algorithms for Scheduling Independent Tasks,”JACM 23:114–127(1976).