Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте za4eti.ru

Экономика и Финансы Экономика и Финансы     Экономико-математическое моделирование Экономико-математическое моделирование

Решение задачи о коммивояжере

Карабин, 6x60 мм.
Размеры: 6x60 мм. Материал: металл. Упаковка: блистер.
42 руб
Раздел: Карабины для ошейников и поводков
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение
Ручка "Помада".
Шариковая ручка в виде тюбика помады. Красный цвет колпачка.
21 руб
Раздел: Оригинальные ручки

Аннотация Задача о коммивояжере состоит в том, чтобы объехать заданные города по одному разу в таком порядке, чтобы пройденное расстояние было минимальным. Такая задача актуальна во многих областях, таких как автомобильные, судовые и железнодорожные перевозки, расчет авиационных линий, конвейерное производство. ОглавлениеВведение Постановка задачи Метод решения Язык программирования Описание алгоритма Описание основных структур данных Описание интерфейса с пользователем Заключение Литература Текст программы Введение Задача состоит в том, чтобы коммивояжер (торговец) обошел все намеченные города единожды и в таком порядке, чтобы его путь был наименьшим. Эта задача заинтересовала меня потому, что её решение интересно с точки зрения программирования и составления алгоритма. Важно нахождение такого алгоритма, который позволит наиболее оптимально решить задачу. Сейчас решение данной задачи необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий. Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место. Постановка задачи Имеется городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения: маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение; в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды. Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице диагональ заполнена нулями). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат. Метод решения Для начала следует сказать, что в основе любого метода решения данной задачи лежит полный перебор всевозможных вариантов путей. Мы проходимся по каждому маршруту: одни отбрасываем, другие сравниваем с минимальным путем. В конце перебора мы получаем кратчайший путь. Особенностью этой задачи является то, что с увеличением количества городов растет общее число различных комбинаций прохождения пути. А вместе с тем растет и время расчета результата. Поэтому главным решением оптимизации алгоритма можно свести к тому, чтобы во время вычислений отбрасывать заведомо не минимальные пути. Необходимо задать такой критерий, который отсекал бы лишние ветви в дереве поиска кратчайшего пути. Для пояснения моего варианта решения задачи следует ввести несколько понятий. Промежуточную длину пути можно определить следующим образом: представим, что торговец выбрал какой-либо путь; он вышел из первого города и сейчас находится в каком-то городе i. Тогда все пройденное расстояние из начала в город i будем называть промежуточная длина пути.

Если исходить из того, что торговец в каждый момент времени будет находиться в каком-то i-ом городе, то всегда можно подсчитать какое расстояние он прошел из начала до этого города, то есть промежуточную длину пути. Минимальным путем будем называть маршрут, проходящий по всем городам и имеющий минимальную длину. Мой критерий строится на одном простом утверждении: если промежуточная длина пути больше минимального пути, тогда очевидно следующее: промежуточная длина будет расти, когда торговец будет двигаться к конечному городу, а значит длина всего пути будет больше длины минимального маршрута. следовательно такой маршрут можно отбросить. Пояснения показаны на рисунке 1. В данной программе используется следующий критерий: при переходе от одного города к другому рассчитывается промежуточная длина пути, и если она больше текущего минимального пути, то вычисления по данной ветви прекращаются. Таким образом, отсекаются лишние ветви. Решение данной задачи приводит к перебору возможных вариантов пути, но критерии такого рода могут значительно сократить вычисление и уменьшить время работы программы. Язык программирования Для написания программы был выбран язык Си по следующим причинам: Среда программирования Wi dows-приложений Microsof Visual C 6.0 позволяет в моей задаче наглядно отобразить карту городов и схему их соединения. Это один из языков, в котором я неплохо разбираюсь. Поэтому мне удобнее писать программу с помощью Visual C . Описание алгоритма В программе содержится рекурсивная функция, которая обеспечивает перебор возможных путей для поиска самого короткого. Именно здесь заключен алгоритм решения задачи «коммивояжера». Рассмотрим его подробнее: Для каждого города (i = от 1 до ), где мы еще не были. Допустим, что мы пришли в какой-то город i. Помечаем его, что мы здесь уже были. Подсчитываем длину пройденного пути. Если она больше чем длина минимального пути, Тогда нет смысла идти по этому пути дальше. помечаем город как не посещенный, выходим из города. Иначе, если мы в конце пути тогда, сравниваем с минимальным путем, если он меньше кратчайшего пути, тогда минимальный путь = кратчайший путь. иначе переходим к пункту 1. Переходим к следующему городу, где мы не были. Следует рассмотреть один из основных моментов алгоритма, связанных с перебором маршрутов. Из рисунка №2 можно проследить порядок формирования путей и рассмотреть на конкретном примере, как работает алгоритм. Здесь приведен пример для 4 городов. Остановимся на рисунке по подробнее. Мы начинаем путь из пункта 1. В нашем маршруте записан первый город. Рассматриваем те города, где мы не были: это 2, 3 и 4. Сначала переходим во второй. Добавляем к маршруту 2 город. Смотрим, можно ли куда-то перейти из второго города. Можно посетить третий и четвертый. Мы выбираем третий город. Ставим на третье место в нашем маршруте город 3. Далее мы смотрим, куда можно отправиться – в пункт 4. На четвертое место в маршруте ставим город 4. Здесь мы видим, что в нашем маршруте заполнены все четыре места и значит наш путь закончен. Сравниваем длину нашего пути с минимальным. Затем мы выходим назад из пункта 4 в пункт 3 и в маршруте перемещаемся на третье место.

Смотрим, что в городе 3 мы были, тогда берем следующий не посещенный город – четвертый. Ставим на третье место маршрута четвертый город. Из четвертого пункта можно посетить только третий. Пришли в третий пункт. Ставим на четвертое место маршрута город 3. Видим, что все четыре места в нашем пути заполнены и значит путь закончен. Сравниваем длину нашего пути с минимальным. Выходим назад – из пункта 3 в пункт 4 и в маршруте перемещаемся на третье место. Видим что здесь тоже нет не посещенных городов. Опять переходим на уровень вверх: из пункта 4 в пункт2 и в маршруте перемещаемся на второе место. В пункте 2 мы были, но остались не посещенными города 3 и 4. Переходим в третий. На второе место в маршруте записываем третий город. Отсюда можно попасть во второй и четвертый. Переходим во второй. На третье место в маршруте ставим второй город. И так далее. Из приведенного примера уже можно выделить, как алгоритм перебирает пути. Он действует по следующей схеме: Начальное значение j = 1 (первое место в маршруте). Мы находимся в городе k. Для каждого города (i = от 1 до ) Рассматриваем город i. Если этот город еще не посещен, тогда переходим в город i; j увеличиваем на единицу. Добавляем номер города в маршрут на место j. Помечаем город как посещенный. Переходим к пункту 1 (k = i). иначе идти некуда, т.е. все города мы посетили. если j = количеству городов ( ), т.е мы добрались до последнего пункта в маршруте и наш путь сформирован, тогда сравниваем длину пути с длиной минимального маршрута. Помечаем город как не посещенный и выходим из него. Уменьшаем j на единицу. Берем следующий город (i=i 1). Описание основных структур данных Теперь рассмотрим структуру приложения, опишем классы и процедуры, которые были изменены и наполнены кодом. Программа состоит из 4 классов: CAbou Dlg связан со встроенным диалоговым окном «О программе». CKurs Lipi App управляет запуском приложения и не связан с каким-либо диалоговым окном. CKurs Lipi Dlg связан с окном IDD KURS LIPI DIALOG. Этот класс организует постановку и решение задачи. CSe i g связан с окном IDD DIALOG1. В окне вводятся параметры к задаче – расстояния между городами. Класс CKurs Lipi Dlg. В начале при вызове функции O I i Dialog() переменные заполняются начальными данными. Затем из файла « able.i i» считывается таблица расстояний между городами. И теперь диалоговое окно готово к работе с пользователем. Функция O Pai () выводит на экран карту, позволяет выделять города, выбранные пользователем, а также соединяет города линиями-путями, когда задача решена. Кроме того, обеспечивается вывод информации для пользователя: пояснения, длина минимального пути и список расстояний между городами, составляющие минимальный путь. При нажатии левой кнопкой мыши вызывается функция O LBu o Dow (). Она определяет по какому городу щелкнул пользователь и ставит/снимает выделение с него. Также здесь осуществляется проверка на количество выделенных городов, т.к. время ожидания решения задачи для количества более 13 городов станет не удовлетворительным (от 1,5 минут и более). Поэтому программа выдаст сообщение, если мы попытаемся выйти за допустимые пределы.

Термин введен для характеристики учения Г. В. Лейбница о существующем мире как наилучшем из возможных. Противоположность оптимизма - пессимизм. ОПТИМИСТИЧЕСКАЯ ПЕЩЕРА - карстовая гипсовая трехэтажная пещера на западе Подольской возв., на Украине. Самая длинная в Европе (153 км). Озера. Туризм. ОПТИМУМ (от лат. optimum - наилучшее) - совокупность наиболее благоприятствующих условий; наилучший вариант решения задачи или путь достижения цели при данных условиях и ресурсах. Оптимум экономический в широком смысле - наиболее эффективное функционирование производства, в узком - наилучшее использование материальных ресурсов, при котором достигается возможный максимальный эффект производства или возможный минимум затрат. ОПТИНА ПУСТЫНЬ (Введенская) - мужской монастырь, в 2 км от г. Козельск. Основан в 14 в. Оптою (Макарием). Скит около монастыря (основан в 1821) посещали Н. В. Гоголь, Ф. М. Достоевский, Л. Н. Толстой. Закрыт после Октябрьской революции. В 1987 передан Русской православной церкви; восстанавливается. Архитектурные памятники 18-19 вв

1. Сетевое моделирование при планировании. Задача о коммивояжере...

2. Методы решения краевых задач, в том числе "жестких" краевых задач

3. Метод Галеркіна пошуку розв’язку лінійної крайової задачі

4. Исследование помехоустойчивого канала передачи данных методом имитационного моделирования на ЭВМ

5. Сущность и методы принятия управленческих решений

6. Расчет площади сложной фигуры с помощью метода имитационного моделирования
7. Методы численного моделирования МДП-структур
8. Методы принятия управленческого решения

9. Методы анализа управленческих решений

10. Методы поиска технических решений

11. Коллективные методы принятия управленческих решений

12. Метод Гаусса для решения систем линейных уравнений

13. Изучение методов принятия управленческих решений для конкретной проблемы

14. Методы принятия управленческих решений

15. Методы разработки управленческих решений

16. Исследование температурного поля наружного угла методом электрического моделирования

Шампунь детский "Natura Siberica" мягкий (для самых маленьких), 250 мл.
Мягкая формула шампуня "Natura Siberica" специально разработана для самых маленьких, он не раздражает глазки и носик при
333 руб
Раздел: Шампуни
Фоторамка С31-009 "Alparaisa" на 6 фотографий, 48x32 см (белый).
Размеры рамки: 48х32x2 cм. Размеры фото: - 15х10 см, 2 штуки, - 10х15 см, 2 штуки, - 9х9 см, 2 штуки. Фоторамка-коллаж для 6-ти
563 руб
Раздел: Мультирамки
Подушка "Verossa" (заменитель лебяжьего пуха), 70х70 см.
Одеяла и подушки торговой марки Verossa с инновационным наполнителем из микроволокна — искусственный лебяжий пух - обладают всеми
792 руб
Раздел: Размер 70х70 см

17. Метод экономического моделирования. Прогнозирование урожайности картофеля

18. Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

19. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

20. Решение задач - методы спуска

21. Задача коммивояжера

22. Решение задач линейной оптимизации симплекс – методом
23. Теория графов. Задача коммивояжера
24. Решение задач на построение сечений в многогранниках методом следов

25. Методы решения некорректно поставленных задач

26. Решение задач линейной оптимизации симплекс – методом

27. Решения смешанной задачи для уравнения гиперболического типа методом сеток

28. Обучение общим методам решения задач

29. Решение задачи методами линейного, целочисленного, нелинейного и динамического программирования.

30. Задача о коммивояжере

31. Задача о коммивояжере

32. Методы решения задач

Фоторамка "Poster silver" (50х60 см).
Рамка настенная может располагаться как вертикально, так и горизонтально. Для фотографий размером: 50х60 см. Материал: пластик.
791 руб
Раздел: Размер 50x60 и более
Книга-сейф "Морские приключения", 24x16x6 см.
Регулярно удалять пыль сухой, мягкой тканью. Материал: картон, металл. Кодовый замок. Товар не подлежит обязательной сертификации.
1010 руб
Раздел: Шкатулки сувенирные
Игровой набор "Мультифункциональный грузовик с мини-бульдозером и запчастями".
Игровой набор "Мультифункциональный грузовик" с целым чемоданом запасных частей станет отличным подарком любому мальчику.
1195 руб
Раздел: Самосвалы, грузовики

33. Математическое моделирование при решении экологических задач

34. Решение задач линейного программирования симплекс методом

35. Решение задач моделирования и оптимизации с помощью программ Excel и Mathcad

36. Решение прикладных задач методом дихотомии

37. Решение экономических задач программными методами

38. Графический метод решения задач линейного программирования
39. Использование моделирования в обучении решению задач в 5 классе
40. Метод Рунге-Кутты четвертого порядка с автоматическим выбором шага интегрирования решения задачи Коши

41. Методы решения логистических задач

42. Схематическое моделирование при обучении решению задач на движение (младшие школьники)

43. Эвристические методы решения творческих задач

44. Кислотно-каталитические процессы в нефтепереработке и в нефтехимии. Решение обратной задачи кинетики статистическими методами

45. Графический метод и симплекс-метод решения задач линейного программирования

46. Оптимизационные методы решения экономических задач

47. Решение задачи линейного программирования симплекс-методом

48. Решения задач линейного программирования геометрическим методом

Комод четырехсекционный "Элегант темный", 39x47x95 см.
Комод четырехсекционный пластиковый с декоративным покрытием. Материал: экологически чистый пластик, пищевой полипропилен, без запаха,
1450 руб
Раздел: Комоды
Фоторамка "Poster silver" (50х60 см).
Рамка настенная может располагаться как вертикально, так и горизонтально. Для фотографий размером: 50х60 см. Материал: пластик.
791 руб
Раздел: Размер 50x60 и более
Книга-сейф "Морские приключения", 24x16x6 см.
Регулярно удалять пыль сухой, мягкой тканью. Материал: картон, металл. Кодовый замок. Товар не подлежит обязательной сертификации.
1010 руб
Раздел: Шкатулки сувенирные

49. Творческие задачи и методы их решений

50. Методы решения транспортных задач

51. Решение задач по курсу "семейное право"

52. Задачи графических преобразований в приложениях моделирования с использованием ЭВМ

53. Формирование структуры электронного учебника и решение задач на ней

54. Решение математических задач в среде Excel
55. Организационный инструментарий управления проектами (сетевые матрицы, матрица разделения административных задач управления, информационно-технологическая модель)
56. СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

57. Решение задачи линейного программирования

58. Графы. решение практических задач с использованием графов (С++)

59. Новый метод «дополнительных краевых условий» Алексея Юрьевича Виноградова для краевых задач

60. Задача по травматологии с решением

61. Задачи, деятельность эксперта в системах моделирования

62. Решение обратных задач теплопроводности для элементов конструкций простой геометрической формы

63. Задачирешениями) по сопромату

64. Предмет, метод и задачи бухгалтерского учета (Контрольная)

Настольная игра "Лови мышей".
«Лови мышей!» - быстрая веселая семейная игра с простыми правилами. Игроки выступают в роли котов, которые хотят поймать как можно больше
567 руб
Раздел: Прочие
Картридж струйный "HP. F6V24AE (№652)", оригинальный, трехцветный для DJ Advantage 1115/2135/3635/3835/4535/4675,.
Цвет – цветной. Бренд поддерживаемых принтеров – Hewlett-Packard. Совместимость – оригинальный. Поддерживаемые модели – DJ Advantage
754 руб
Раздел: Картриджи для струйных принтеров
Подарочный сертификат My-shop.ru номиналом 1500 рублей.
Не знаете, что подарить? Предоставьте право выбора вашим друзьям и близким — подарите им Подарочный сертификат. Получатель сертификата
1500 руб
Раздел: Подарочные сертификаты

65. Задачи и методы планирования производства

66. Овладение методикой построения экономико-математических моделей, решение конкретных задач по стратегическому планированию и прогнозированию

67. Формулы для решения задач по экономике предприятия

68. Создание программных продуктов для решения задач

69. Решение транспортной задачи

70. К решению нелинейных вариационных задач
71. Решение задач по прикладной математике
72. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

73. О некоторых трудностях, возникающих при решении геометрических задач

74. Применение подобия к решению задач

75. Обучение решению математических задач с помощью графов

76. Новые представления о задачах и методах гипербарической медицины

77. Построения коллектива с акцентом на решение задач или на поддержание отношений в нем

78. Пример решения задачи по разделу «Переходные процессы»

79. Пример решения задачи по механике

80. Способ устойчивого решения неустойчивых задач и его алгоритм

Плакат "Пластилиновая азбука".
Уникальный электронный сенсорный плакат "Пластилиновая Азбука" разработан на основе обучающей методики Сергея и Екатерины
590 руб
Раздел: Электронные и звуковые плакаты
Набор "Парикмахер".
Набор будет прекрасным подарком для девочек, отлично подойдет для сюжетно-ролевых игр. Выполнен в виде саквояжа, который можно
652 руб
Раздел: Наборы "Парикмахер"
Подогреватель от USB.
Подогреватель для чашки с USB-подключением и разветвителем служит одновременно для сохранения тепла вашего напитка и для подключения
433 руб
Раздел: USB-устройства

81. Влияние использования схем, чертежей, иллюстраций на формирование ЗУН при обучении младших школьников решению задач на движение

82. Развитие логического мышления младших школьников при обучении построению вспомогательных моделей в процессе решения текстовых задач

83. Этапы решения мыслительной задачи

84. Структуризация и систематизация сюжетных задач по сложности их решения

85. От решения задач к механизмам трансляции деятельности

86. Нечеткая логика при решении криминологических задач
87. Дифференциальные уравнения движения точки. Решение задач динамики точки
88. Алгоритм решения обратной задачи вихретокового контроля (ВТК)

89. Электрофизиологические корреляты центральных программ при решении простых моторных задач у лиц с различным профилем асимметрии

90. Основные задачи термохимии. Использование калориметрических методов для определения теплот растворения солей

91. Решение задач по химии

92. Принятие проектных решений в задачах производственного и операционного менеджмента

93. Задачи по экономике с решениями

94. Анализ экономических задач симплексным методом

95. Решение многокритериальной задачи линейного програмирования

96. Постановка и разработка алгоритма решения задачи Учёт основных средств

Кастрюля со стеклянной крышкой, 2,2 л.
Объем: 2,2 л. Диаметр: 16 см. Глубина: 10,5 см. Толщина стенок: 0,5 мм. Кастрюля из высококачественной нержавеющей стали класса
598 руб
Раздел: До 3 литров
Рюкзак ортопедический мягкий «Marvel. Мстители».
Вместительный ортопедический рюкзак «Marvel» Мстители – это удобный помощник. Благодаря своей мягкой, но прочной конструкции, он имеет
3175 руб
Раздел: Без наполнения
Кружка суповая с мини теркой "Сад", 500 мл.
Кружка суповая с мини теркой. Объем: 500 мл. Материал: костяной фарфор, металл.
320 руб
Раздел: Супницы, бульонницы, суповые кружки

97. ГЕОСИСТЕМНОЕ прогнозирование: задачи, прогнозная информация, методы составления прогнозов

98. Концепция создания дополнительных геофизических модулей для контроля технологических параметров и решения геологических задач

99. Настройка и решение обратной петрофизической задачи


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.