Задача коммивояжера методом ветвей и границ в 1С

04.07.12

Разработка - Математика и алгоритмы

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
ЗадачаКоммивояджера
.epf 13,72Kb
58
58 Скачать (1 SM) Купить за 1 850 руб.

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

На закладке "Матрица расстояний" необходимо задать размерность, т.е. количество узлов маршрута и нажать кнопку "Создать структуру", в заполненной таблице необходимо заполнить прямые и обратные расстояния между пунктами, после чего нажать на кнопку "Решить", после расчета в строке сообщений будет выведен оптимальный маршрут (последовательность узлов).
Второй вариант - это несколько доработать справочник "Регионы" стандартной конфигурации "УТ", добавить 2 регвизита "Широта" и "Долгота", в которых заполнены географические координаты населенных пуктов. Я заполнял пользуясь shape-файлами, брал например здесь http://gis-lab.info/projects/osm-export.html , можно пользуясь сервисами API карт yandex или google. Тогда на закладке "Пункты" нужно заполнить список регионами, между которыми выполнять поиск, нажать кнопку "Создать матрицу" (таблица "Матрица расстояний" будет заполнена исходя из расстояний между координатами регионов на сфере), после этого нажать на кнопку "Решить", при этом на закладке "Пункты" будет отображено графическое представление пунктов и кратчайшего маршрута между ними.

См. также

Математика и алгоритмы Программист Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    2849    stopa85    12    

38

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    6999    user1959478    50    

36

Математика и алгоритмы Разное Платформа 1С v8.3 Конфигурации 1cv8 Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    2789    maksa2005    8    

26

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    10579    7    SpaceOfMyHead    18    

61

Математика и алгоритмы Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    4058    RustIG    9    

25

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

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

23.11.2022    3190    gzharkoj    14    

25

Математика и алгоритмы Программист Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    8985    7    kalyaka    11    

44
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. Angeros 05.07.12 08:48 Сейчас в теме
Списибо, давно искал, самому было лень вспоминать :)
2. Angeros 05.07.12 08:53 Сейчас в теме
А что со скрин шотами? какойто новомодный дэзайн?
3. MarcoPolo3 50 05.07.12 11:25 Сейчас в теме
(2) Angeros, а что не так со скриншотами?
4. automatizator 170 11.07.12 02:44 Сейчас в теме
Осталось объединить например с infostart.ru/public/142306 и написать обработку для оптимизации развоза товара для УТ, или планирования маршрута торгпредов!

Кому не слабо?
5. putin-vv 11.07.12 09:53 Сейчас в теме
(4) automatizator, дело за малым - сколько заказчик готов за это заплатить
6. catena 110 16.07.12 11:40 Сейчас в теме
(4)Вряд ли получится. Для того, чтобы вышел толк, надо к длине пути добавлять еще вес загруженности и альтернативные маршруты - иначе в любом более менее большом городе это планирование маршрутов накроется медным тазом.
7. philya 77 07.05.13 10:20 Сейчас в теме
Проверить работоспособность не удалось. На трех точках с матрицей

0 1 1
1 0 1
1 1 0

пишет "все плохо. идите вон"

{ВнешняяОбработка.ЗадачаКоммивояджера.МодульОбъекта(128)}: Операции сравнения на больше-меньше допустимы только для значений совпадающих примитивных типов (Булево, Число, Строка, Дата)
Если НовыйУзел.Оценка < ДеревоРешений.Оценка Тогда
8. Aleksey81 1184 27.01.14 15:32 Сейчас в теме
Пишет все плохо!!!
{ВнешняяОбработка.ЗадачаКоммивояджера.МодульОбъекта(128)}: Операции сравнения на больше-меньше допустимы только для значений совпадающих примитивных типов (Булево, Число, Строка, Дата)
Если НовыйУзел.Оценка < ДеревоРешений.Оценка Тогда
Явная ошибка в алгоритме!!!
Оставьте свое сообщение