Обработка "Матрица маршрута".
Разработана на платформе 1С:Предприятие 8.3 (8.3.12.1685). Управляемая форма.
Для использования необходимо сначала указать размер таблицы, в которой:
— заполняются города;
— на пересечении между городами — расстояние между ними;
В обработке при создании таблицы происходит демонстрационное заполнение. Город1, Город2 …. ГоронN.
Расстояние между ними заполняется с помощью генератора случайных чисел.
При использовании вы можете отключить эту часть кода, или настроить по своим потребностям.
После заполнения задаем маршрут: из какого Города в какой Город необходимо рассчитать кратчайшее расстояние.
При нажатии "Сформировать маршрут" — обработка формирует все возможные комбинации передвижения из пункта 1 в пунтк 2.
Если между какими то городами нет прямой дороги, тогда в таблице указывается значение "0". В этом случае такой маршрут исключается из возможных.
По диагонали таблица автоматически заполнена нолями, т.к. не имеет смысла перемещение из Города1 в Город1.
Для реализации расчета возможных маршрутов использован "Программный алгоритм составления перестановок, размещений и сочетаний"
Алгоритм представляет собой рекурсивную процедуру (т. е. процедуру, вызывающую саму себя с изменяющимися параметрами).
Полное описание механизма вы можете посмотреть на сайте:
Цибирова И.М. Программный алгоритм составления перестановок, размещений и сочетаний // Научный форум: Технические и физико-математические науки: сб. ст. по материалам XV междунар. науч.-практ. конф. — № 5(15). — М., Изд. «МЦНО», 2024. — С. 31-37.
Текст алгоритма, преобразованного в программный код 1С:
Sub CalcCombin(I As Integer, u As Integer)
Dim s As String, k As Integer, j As Integer
For k = u To N
If b(k) <> Empty Then
If i = M Then
c(i) = b(k)
s = ""
For j = 1 To M
s = s + c(j)
Next j
z = z + 1
znach(z) = s
Else
c(i) = b(k)
b(k) = Empty
If proverka = True Then
Call CalcCombin(i + 1, k + 1)
Else
Call CalcCombin(i + 1, 1)
End If
b(k) = c(i)
End If
End If
Next k
End Sub
Вот, пожалуй, и все. Возможно, кому-то будет полезна данная обработка.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Интересно, а как она будет работать если матрица будет, допустим, 500 на 500?
Круто! В какой конфигурации используете ?
(1)Я думаю будет очень долго работать, но разве есть такая необходимость? создавать маршрут из 500 населенных пунктов, добавить 10 ближайших городов и рассчитать, на практике наверное и меньше будет.
(2)Конфигурация не имеет значения, к объектам метаданных привязки нет, форма автономная.
(3)
Да речь не про города. Хотя даже с городами, например глобальный логистический план — т.е. классическая транспортная задача. Мне в практике довольно часто приходилось решать подобные задачи. Просто метод показался необычно «дорогим», поэтому поинтересовался ))
(5)Может подскажите как вы их решали? Я искал формулы, но ничего подобного не нашел, остается прокачивать железо)))
(6) Симплекс метод с различными модификациями в зависимости от планируемой нагрузки и задач. В быту использую сервис гугла
(7)
Спасибо, изучу этот метод, если разберусь, то модернизирую обработку.
к сожалению алгоритм работает полным перебором и, как следствие, имеет довольно узкий круг применения
есть еще момент: 1С вылетает (окно предприятия схлопывается не выдавая никаких ошибок) при уровне вложенности вызова ~2000
(9)
Во-первых, для данного алгоритма максимальная сложность n! (факториал)
Во-вторых, функция рекурсивная, а стек не резиновый
(9)Да, ограничение есть, какой размер матрицы вы тестировали?
Сейчас я изучаю «Симплекс метод», но из-за нагрузок на основной работе не хватает времени. Надеюсь в скором будущем усовершенствую функционал, будем «Сервису Googlе» конкуренцию создавать))))
(9)
Как-то мерил — 1748 был максимальный уровень вложенности на клиенте.
А алгоритм действительно весьма ущербный. Оптимизация тут или приводит к неточности, или к пожиранию памяти — за все нужно платить.