Простая задача с непростыми логическими и математичеcкими проблемами (можно найти ответ, а как строго решать "задачи коммивояжера") в кольце "Информация Наука Культура": математики, Инженеры, менеджеры, логистика The tutor's Courses

Кольцо ИНК
Новости раздела "Образование" Открыть РАЗДЕЛЫ ИНК в новом окне Окно разделов ИНК

This page:

Russian
English

Disability

Под общим руководством Борзых А.А. { >> }
"Информация Наука Культура"

сайт естественно- математического образования

Обсуждения в клубе "Математический склад ума и когнитология: задачи из жизни и их формализация"

Наш профиль - СИСТЕМНЫЕ ИССЛЕДОВАНИЯ

ОТ ПОПУЛЯРНОЙ МАТЕМАТИКИ К ПРОБЛЕМАМ ЛОГИКИ И МАТЕМАТИКИ
Вопросы для задумывающихся о методах
(с этими задачами сталкиваются инженеры, экономисты, менеджеры, специалисты по логистике, а можно задуматься математикам и когнитологам)
{ >>} Все виды заданий серии

© A.Borzykh. 2005. Version 1.0 ; © A.Borzykh. 2010. Version 2.0
Несанкционированное копирование и использование тестов запрещено.

Настоящие тесты, разработанные А.А. Борзых,
являются элементами учебно-методического комплекса в тренинговых программах ИНКЦентра. В апробации тестов участвовали слушатели семинаров "Инновационно- консалтингового центра".

Тест ранее опубликован в учебном пособии "Приемы формализации в исследованиях социально-экономических систем (2005)".

От нашей игры "Стать миллионером?" и простой "задачи коммивояжера" шагните к задаче с непростыми логическими и математичеcкими проблемами

На рисунке вы видите не слишком сложную транспортную сеть (сама схема и числовые значения в ней - просто пример). Расстояния между пунктами известны (показаны возле стрелок- путей). Коммивояжер (разъездной торговец) , выезжающий из пункта #1, должен посетить все пункты, имеющиеся в этой сети (#2,#3 и #4), и вернуться к исходному пункту #1.

В каком порядке коммивояжер должен посетить эти пункты?

Те кто сталкивался с подобными задачами в вузовском курсе математики или в популярных книгах, могут вспомнить, что эта задача похожа на задачу Эйлера по обходу кёнигсбергских мостов и относится при определенных условиях к нахождению, так называемых, гамильтоновых контуров в графе транспортной сети. Задача коммивояжера часто является таким образом задачей о нахождении некоторого минимального контура в заданном графе (схеме связей).
Однако, во многих учебниках по теории графов вы обнаружите примечания такого типа: не имеется достаточно-универсальных методов для нахождения конкретных контуров, являющихся решениями таких задач, а есть лишь критерии несуществования и методы оценок снизу (сверху) минимальной длины контура.
И это обычно является неожиданностью для тех, кто знакомится с этой темой: "ну как же!? В простых случаях контур такого объезда легко подбирается! Нужно только обобщить алгоритм подбора."

Чаще всего так реагируют специалисты по компьютерным методам и системам.
На самом деле к утверждению о сложности таких задач есть много веских оснований.
С ними мы и познакомимся, одновременно познакомившись с уже имеющимися в математике методами поиска таких решений.
Для начала все-таки найдите самый короткий маршрут объезда и найдите его длину!

Сколько же километров, по выбранному вами маршруту, проедет коммивояжер?

Настоящая WWW-страница создана 21 декабря 2010 г. This page is opened at 21 December 2010.

Адрес для переписки: Кафедра
Оставить для всех посетителей сайта комментарий или вопрос по тестам "что же дает математика"
Просмотреть комментарии к этой странице. В настоящее время 2 комментариев
Гостевая книга сайта "Естественно- математическое образование"

Комментарии

Уважаемый автор! Увидел, что у вас появилась новая задача и сразу решил изучить ее. Но Ваших замечаний о ее сложности не понял. Задача похожа на вашу "Транспортную сеть", варианты маршрутов быстро перечисляются: например, можно проложить маршрут через точки 1-2-3-4 и далее на 1.
Тогда с первым направлением 1-2 есть всего лишь один дополнительный вариант последующего передвижения: 1-2-4-3 и далее на 1. И так, ровно по два маршрута будет при выборе первоначального движения на точку 3, а также на точку 4.
То есть всего шесть маршрутов передвижения, а для ваших условий среди них будут четыре заведомо невыгодных из-за очень большого пути между т.2 и т.4 (или 4-2) длиной 16 км.

Что-то Ваш пример слишком простой? (12 января 2011, сообщение прислал Игорь, isis...@pochta.ru)

Уважаемый Игорь! Спасибо за подробный разбор логики перечисления и поиска ЧАСТИ маршрутов в этой задаче. Но маршрут 1-2-3-4-1 НЕ КРАТЧАЙШИЙ! (как и второй - в обратном направлении). Думаю, что ваши заметные комбинаторные навыки помогут вам найти правильный кратчайший маршрут самому.(А.Б.,14 января 2011)

Сайт управляется системой uCoz

Кольцо ИНК

This page:

От нашей игры "Стать миллионером?" и простой "задачи коммивояжера" шагните к задаче с непростыми логическими и математичеcкими проблемами

В каком порядке коммивояжер должен посетить эти пункты?

Сколько же километров, по выбранному вами маршруту, проедет коммивояжер?