Поиск кратчайшего маршрута между городами в 1С
Добрый, день. Нужна помощь с заданием в учебной 1С. Есть два справочника "Города", в котором хранятся название городов. "Дороги", в котором хранятся данные города из которого выехали (ГородНачало, тип "Города") и город в которой приехали (ГородКонец, тип "Города"), а также данные расстояния между городами (тип число) в километрах. Нужно создать обработку, которая будет искать самый короткий путь между городами. В форме обработки должны быть реквизиты "ГородНачало", "ГородКонец" и "Расстояние". Например между городом А и Б есть две дороги в 5км и 10км. Нажав кнопку "найти кратчайший путь" в поле формы обработки "Расстояние" добавится число 5, так как это самый короткий путь. Заранее спасибо.
По теме из базы знаний
Ответы
Подписаться на ответы
Инфостарт бот
Сортировка:
Древо развёрнутое
Свернуть все
(2)
Данная задача больше похожа на задачу из ЕГЭ для школьников. Но там её чаще решают вручную.
Задача коммивояжёра
Думаю, что нет. Задача коммивояжёра, по моему - нахождение кратчайшего пути где будут все точки. В данной задаче просто минимальное расстояние между двумя. И таких одинаково минимальных и разных путей может быть несколько.
Данная задача больше похожа на задачу из ЕГЭ для школьников. Но там её чаще решают вручную.
Прикрепленные файлы:
(1) Повторюсь.
Кроме А, Б, Расстояние, можно и сам путь нарисовать. Он всё равно будет формироваться в процессе решения для исключения зацикленностей.
Решается рекурсией. Рекурсивным запросом тоже можно, но не в 1С, так как 1С не поддерживает рекурсивные запросы.
Кроме А, Б, Расстояние, можно и сам путь нарисовать. Он всё равно будет формироваться в процессе решения для исключения зацикленностей.
Решается рекурсией. Рекурсивным запросом тоже можно, но не в 1С, так как 1С не поддерживает рекурсивные запросы.
(1) Если не нужно путь искать между ГородНачало и ГородКонец, а только прямые дороги, то задача крайне простая.
Вся сложность в том, что дороги разнонаправленные и сначала надо все их преобразовать от меньшего города к большему или наоборот.
Пусть на входе у вас даны 4-ре дороги:
***************************************************
ГородНачало, ГородКонец, 23
ГородНачало, ГородКонец, 15
ГородКонец, ГородНачало, 10
ГородКонец, ГородНачало, 5
Сначала их преобразовать где в начале будет всегда один город, а в конце всегда второй. Например:
***************************************************
ГородНачало, ГородКонец, 23
ГородНачало, ГородКонец, 15
ГородНачало, ГородКонец, 10
ГородНачало, ГородКонец, 5
Далее простое условие, где город начало это город начало, а город конец это город конец. И минимум продолжительности дороги.
Все это делается простым запросом.
Города это справочник. В справочнике всегда один элемент больше другого по ссылке. Не важно какой какого. Параметр в запрос тоже можно передать как МИН(ГородНачало, ГородКонец) и МАХ(ГородНачало, ГородКонец). А можно условие в запросе чуть дописать. Тут дело вкуса. Задача учебная, поэтому не важно.
Вся сложность в том, что дороги разнонаправленные и сначала надо все их преобразовать от меньшего города к большему или наоборот.
Пусть на входе у вас даны 4-ре дороги:
***************************************************
ГородНачало, ГородКонец, 23
ГородНачало, ГородКонец, 15
ГородКонец, ГородНачало, 10
ГородКонец, ГородНачало, 5
Сначала их преобразовать где в начале будет всегда один город, а в конце всегда второй. Например:
***************************************************
ГородНачало, ГородКонец, 23
ГородНачало, ГородКонец, 15
ГородНачало, ГородКонец, 10
ГородНачало, ГородКонец, 5
Далее простое условие, где город начало это город начало, а город конец это город конец. И минимум продолжительности дороги.
Все это делается простым запросом.
Города это справочник. В справочнике всегда один элемент больше другого по ссылке. Не важно какой какого. Параметр в запрос тоже можно передать как МИН(ГородНачало, ГородКонец) и МАХ(ГородНачало, ГородКонец). А можно условие в запросе чуть дописать. Тут дело вкуса. Задача учебная, поэтому не важно.
(5)
Город Начало = Москва
Город Конец = Уральск
Есть дороги:
Москва - Петербург = 800 км
Москва - Владикавказ = 3000 км
Москва - Самара = 1100 км
Уральск - Самара = 500 км (хз по условию задачи графы однонаправленные или двунаправленные, будем исходить из того, что двунаправленные)
Петербург - Самара = 2000 км
Владикавказ - Уральск = 2500 км
Спойлер - прямой дороги нет.
Город Начало = Москва
Город Конец = Уральск
Есть дороги:
Москва - Петербург = 800 км
Москва - Владикавказ = 3000 км
Москва - Самара = 1100 км
Уральск - Самара = 500 км (хз по условию задачи графы однонаправленные или двунаправленные, будем исходить из того, что двунаправленные)
Петербург - Самара = 2000 км
Владикавказ - Уральск = 2500 км
Спойлер - прямой дороги нет.
Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот