9. Список литературы

1. Bellmore М., Nemhauser G. L. (1968), The travelling salesman problem - a survey. Ops. Res., 16, p. 538.

2. Bellmore M., Malone J. C. (1971), Pathology of travelling salesman subtour-elimination algorithms. Ops. Res., 19, p. 278.

3. Burstall R. M. (1967), Tree-searching methods with an application to a network design problem. Machine Intelligence, Vol. 1, Collins and Michie, Eds., Oliver and Boyd, London.

4. Camerini P. M., Fratta L., Maffioli F. (in press). The travelling salesman problem: heuristically guided search and modified gradient techniques.

5. Charlton J. M., Death C. C. (1970), A method of solution for general machine-scheduling problems. Ops. Res., 18, p. 689.

6. Christofides N. (1973), Large scheduling problems with bivalent costs, The Computer J., 16, p. 263.

7. Christofides N. (1970), The shortest Hamiltonian chain of a graph, /. of SIAM {Appl. Math), 19, p. 689.

8. Christofides N. (1972), Bounds for the travelling salesman problem. Ops. Res., 20, p. 1044.

9. Christofides N., Eilon S. (1969), An algorithm for the vehicle dispatching problem, Opl. Res. Quart., 20, p. 309.

10. Christofides N., Eilon S. (1972), Algorithms for large-scale travelling salesman problems, Opl. Res. Quart., 23, p. 511.

11. Danielson G. H. (1968), On finding the simple paths and circuits in a graph, IEEE Trans., CT-15, p. 294.

12. Demoucron G., Malgrange Y., Petmiset R. (1964), Graphes planaires; reconnaissance at construction de representations planaires topologiques. Rev. Fran, de Resh. Oper., 8, p. 33.

13. Deo N., Hakimi S. L. (1965), The shortest generalized Hamiltonian tree, Proc. 3rd Allerton Conference on Circuit and Systems Theory, University of Illinois, Urbana, p. 879.

14. Dhawan V. (1969), Hamiltonian circuits and related problems in graph theory, M. Sc. Report, Imperial College, London.

15. Eilon S., Watson-Gandy C. D. Т., Christofides N. (1971), Distribution Management: Mathematical modelling and practical analysis. Griffin, London.

16. Gilmore P. C, Gomory R. E. (1964), Sequencing a one-state variable machine; a solvable case of the travelling salesman problem. Ops. Res., 12, p. 655.

17. Haring D. R. 1966), Sequential-circuit synthesis, MIT Press, Research Monograph 31, Cambridge, Massachusetts.

18. Held M., Karp R. M. (1970), The travelling salesman problem and minimum spanning trees. Ops. Res., 18, p. 1138.

19. Held M., Karp R. M. (1971), The travelling salesman problem and minimum spanning trees. Part II, Math. Progr., 1, p. 6.

20. Krolak P., Felts W., Marble G. (1971), A man-machine approach toward solving the travelling salesman problem. Comm. of ACM, 14, p. 327.

21. Lawler E. L. (1971), A solvable case of the travelling salesman problem. Math. Prog., 1, p. 267.

22. Lin S. (1965), Computer solutions of the travelling salesman problem. Sell Syst. Tech. J., 44, p. 2245.

23. Lin S., Kernighan B. W. (1971), A heuristic technique for solving a class of combinatorial optimization problems, Princeton Conf. on System Science.

24. Maffioli F. (1973), The travelling salesman problem and its implications. Report, Institute di Elettrotecnica ed Elettronica, Politechnico di Milano.

10. Приложение

Ниже излагается алгоритм вычисления верхней границы В минимального числа перенастроек аппаратуры, требующихся в задаче планирования из разд. 4 данной главы, который можно использовать в качестве начального алгоритма этого раздела.

Шаг 0. Индекс ч- О, 5 ч- 0.

Шаг 1. Взять метки I (zj) = 0, V л:; 6 Z. Положить р = 0. Шаг 2. G = (X, А), выбрать любое х^, g Z, положить S =

= К}.

Шаг 3. Если индекс =0, образовать S = S \} Т (5); в противном случае S = S [} Т' (S). Здесь Г (xt) ={xj {xt, Xj) 6 А} и Г (S) = и Г (Xi), а также

r-4xO{xj\ixj,Xt)A} и Г-1(5)= и r-i(zO.

Шаг 4. Если S = S, то перейти к шагу 5; в противном случав р ч- р -f 1, I (xi) -<r- рУ/ Xi S - S, S -(-S и вернуться к шагу 3.

25. Nash-Williams С, St, J. А. (1966), On Hamiltonian circuits in finite graphs, Proc. American Mathematical Soc, 17, p. 466.

26. Ore O. (1962), Theory of Graphs, American Mathematical Society, New-York.

27. Перепелица В. A., Гимади Э. X. (1969), К задаче нахождения минимального гамильтонова контура на графе со взвешенными дугами, сб. Дискретный анализ , Новосибирск, стр. 57-65.

28. РоЫ J. (1970), Heuristic search viewed as path in a graph. Artificial Intelligence, 1, p. 193.

29. Posa L. (1962), A theorem concerning Hamiltonian lines, Magyar Tnd. Akad. Mat. Kutatd Int. Kozl., 7, p. 225.

30. Roberts S. M., Flores B. (1967), An engineering approach to the travelling salesman problem, Man. Sci., 13, p. 269.

31. Roberts S. M., Flores B. (1966), Systematic generation of Hamiltonian circuits. Comm. of ACM, 9, p. 690.

32. Roy B. (1959), Recherche des circuits elementaires et des circuits Hamil-toniens dans un graphe quelconque, Mimeographe, Soc. de Math. Appl., Paris.

33. Roy B. (1969, 1970), Algebre modern et theorie des graphes. Vols 1 an 2, Dunod, Paris.

34. Рубинштейн M. И. (1971), O симметричной задаче коммивояжера. Автоматика и телемеханика, 9, стр. 126.

35. Selby G. R. (1970), The use of topological methods in computer-aided circuit layout. Ph. D. Thesis, London University.

36. Syslo M. M. (1973), A new solvable case of the travelling salesman problem. Math. Prog., 4, p. 347.

37. Yau S. S. (1967), Generation of all Hamiltonian circuits, paths and centres of a graph and related prolblems, IEEE Trans., CT-14, p. 79.

Шаг 5. Найти х {xt \ I (х;) = р).

Шаг 6. Если индекс=0, найти х' {xi \ I (х,) = р - 1 и {х', х) А}; в противном случае найти х' {Xi \ I (х;) = р - 1 и {х, х) 6 А).

Шаг 7. X Х-{х},А^А -{{х, ж;) \Xi Х) ~{{xi, х) \ XiX). Если ж ={хо}, то 5 4-5 + 1 и перейти к шагу 12; в противном случае перейти к шагу 8.

Шаг 8. ж -е-ж', р /7 - 1. Если х' = х^, перейти к шагу 9; в противном случае перейти к шагу 5.

Шаг 9. Если индекс =0, индекс1 и перейти к шагу 1; в противном случае перейти к шагу 10.

Шаг 10. Если X = {хд}, то 5 -е- 5 -f 1 и перейти к шагу 12; в противном случае перейти к шагу И.

Шаг 11. Индекс ч- О, 5 ч- 5 + 1.

X ч- Z - {хд}, А^А- ({(хо, Xi) \xiX)- {[xi, Хо) I Xi g X}). Шаг 12. Стоп. В является требуемой верхней границей.

Алгоритм требует некоторых пояснений. Если индекс =0, то прослеживаются прямые цепи, проходящие по вершинам графа G, начиная с вершины Хд. Эти цепи прослеживаются с присвоением метки р тем вершинам из G, которые могут быть достигнуты из Хо через р дуг (шаги 1, 2, 3 и 4). Если ни одна из этих цепей не может быть продолжена, то алгоритм переходит к шагам 5, 6 и 7, в которых самая длинная из этих цепей прослеживается назад к вершине Хо, при этом убираются из графа вершины (и ассоциированные с ними дуги), лежащие на этой самой длинной цепи. Шаг 8 прекращает процесс удаления вершин. Шаг 9 возвращает к началу алгоритма со значением индекса =1, чтобы начать формирование обратных цепей, т. е. цепей, оканчивающихся в х^. Снова находится и удаляется самая длинная из этих цепей.

Самая длинная из прямых и обратных цепей (в или из Хо) может рассматриваться как одна длинная цепь, содержащая Хо. Число В (необходимых последовательностей цепей) увеличивается тогда на единицу на шаге 11, и после выбора другой вершины Хо из оставшегося графа процесс продолжается (формируются новые длиннейшие прямые и обратные цепи и т. д.), пока не будет исчерпан весь граф.

Конечное значение В, которое равно числу последовательностей цепей, необходимых для стирания всего графа (т. е. для покрытия всех вершин), является тогда, очевидно, верхней границей для требуемого минимального числа таких покрывающих последовательностей (т. е. минимального числа перенастроек аппаратуры).