Транспортная задача 1С #762179

Добрый день, форумчане и с новым 2016 годом! Есть проблема за такой задачей. Существует регистр сведений такого вида: На самом деле РС конечно же очень большой, добавлено много складов. Требуется написать процедуру которая бы искала кратчайший путь от СкладА до СкладЯ. Я уже голову всю сломал, подскажите, пожалуйста, как это сделать. Спасибо.

Добрый день, форумчане и с новым 2016 годом! Есть проблема за такой задачей. Существует регистр сведений такого вида: На самом деле РС конечно же очень большой, добавлено много складов. Требуется написать процедуру которая бы искала кратчайший путь от СкладА до СкладЯ. Я уже голову всю сломал, подскажите, пожалуйста, как это сделать. Спасибо.

Добрый день, форумчане и с новым 2016 годом! Есть проблема за такой задачей. Существует регистр сведений такого вида: На самом деле РС конечно же очень большой, добавлено много складов. Требуется написать процедуру которая бы искала кратчайший путь от СкладА до СкладЯ. Я уже голову всю сломал, подскажите, пожалуйста, как это сделать. Спасибо.

Обходишь все возможные повороты от каждой точки. Строишь это в виде графа, хотя в некоторых случаях и дерево подойдёт. В каждом узле фиксируешь расстояние до предыдущих точек. Так-же фиксируешь все множества маршрутов до этого узла. В итоге потом надо будет просто обойти граф с поиском минимальный маршрут с учётом обхода всех складов. Как-то так. Я сейчас подобным на асме буду заниматься)))))

Как идея: построй матрицу по складам, в которой 1 есть путь со склада до склада, умножай её на саму себя и считай расстояние если в интересующем тебя складе есть 1. Типа граф связанности точек.

На ассемблере строить массивы и деревья?

Ну как бы можно обратиться к детям если есть в старших классах. Где то там начинают решать системы линейных уровнений.

Уже сижу на обёртке от фасма, которая совсем даёт другой уровень абстракции и ассемблерные вставки делаю только в критических моментах. А так да, для масма есть блок для работы с деревьями.

Линейное программирование. Исследование операций. Раздел Транспортная задача. Вам туда.

маленький вопрос: склад1, склад2, 1 означает, что склад2, склад1,1?

А вообще вот: Задача_о_кратчайшем_пути

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

Всем спсибо, буду пробовать.

не факт, но у ТС думаю да добавь сущность Маршруты - справочник реквизиты (СкладОткуда, СкладКуда, ПолноеРасстояние) ТЧ (СкладПромежуточный, Расстояние) затем заполни перебором всевозможные маршруты (без графов даже можно но долго будет перебирать) затем эти Маршруты подвяжи к новым записям в регистр свой

Задача - не транспортная, а поиска пути. Самое простое (но не самое быстрое) - алгоритм Флойда, три вложенных цикла. Определяет кратчайший путь между всеми парами складов. По матрице смежности - for k = 1 to n   for i = 1 to n     for j = 1 to n

табличка умножения это гениально

+ но что делать если Склад1 > Склад2 есть, а наоборот не возят?

+ а понял юзать вариацию алгоритма с

Нет. Хранить расстояния в матрице смежности, а использовать алгоритм Флойда. Четыре строчки, три вложенных цикла. Матрица достижимости - это не алгоритм.

да но алгоритм в ответ только число выдает - кратчайшее расстояние

Так же в три строчки определяется путь.

может быть но что то мне подумалось что в случае ТС лучше так как нужен не только кратчайший путь но меньшее число перегрузок (на вершинах - складах)

Алгоритм ли работает на дискретном поле! На клеточном например. Не вижу клеточного поля в задаче Тут самый быстрый - дейкстра. Но он сложнее в реализации, и куда спешить?

Кто мешает стоимость перегрузке прибавить к длине пути при формировании матрицы смежности?!

Всё, построили матрицу смежности. И каким образом учет стоимости перегрузки может зависеть от алгоритма поиска пути? Он совершенно одинаково учитывается в любом алгоритме.

не дискретном а планарном не факт что в планарное но если рейсы всегда только между 2 складами то можно структуру перевозок привести к планарной))

Дискретном. С клеточками. И зачем тебе это? Я не понимаю логики. Самый простой в реализации алгоритм - Флойда. Четыре строчки кода. Ты же начинаешь что-то выдумывать.

клеточки это только моделька, для упрощения это частный случай "волнового алгоритма"

+ суть можно работать сразу с исходной структурой-таблицей (СкладОткуда, СкладКуда, Расстояние) достаточно добавить еще одну колонку и начать в цикле рассылать волны из исходного склада

+ в алгоритме ли (на клеточках) очень легко определить соседей тут же придется на каждом шаге делать полный перебор всей таблицы с проверкой на условия - но при малом числе складов (<50) это вполне шустро

Я опять тебя не понимаю. Ты взял быстрый алгоритм, сделал так чтоб он стал медленным, и пытаешься им заменить самый простой из существующих алгоритмов? Зачем? Если писать быстрый алгоритм, например Дейкстру - то писать сразу нормально. Если нужен простой алгоритм, то проще Флойда алгоритма не существует.

реализация проще получается, нет никакой предварительной подготовки данных для Флойда нужно как минимум склады пронумеровать (т.е. сохранить куда то последовательность складов с номерами) и матрицу составить для Дейкстры нужно тоже что то изобретать для хранения графа и состояния обхода

Ты издеваешься? Я тебе подготовку данных выше написал - - это весь код формирования матрицы смежности.

+ "лучше день потерять потом за 5 минут долететь" - это не всегда верно т.е. если складов дофига, они никогда не меняются то да Флойд или Дейкстра если складов немного и иногда некоторые "не работают" то лучше волновой

Можешь скопировать в ветку работающий алгоритм ЛИ для случая ? Реализация ведь простая, проще +

Чем "волновой" лучше "Дейкстры"? В каких случаях волновой лучше Дейкстры?

блин... вот был "Склад 1" запускаем алгоритм, а в это время кто то перименовал его в "Склад 21" как понять что "Склад 1" из алгоритма это "Склад 21" из базы?

в данном случае не "алгоритм Ли", а просто "волновой алгоритм" и да реализация проще, у тебя только какие то непонятные переменные без понятия откуда они взялись из исходного регистра сведений

Дай ссылку на реализацию волнового алгоритма не "по сетке". На недискретном графе.

Ты издеваешься? Тебе выложить код который пронумерует склады?

Я не издеваюсь, а уточняю что реализация будет несколько сложнее и нужно предусмотреть варианты типа

+ фишка что мы меняем вершины (склады) с ребрами (путь между парами складов) местами и начинаем сразу волновой на исходных данных

Начинаем с самого начала. Волновой алгоритм не работает в случае задачи . Далее - алгоритм Флойда по сложности написания самый простой. Проще не бывает. Суммарно всё, вместе с нумерацией складов (например при помощи формирования списка складов - номер в списке это порядковый номер склада), с выдачей самого пути - это максимум строк 20 простейшего кода. Что у тебя первым пунктом? А теперь читай И при чем тут переименование складов? Каким образом в алгоритме фигурирует имя склада? Внимательно прочитай условие по ссылке которую ты дал - у тебя дискретный граф, и расстояние между каждой парой вершин равно единице!

В любом алгоритме придется пронумеровать вершины. И я не понимаю в чем проблема. Неужели так тяжело пронумеровать, например путем формирования списка складов?

> Внимательно прочитай условие по ссылке которую ты дал - у тебя дискретный граф, и расстояние между каждой парой вершин равно единице! перечитал, откуда взялось про дискретный граф не понял? "Дано: непyстой гpаф G=(V,E). " да волновой алгоритм решит не задачу "кратчайший путь", а задачу "меньшее число перевозок между складами/перевалок" лично я считаю что для логистики в плане оптимизации затрат (не времени доставки) это логичнее

Меньшее число перевалок  - это тоже самое что путь между двумя вершинами в графе равен единице. Каждое ребро - одна перевалка, то есть длина пути единица. Вот отсюда и берется дискретность графа. Давай вернемся к нашему разговору - где реализация волнового алгоритма для недискретного графа? Где решение задачи волновым алгоритмом?

блин... кто мешает заменить каждую пару (СкладN1, СкладN2, S) на нужное число пар "дискретных" ? но к задаче это уже не рассматриваем и тогда Флойд или Декстра ЗЫ и да ну как как получить из Флойда пусть в контексте исходных пар складов из регистра?

+ *путь получить (по складам) а не только расстояние общее пути

открываешь любую статью по флойду, и читаешь как получить  путь :) во второй матрице просто вместо расстояний хранишь путь, когда находишь новый кратчайший путь - складываешь пути из двух ячеек матрицы (ровно так-же как складываются длины путей)

Как сделать? Взять готовый алгоритм, реализующий транспортную задачу на Pascal и переделать на 1С.

for k = 1 to n   for i = 1 to n     for j = 1 to n Путь не содержит начальную и конечную вершину, содержит только промежуточные в порядке их обхода. Изначально Путь[][] по всей матрице равен пустой строке.

Повторюсь - это не транспортная задача, а задача поиска кратчайшего пути по графу.

Плиз проверьте кто нибудь...

+ да это волновой алгоритм (ищет маршрут минимальным числом перевозок между складами) а не Флойд (минимальное расстояние перевозки) за Флойдом это к NS ))

Твой код, даже если и работает, ищет не кратчайший маршрут, а первый попавшийся маршрут за минимальное число шагов (за минимальное количество промежуточных складов). Какой смысл его проверять?

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

Даже на первый взгляд - код соврешенно не рабочий, ибо нигде не запоминаются достижимые узлы на каждом шаге. И это что за комментарий? Ты пытаешься считать минимальное число перевалок, то есть расстояние между вершинами одинаково, то есть граф дискретный, считаешь "по клеточкам"

+ в смысле можно находить всевозможные маршруты, их в табличку, рассчитать общий путь для каждого и затем выбрать с минимальным путем

ыыы, а их и не нужно запоминать эти достижимые узлы, ибо вместо этого НомерВолны юзается ЗЫ потому и прошу проверить что на приведенном наборе пашет, а будет ли работать на разных хз

Сама суть волнового алгоритма - мы запоминаем вершины достижимые на каждом шаге. На следующем шаге из вершин достижимых на шаге n строим вершины достижимые на шаге n+1 Покажи строчку в твоем коде где запоминаются вершины достижимые на шаге n+1.... Волновой алгоритм аналогичен "алгоритму закраски в ширину"

любой не дискретный граф можно привести к дискретному виду достаточно выбрать подходящий "шаг дискретизации", понятно что в некоторых случаях НОДа нету и придется округлять

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

Не работает волновой алгоритм на любом графе приведенном к дискретному виду. Он вырождается в Дейкстру. Когда на каждом шаге строим путь из еще не обработанной вершины к которой текущий путь минимален.

Ты на вопрос не ответил. Где у тебя на каждом шаге запись в ТЗ?

ТекМаршрут.НомерВолны = НомерВолны + 1;

Где у тебя на каждом шаге запись в ТЗ вершин достижимых на данном шаге? НомерВолны - это не вершина.

+ эээ суть это "обратный волновой поиск" т.е. ищу с конца путь в начало, если нашли то просто по уменьшению чисел идем

+ не треба

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

ЦИКЛ   ДЛЯ каждой ячейки loc, помеченной числом d     пометить все соседние свободные непомеченные ячейки числом d + 1   КЦ   d := d + 1 ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны) Смотри внимательно третью строчку псевдокода. Любой волновой алгоритм требует запоминания (пометки) достигнутых вершин.

достигнутые вершины (пары маршрутов между складами) помечаются числами не достигнутые помечены -1

блин, так запустить то код а? добавить туда маршрутов и проверить? дык не знаю как оно себя будет вести если данные некорректны если есть маршруты (Склад1, Склад1) или кольцевые маршруты

Строчку укажи в твоем коде, где помечаются вершины.

см больше реально нигде нет записи в ТЗ для получения списка уже достигнутых "МаршрутыТекВолны = тзМаршруты.НайтиСтроки(Новый Структура("НомерВолны", НомерВолны));"

У тебя есть ТЗМаршруты, куда записаны ребра графа. У тебя даже структуры хранения пройденных (достигнутых) вершин нет.

Как-же ты их получаешь, если ты их не пишешь?

блин... можешь ответить оно вообще работает? не смотря на то что "не должно"

Как можно что-то получить из структуры данных, не записав туда?

Еще раз тебе говорю - конечно не работает. Волновой алгоритм выглядит совсем не так.

дык записываю в клеточки циферки, затем ищу клеточки с самой последней циферкой

ладно это не "волновой алгоритм"... скажи тогда как его назвать?

Ты обидишься, если я придумаю адекватное название неработающему алгоритму :)

Ты не в клеточки записываешь числа. Клеточки - это склады, вершины, а не ребра. А ты записываешь числа в ребра графа.

ну да в ребра пишу а что? какая разница ведь еще писал

И более того - даже эти записанные числа нигде не используешь. Создается структура в которой хранятся все склады. Далее пишешь по пунктам волнового алгоритма. Берешь начальную вершину, из которой строится путь, и во все достижимые из неё вершины пишешь единицу. Потом в цикле по номерам волны начиная с единицы ищешь вершины достижимые из вершин помеченных текущем номером волны, и если там ноль, то пишешь туда "номер текущей волны + 1" Можно проще - просто в начальную вершину записать единицу, а потом начать цикл по волнам начиная с единицы. Тогда число в вершине равно "длинепути + 1"

+ цель была наваять алгоритм без преобразования данных (исходный регистр + новая колонка) и без дополнительных структур

Разница такая, что ты написал нерабочий алгоритм.

зачем так сложно то? у нас ведь цель то не склады найти... а маршруты между складами зачем нам искать склады, а потом назад возвращаться из складов к маршрутам снова поиск делать?

Четыре ребра 1->2 2->3 3->4 4->5 Распиши по шагам как твой алгоритм найдет путь из "1" в "5"

почему на приведенном тестовом наборе оно зараза тогда работает?

Потому что есть путь в два шага. А у тебя только в два шага и умеет искать.

Для Каждого МаршрутТекВолны Из МаршрутыТекВолны Цикл У тебя два вложенных цикла, которые ищут маршрут в два шага. В три шага естественно такой код уже не найдет.

А религия не позволяет работать с яндекс или гугл апи?

Нашли решение! СкладОткуда|СкладКуда|НомерВолны Склад1|Склад2|3 Склад2|Склад3|2 Склад3|Склад4|1 Склад4|Склад5|0 Найденные маршруты: 1|Склад1|Склад2|1 2|Склад2|Склад3|1 3|Склад3|Склад4|1 4|Склад4|Склад5|1 Общая длина маршрутов = 4

А, хотя ты добавляешь каждый раз ребра в новую ТЗ. Да, тогда рабочий, но по сложности алгоритма - это не волновой алгоритм. то есть это испорченный волновой алгоритм.

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

ну пытался волновой упростить... получился вырожденный

Упростить? Волновой алгоритм - шесть строк кода. Как его можно упростить?