Читать онлайн «Задача о коммивояжере»

В. И. ЛЛудров, профессор, доктор технических наук ЗАДАЧА О КОММИВОЯЖЕРЕ Издательство «Знание» Москва 1969 517. 8 М89 2-2-3 77*9 Глава 1 Математическая формулировка задачи о коммивояжере § L ПОСТАНОВКА ВОПРОСА Наявание этой книги у некоторых читателей, ш-ш- димому, способно вызвать ироническую улыбку. Неужели находятся чудаки, интересующиеся деятельностью и заботами коммивояжеров, которые навсегда исчезли в нашей социалистической стране? Ведь даже в каяитлистических странах они почта прекратили свои путешествия с целы© выяснения конъюнктуры, рекламирования образцов wmapm я заключения соглашений об их поставке, поскольку владельцы предприятий предпочитают пользоваться для этого более современными способами поддержания деловых контактов. Надо прямо сказать, что таких людей, но крайней мере среди инженеров и математиков, в настоящее время нет, «го к задаче, известной под этим названием ш насчитывающее более чем двухсотлетнюю историю, интерес ие только йе ослабевает, но, наоборот, постоянно возрастает» ш многие знаменитые ученые, начиная с Эйлера1 и Гамильтона2 и кончая выдающимися математиками современности Д. Данцигом3, 1 Эйлер, Леонард <{1707—1783 тг) — великий математик, механик и физик. С 1727 т. академик Российской академия наук. Круг занятий Эйлера был необыкновенно широким и охватывал все разделы современной ему математики и механики, теорию упругости, математическую физику, оптику, теорию машин, теорию музшси, баллистику, морскую науку, страховое дело и т. д. Во всех без исключения разделах он получил основополагающие результаты. 2 Гамильтон, Уильям Роуан (1805—1865 гг. )—знаменитый английский математик и механик. С 1827 г. и до конца жизни — профессор астрономии в Дублинском университете. Является одним из основоположников векторного исчисления, теории гиперкомплексных чисел и вариационных методов механики. 3 Данциг, Джордж Беряард (род. 1914 г. ) —известный американский математик, профессор Калифорнийского университета, сотрудник корпорации RAND, один из основоположников теории линейного программирования. 3 Р. Беллманом1 и другими, предлагали методы ее решения, проверяя одновременно на ней возможности новых вычислительных приемов и методов. Хотя первоначально задача возникла как чисто развлекательная, впоследствии она утратила этот характер и нашла многочисленные практические применения. Так часто бывает в истории науки. Решения многих задач, казавшихся поначалу развлечениями и головоломками, впоследствии послужили ключом для решения важных теоретических и практических вопросов. Укажем, например, на задачу кавалера Де-Мере2, которая была решена Паскалем3 и послужила толчком для возникновения одного из основных понятий теории вероятностей—понятия математического ожидания, или на игры типа игры в «орлянку», размышления над которыми привели Бо- реля4 к формулировке основной теоремы теории игр, являющейся в настоящее время главным инструментом при изучении конфликтных ситуаций. При этом, конечно, нужно иметь в виду, что выдающиеся ученые, занимаясь подобными задачами, предвидели фундаментальную роль научных теорий, кладущихся в основу их решения.