Добрый день, форумчане и с новым 2016 годом!

Есть проблема за такой задачей. Существует регистр сведений такого вида:

СклОткуда, СклКуда, РасстояниеКм
Склад1, Склад2, 1
Склад1, Склад3, 2
Склад1, Склад4, 3
Склад3, Склад2, 4
Склад4, Склад3, 5
Склад4, Склад5, 6

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

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

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

Типа граф связанности точек.

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

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

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

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

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

А вообще вот: https://ru.m.wikipedia.org/wiki/Задача_о_кратчайшем_пути

Вот статья: http://catalog.mista.ru/public/271270/ . Она называется "Определение кратчайших путей, критических путей одним запросом" . К статье прилагается работающая обработка. В частности, обработка позволяет находить кратчайшие пути по схеме метро. Думаю, и со складами проблем не будет.

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

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

(7) не факт, но у ТС думаю да

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

затем заполни перебором всевозможные маршруты (без графов даже можно но долго будет перебирать)

затем эти Маршруты подвяжи к новым записям в регистр свой

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

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

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

(14)+ а понял юзать вариацию алгоритма с https://ru.wikipedia.org/wiki/Матрица_достижимости

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

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

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

(18) может быть

но что то мне подумалось что в случае ТС лучше https://ru.wikipedia.org/wiki/Алгоритм_Ли

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

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

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

Для а=1 по количествопутей цикл
Длинапути = путь[а].ДлинаПути+стоимостьперегрузки; // прибавили стоимость перегрузки
W[путь[а].Откуда,путь[а].Куда]=Длинапути;
КонецЦикла;

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

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

то можно структуру перевозок привести к планарной))

https://ru.wikipedia.org/wiki/Теория_графов

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

(25) клеточки это только моделька, для упрощения

https://ru.wikipedia.org/wiki/Алгоритм_Ли это частный случай "волнового алгоритма" https://ru.wikipedia.org/wiki/Поиск_в_ширину

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

достаточно добавить еще одну колонку и начать в цикле рассылать волны из исходного склада

(27)+ в алгоритме ли (на клеточках) очень легко определить соседей

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

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

(29) реализация проще получается, нет никакой предварительной подготовки данных

для Флойда нужно как минимум склады пронумеровать (т.е. сохранить куда то последовательность складов с номерами) и матрицу составить

для Дейкстры нужно тоже что то изобретать для хранения графа и состояния обхода

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

(30)+ "лучше день потерять потом за 5 минут долететь" - это не всегда верно

т.е. если складов дофига, они никогда не меняются то да Флойд или Дейкстра

если складов немного и иногда некоторые "не работают" то лучше волновой

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

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

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

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

(33) в данном случае не "алгоритм Ли", а просто "волновой алгоритм"

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

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

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

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

(37) http://algolist.manual.ru/maths/graphs/shortpath/wave.php

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

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

(39) Что у тебя первым пунктом? А теперь читай (30) (35)
И при чем тут переименование складов? Каким образом в алгоритме фигурирует имя склада?

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

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

(41) >(39) Внимательно прочитай условие по ссылке которую ты дал - у тебя дискретный граф, и расстояние между каждой парой вершин равно единице!

перечитал, откуда взялось про дискретный граф не понял?
"Дано: непyстой гpаф G=(V,E). "

да волновой алгоритм решит не задачу (0) "кратчайший путь", а задачу "меньшее число перевозок между складами/перевалок"

лично я считаю что для логистики в плане оптимизации затрат (не времени доставки) это логичнее

(43) Меньшее число перевалок  - это тоже самое что путь между двумя вершинами в графе равен единице. Каждое ребро - одна перевалка, то есть длина пути единица. Вот отсюда и берется дискретность графа.

Давай вернемся к нашему разговору - где реализация волнового алгоритма для недискретного графа? Где решение задачи (0) волновым алгоритмом?

(44) блин... кто мешает заменить каждую пару (СкладN1, СкладN2, S) на нужное число пар "дискретных" ?

но к задаче это уже не рассматриваем и тогда Флойд или Декстра

ЗЫ и да ну как как получить из Флойда пусть в контексте исходных пар складов из регистра?

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

https://ru.wikipedia.org/wiki/Задача_коммивояжёра

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

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

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

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

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


&НаСервере
Процедура Показать(тзДанные);
    Сообщить("СкладОткуда|СкладКуда|НомерВолны");
    Для Каждого ТекСтр Из тзДанные Цикл
        Сообщить(""+ТекСтр.СкладОткуда+"|"+ТекСтр.СкладКуда+"|"+ТекСтр.НомерВолны);        
    КонецЦикла;
    Сообщить("");
КонецПроцедуры    

&НаСервере
Процедура ДобавитьЗапись(лтзМаршруты, лСкладОткуда, лСкладКуда, лРасстояние)
    НовСтр = лтзМаршруты.Добавить();
    НовСтр.СкладОткуда = лСкладОткуда;
    НовСтр.СкладКуда = лСкладКуда;
    НовСтр.Расстояние = лРасстояние;
КонецПроцедуры    

&НаСервере
Процедура РасчетМаршрута()
    
    //Подготовка данных
    тзМаршруты = Новый ТаблицаЗначений;
    тзМаршруты.Колонки.Добавить("СкладОткуда");
    тзМаршруты.Колонки.Добавить("СкладКуда");
    тзМаршруты.Колонки.Добавить("Расстояние");
    
    ДобавитьЗапись(тзМаршруты, "Склад1", "Склад2", 1);
    ДобавитьЗапись(тзМаршруты, "Склад1", "Склад3", 2);
    ДобавитьЗапись(тзМаршруты, "Склад1", "Склад4", 3);
    ДобавитьЗапись(тзМаршруты, "Склад3", "Склад2", 4);
    ДобавитьЗапись(тзМаршруты, "Склад4", "Склад3", 5);
    ДобавитьЗапись(тзМаршруты, "Склад4", "Склад5", 6);
    
    тзМаршруты.Колонки.Добавить("НомерВолны");
    тзМаршруты.ЗаполнитьЗначения(-1, "НомерВолны");
    
    // Задаем начальный и конечный склады
    СкладОткуда = "Склад1";
    СкладКуда = "Склад5";
    
    // Установка начального
    НомерВолны = 0;
    Для Каждого ТекМаршрут Из тзМаршруты Цикл
        Если ТекМаршрут.СкладКуда = СкладКуда Тогда
            ТекМаршрут.НомерВолны = НомерВолны;
        КонецЕсли;
    КонецЦикла;
    НашлиРешение = Ложь;
    
    // Пошли делать волны
    Пока Не НашлиРешение Цикл
        МаршрутыТекВолны = тзМаршруты.НайтиСтроки(Новый Структура("НомерВолны", НомерВолны));
        Если МаршрутыТекВолны.Количество()=0 Тогда
            Сообщить("Решения нет!");
            Прервать;
        КонецЕсли;
        
        Для Каждого МаршрутТекВолны Из МаршрутыТекВолны Цикл
            //Сообщить("Обработка волны № "+НомерВолны);
            ТекСклад = МаршрутТекВолны.СкладОткуда;
            
            Для Каждого ТекМаршрут Из тзМаршруты Цикл
                Если ТекМаршрут.СкладКуда = ТекСклад Тогда
                    //Сообщить("Нашли следующий склад");
                    ТекМаршрут.НомерВолны = НомерВолны + 1;
                    Если ТекМаршрут.СкладОткуда = СкладОткуда Тогда
                        НашлиРешение = Истина;
                    КонецЕсли;
                КонецЕсли;
            КонецЦикла;
            
        КонецЦикла;
        
        Если НашлиРешение Тогда
            Сообщить("Нашли решение!");
            Прервать;
        КонецЕсли;
        
        НомерВолны = НомерВолны + 1;
    КонецЦикла;
    
    // Вывод "заполненных клеточек" NS не верил что можно волновой "не на клеточках"
    Показать(тзМаршруты);
    
    // Строим маршрут и выводим
    Если НашлиРешение Тогда
        Сообщить("Найденные маршруты:");
        тзМаршруты.Сортировать("НомерВолны Убыв");
                
        НомерВолны = тзМаршруты[0].НомерВолны;
        НомерМаршрута = 0;
        ОбщаяДлинаМаршрутов = 0;
        
        Для Каждого ТекМаршрут Из тзМаршруты Цикл
            Если (НомерВолны>=0) И (ТекМаршрут.НомерВолны = НомерВолны) Тогда
                НомерМаршрута = НомерМаршрута + 1;
                ОбщаяДлинаМаршрутов = ОбщаяДлинаМаршрутов + ТекМаршрут.Расстояние;
                Сообщить(""+НомерМаршрута+"|"+ТекМаршрут.СкладОткуда+"|"+ТекМаршрут.СкладКуда+"|"+ТекМаршрут.Расстояние);
                НомерВолны = НомерВолны - 1;
            КонецЕСли;
        КонецЦикла;
        
        Сообщить("Общая длина маршрутов = "+ОбщаяДлинаМаршрутов);
    КонецЕсли;
КонецПроцедуры

&НаКлиенте
Процедура Команда1(Команда)
    РасчетМаршрута();
    
КонецПроцедуры



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

за Флойдом это к NS ))

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

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

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

// Вывод "заполненных клеточек" NS не верил что можно волновой "не на клеточках"

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

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

(56) ыыы, а их и не нужно запоминать эти достижимые узлы, ибо вместо этого НомерВолны юзается

ЗЫ потому и прошу проверить что на приведенном наборе пашет, а будет ли работать на разных хз

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

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

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

это модификация волнового для ТЗ

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

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

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

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

(64)+ эээ суть это "обратный волновой поиск"

т.е. ищу с конца путь в начало, если нашли то просто по уменьшению чисел идем

(65)+ не треба

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

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


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

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

(68) блин, так запустить то код а?
добавить туда маршрутов и проверить?

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

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

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

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

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

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

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

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

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

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

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

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

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

И более того - даже эти записанные числа нигде не используешь.

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

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

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

(84) зачем так сложно то?
у нас ведь цель то не склады найти... а маршруты между складами


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

(85)
Четыре ребра
1->2
2->3
3->4
4->5

Распиши по шагам как твой алгоритм найдет путь из "1" в "5"

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

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

Для Каждого МаршрутТекВолны Из МаршрутыТекВолны Цикл
            //Сообщить("Обработка волны № "+НомерВолны);

            ТекСклад = МаршрутТекВолны.СкладОткуда;
            
            Для Каждого ТекМаршрут Из тзМаршруты Цикл

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

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

(88)

Нашли решение!
СкладОткуда|СкладКуда|НомерВолны
Склад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

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

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

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

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

(97) нифига там не 6 строк, если учесть подготовку данных и потом выдирание пути

плюс требуется отдельная переменная (у меня она осталась) и два списка вершин (СтарыеВершины и НовыеВершины)

(98)+ пытался через Склады решать а не через сразу Маршруты так очень неудобно на 1С получается

(98)
1. В волновом алгоритме мы должны знать уже пройденные вершины. Причем доступ к ним должен быть за О(1) - то есть это в обязательном порядке массив вершин.
Список вершин текущей волны легко можно получить очередью либо стеком. Так-же с доступом за О(1) - это тоже всего один массив.
То есть для правильной реализации алгоритма необходимо и достаточно два вспомогательных массива. В одном хранятся уже пройденные вершины с длиной пути до них, во втором список вершин текущей волны.

(100) правильно нужно еще два массива (ТЗ или СЗ)
мне удалось обойтись без них
да получил замедление алгоритма это естественно

Легко доказывается что в волновом алгоритме каждое ребро рассматривается только один раз, и каждая вершина рассматривается только один раз. То есть сложность алгоритма при правильной реализации O(E+N), где Е число ребер, N - число вершин.
Но при этом возникают условия - проверка что вершину уже проходили О(1) (массив). получение и добавление вершины в список волн О(1) (массив). Получение очередного ребра из данной вершины О(1) (массив).
(101) Ты в цикле создаешь новую ТЗ на каждую волну. Вместо двух ты их создаешь количеством равным количеству волн. Причем каждый раз пишешь кучу ненужной информации (там должен быть только склад, вершина. Всё.). При этом ты повторно проходишь одни и те-же вершины. Чего не должно быть.

При этом самое главное - волновой алгоритм не в состоянии решить задачу (0). А решает совершенно другую, в данном случае ненужную задачу.

(102) да с этим полностью согласен, получилось O(N*N)

(103) а вот это неправда!
волновой алгоритм для (0) см (57)

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

да сложность уже O(N*N+N)

(105) Можно еще раз?
1->3 100
1->2 1
2->3 1
Правильное решение задачи (0) 1->2->3
Волновой алгоритм выдаст 1->3
Волновой алгоритм работает только на дискретных графах. Сколько можно по кругу об одном и том-же?

(106) волновой алгоритм может выдать "всевозможные пути" а не только "с самым меньшим числом волн (шагов)"

достаточно его не останавливать а довести до конца

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

(107)+ но сложность еще возрастает и нет смысла, да тогда проще Флойд или Дейкстра

(107) ?!?
Все возможные пути - это полный перебор. Это вообще не алгоритм. Он у тебя на двадцати вершинах путь не выдаст.
И полный перебор - это не волновой алгоритм.
Модификация волнового алгоритма работающая на любых графах без дуг отрицательного веса - называется алгоритмом Дейкстры. И заметно отличается от волнового алгоритма по реализации, ибо нужен быстрый способ получения вершины с минимальным индексом.
Волновой алгоритм за О(N*N)- Это не волновой алгоритм. Это бессмысленный алгоритм. Ибо волновой алгоритм просматривает пути из каждой вершины только один раз - это следует из его определения, помечая потом вершину как пройденную.

(109) да полный перебор волновым методом для сокращения числа вариантов
т.е. заранее отсекаются невозможные и не рассматриваем повторно уже пройденные

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

экономия памяти за счет вычислительных ресурсов

(110)+ еще вопрос что быстрее память или проц+память при последовательном чтении

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

(111) ?!?
(110) Полный перебор - это полный перебор. Волновой алгоритм - это волновой алгоритм. Реализация и волнового алгоритма, и полного перебора - сложнее реализации метода Флойда.

(112) блин машина тьюринга или память только стример с перемоткой кассеты

если метод Флойда проще то плиз реализуй на тех же исходных данных и с таким же выводом... а потом посчитаем полученное число строк кода ))

(106) кста можно шаг 1->3 100 заменить на 100 шагов
1->1.1
1.1->1.2
...
1.99->3 и после запуска моего "испорченного волнового" получить искомый короткий 1->2->3

(113) Ты 1С запустил на машине Тьюринга?

(114)+ понятно что это изврат

(115) причем тут 1С ?

(116) Современная алгоритмика, сложность алгоритмов - расписывается для архитектуры фон Неймана. В которой доступ к памяти - О(1). Константа. Независимо от порядка доступа.

А задача в (0) Для 1С. 1С запускается только на архитектуре фон Неймана. И доступ к памяти (массив) всегда О(1) - независимо от порядка доступа. Последовательный или случайный - неважно.

(117) не надо путать... фон Неймановская архитектура никак не стандартизирует память

это просто черный ящик

технически еще на спектруме когда не хватало оперативки (16 кб) юзал при работе проги ленту (600 кб)

да 1С на спектруме не запустить (можно но ждать надоест загрузки и сначала нужно какой то эмулятор с памятью придумать откуда взять) но кто сказал что спектрум не фон Нейман?

(0)(51) А! Тогда старый добрый метод решения подобных задач https://ru.wikipedia.org/wiki/Алгоритм_Беллмана_—_Форда .

(119) стандартизирует. прочитай внимательно определение.

(121) прочитал... про время доступа там ничего нет

(122) "Принцип адресности"

(123) не понял причем тут принцип адресности и как он связан со времен последовательного и произвольного доступа?

да вся память адресуется и на ленте/диске (стример/кассета/fdd/hdd) в т.ч.

но вот время то разное!

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

(124) Кассета не подходит под определение памяти фон-Неймана. Ну никак.

(120) хороший алгоритм но вот память кушает не по детски

к примеру у нас ардуинка и нужно найти путь среди 10 000 маршрутов, время поиска пути неважно

(126) эээ? каким таким образом она не подходит то?

(128)+ https://ru.wikipedia.org/wiki/Архитектура_фон_Неймана
где противоречие?

(128) Нигде не подходит. Для примера какой процессор умеет выполнять команды с ленты? В каком месте у ленты прямая адресация? Лента подходит под машину Тьюринга, а никак не под архитектуру фон Неймана.

фон Неймановская память - только ОЗУ. Возможно с кешем.

(130) мда... любой процессор можно научить выполнять команды с ленты
банальный пример http://zx-info.ru/?rc=12&id=5

(131) пошел какой то спор ради спора... может все таки определение памяти по фон Нейману и какому пункту этого определения не удовлетворяет лента?

(132)+
лента разделенная на ячейки - для доступа к ячейке нужно сначала перемотать ленту, последовательные ячейки читаются быстро, перемотка занимает время

или

линейная "память" разделенная на ячейки - время чтения любой ячейки одинаково

(131) есть вспомнил! EMS/XMS память ))

https://ru.wikipedia.org/wiki/Расширенная_память
https://ru.wikipedia.org/wiki/Дополнительная_память

не фон Нейман да ))

(134) Ну сколько можно? Прекрати уже.
http://arch.cs.msu.su/Text/Chapter_02.pdf
Принцип линейности и однородности памяти.

Память машины Фон Неймана – это линейная
(упорядоченная) и однородная последовательность некоторых элементов, называемых ячейками. В
любую ячейку памяти другие устройства машины (по толстым стрелкам на схеме рис. 2.1) могут за-
писать и считать информацию, причем время чтения из любой ячейки одинаково для всех ячеек па-
мяти. Время записи в любую ячейку тоже одинаково (это и есть принцип однородности памяти).

(135) +
"Разумеется, время чтения из ячейки памяти может не совпадать со временем записи в не?. Такая па-
мять в современных компьютерах называется памятью с произвольным доступом (Random Access
Memory – RAM). На практике современные ЭВМ могут иметь участки памяти разных видов. Напри-
мер, некоторые области памяти поддерживают только чтение информации (по-английски эта память
называется Read Only Memory – ROM), данные в такую память записываются один раз при изготов-
лении этой памяти. Другие области памяти могут допускать запись, но за б?льшее время, чем в
обычную память (это так называемая полупостоянная память, такой памятью комплектуются попу-
лярные в настоящее время карты флэш-памяти) и др"

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

сейчас при нехватки памяти ОС начинает свопить на HDD/SSD
т.е. или современные компы это не фон Нейман?

тогда про выполнение алгоритмов на каких машинах мы говорим?

или все таки даже своп (swap) это фон Нейман ?

Беспредметный спор. Если страница памяти выгружена в своп файл, то соответственно время доступа будет определяться временем доступа к диску, а там куча своих нюансов: очередь к диску, попали ли в кэш, как далеко находится считывающая головка от сектора на диске и т.д. Другой момент, ячейка в памяти может находиться в кэше (1, 2, 3, 4 уровень), соответственно и время доступа и время считывания будет меньше. Так же нужно понимать, что если следовать только архитектуре Неймана, получается мы должны будем ограничиться только трехадресными командами: адрес первого, второго операнда, и адрес, куда мы пишем результат. Между тем в процессорах с незапамятных времен используются регистры, для ускорения вычислений без использования медленной общей памяти. Сейчас еще сложнее дело обстоит за счет суперскалярности, предварительным считыванием, предварительным выполнением команд. Это все не отменяет базовых принципов архитектуры Неймана, но есть разная память и процессор имеет разные инструменты для работы с этой памятью.

(137) так и пытаюсь добиться справедливости ))

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

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

Через какое время у тебя остановится счет на таком наборе данных
1->2
2->1
3->4
4->3
Найти путь 1->4

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

И сложность твоего алгоритма не О(N^2), а намного хуже.

(140) даже тестить не буду... может лучше свои продвигаемые протестишь на таком?

(141) сам алгоритм волны О(N^2), если без построения пути
еще построение пути O(N) поэтому и писал уже что сложность O(N^2+N)

У тебя Е- количество ребер. На каждом шаге утебя два вложенных цикла по всем ребрам. То есть сложность только каждого шага О(E^2), или иначе на графах близких к полным - каждый шаг алгоритма О(N^4).  и это поиск пути только между одной парой вершин.
Флойд ищет пути между всеми парами вершин за О(N^3). Где Е-количество ребер. N - количество вершин.

(142) Конечно не будешь тестить, так как твой алгоритм не выдаст правильного результата - что пути нет. Любой нормальный алгоритм такой результат выдаст.

(142) Та на полном серьезе считаешь общеизвестные алгоритмы неработающими?

(145) Да я на полном серьезе считаю что "общеизвестные алгоритмы" без напильника на реальных данных нерабочие.
Как только выходим за рамки академической задачи и требуются дополнительные данные или условия получить.

(146)+ пока что мы сравниваем "рабочий алгоритм" с некими сферическими...

(143) когда оценивают сложность алгоритма по вершинам (N) не учитывая количество ребер (E) это немного странно?

допустим есть полносвязный граф (каждая вершина соединена с ребрами с каждой) какая будет сложность для Флойда?
учитывая что матрицу предварительно чтобы построить что нужно? O(N^2)

(146) Какой напильник? Какие дополнительные данные?
Задача совершенно четко сформулирована. Есть граф, есть длины ребер, найти путь с наименьшей длиной. Всё. В этой задаче не бывает дополнительных условий.

(149) условие задачи четко оговорено в (0)...
никаких графов я там не наблюдаю

(148) Никогда. Посмотри выше оценку нормально работающего волнового - О(N+E)
Сложность Флойда совсем не зависит от количества ребер. Там три вложенных цикла по вершинам, поэтому и сложность О(N^3)Учитывая что в связном графе число ребер всегда не меньше чем N-1. Можно сказать что сложность Флойда лежит в пределах
от О(Е^1.5) до О(E^3)

У тебя сложность каждого шага не зависит от количества вершин, а зависит только от количества Ребер. То есть сложность каждого шага О(E^2). В тех случаях когда твой алгоритм работает, то есть когда есть путь. Так как путь не длиннее N-1, то полная  сложность твоего алгоритма О(N*E^2) - что полный алес.
Ну и нормальный алгоритм должен в случае отсутствия пути выдавать что пути нет. А не считать бесконечно.

(150) Ладно, завязываем этот разговор.

(151) согласен, можно оптимизировать мой алгоритм вместо полного перебора всех ребер (маршрутов) на поиск с нужной вершиной (СкладОткуда)

(152) предлагаю для условия когда расстояние между любой парой складов =1 (в этом случае теоретически алгоритмы должны выдавать одинаковый маршрут) устроить соревнование алгоритмов

(153) какое соревнование? Сложность всех алгоритмов известна.
Нужны соревнования по алгоритмике - http://codeforces.com/

Результатом работы алгоритма будет стандартный набор двух-трех базовых маршрутов. Так как любые другие маршруты не будут соответствовать оптимуму...
Как в той шутке: -А давайте уволим тех, кто работает хуже среднего уровня в компании!

(154) к сожалению (или к счастью) в "соревнованиях по алгоритмике" задачи (требования, условия) на ходу не меняются

как это в реальной практике обычное дело, особенно в применении 1С для целей "автоматизации хаоса"

(155) обычно так и делают с одновременным набором новых сотрудников (предполагается что они выше среднего уровня)

(157) И через пару месяцев уровень общий ещё хуже)))

(0) слишком просто
в реале вместо расстояний используют время движения между точками, еще д.б. ограничения по вместимости автомобилей, время работы складов (9.00-18.00 или 0.00-24.00)

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

(156) Тут задача с четкими условиями. Любые корректировки делаются корректировкой расстояния. То есть решается чистым решением задачи о кратчайшем пути по графу. Остальное уже настройки длин пути.
И нужен нормальный метод решения. Быстрый и легко реализуемый. И не подвисающий на некорректных условиях.
У нас например по складу сборщики ходят почти оптимальными маршрутами, только задача более сложная - задача коммивояжера. И никаких дополнительных условий естественно нет и не должно быть. И эти маршруты здорово повысили эффективность работы сборщиков.

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

(127) Если описывать граф из 10000 складов 2-мерным массивом, в случае когда каждый из складов связан только с 2-мя или 3-мя другими складами, то согласен. Это нерациональный расход памяти по определению теории алгоритмов - отъедание памяти будет увеличиваться пропорционально квадрату количества складов. Проблему можно обойти, если использовать соответствия или структуры. С их помощью можно компактно уместить описание такого графа в памяти компьютера.

(162) Если 10000 складов, то решения в любом случае не дождешься (10000^3 операций, 10^12). Но таких компаний в России нет.
И нужно сразу решить - нужны один раз рассчитанные все пути, или нужно каждый раз рассчитывать на лету путь между двумя складами. Навигаторы например рассчитывают "на лету" путь между двумя заданными точками. У меня структура склада не меняется, пробок на складе не бывает, поэтому всё рассчитано один раз, и длина пути просто берется из структуры хранения.

Книга знаний: Решение транспортной задачи в 1С:Предприятие 8.2

(164) это называется пришел romix и все опошлил ))

только вот не совсем в тему (0) хотя и в тему темы

(163) >Но таких компаний в России нет.

41 901 отделение почтовой связи.
https://ru.wikipedia.org/wiki/Почта_России

(166)+ и ведь как то решают эту задачу )) причем из произвольного отделения в произвольное через центры обработки
понятно что задача упрощена небольшим кол-во этих центров

(166) А какая проблема решить?
Флойд, из каждого в каждый - решать будет долго. А из конкретного в конкретный решается быстро.

(168) снова тоже самое...

привел аргументированный ответ на "таких компаний в России нет"

- и вместо того чтобы признать свою ошибку начинается
"А какая проблема решить?"

(169) Зачем ты из всего делаешь проблему?

Математику я давно забыл. Попробовал разобраться с Флойдом. Занимательно, но совершенно не понятно как это потом мне поможет Вызывая функцию
КратчайшийПуть(Склад1, Склад100)

получить в итоге такой массив:

Склад1, Склад4
Склад4, Склад77
Склад77, Склад100

(160) а положения ячеек друг-относительно друга как задается у вас? и какую систему управления складом юзаете?

(171) тышшу рублев наскребешшь?

(163) (166) Для случая 10000 складов когда есть ребра графа "каждый в каждый" практически никакой алгоритм не поможет - слишком много вариантов перебирать придется. В реальности каждый из 10000 складов будет связан лишь с несколькими географически соседствующими и эти ребра можно ввести в граф на ЭВМ без лишнего расхода памяти. Понятен смысл (162)?

(174) да это недоработка "общеизвестных алгоритмов" на графах... которые все вершинами оперируют, вместо ребер ))

ЗЫ по 100 рублей за каждый склад готов сделать реально работающий вариант когда даже "каждый в каждый"
причем будет прокладывать маршрут с учетом разных критериев

(166) Наличие хабов экспотенциально упрощает задачу.

(175) Что в твоем понимание есть "реально работающий"?

(176) за разумное время на разумном железе

(177) Обтекаемое определение.

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

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

(179) Как думаешь, сколько будет считать полный пересчет при 100 000 складов и готов ли ты оплатить хотя бы по 10 рублей за склад при неудаче? :)

(181) кто то готов заплатить 10 лямов?
но признаю что при неудаче даже по 1 рублю за склад не готов ((

(182) Ну, так и я готов спорить :)

(181) приблизительно 115,7 дней будет считать

(183) если устроит такой срок то готов ))

(184) Ага, особенно при добалении нового склада ежемесячно )))

(185) да это недостаток
но всегда есть решение, просто нужно за полгодика планировать открытие/закрытие складов ))

(186) Не поможет. Тогда придется открывать склалы пачками раз в полгода.

А решение есть - хабы.

(186)+ хотя подождите... я же не учел что задачка то распараллеливаемая!!!

можно заюзать 115,7 компов и посчитать за 1 день ))

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

(188) Ты про разумное железо говорил :-)

(189) эм, то-то я удивляюьсь. Т.е. надо умножить на 100000! (Факториал) :)))))

Черед, не факториал а цэ из 100000 по 2)

(189)+ если хочется найти все маршруты между всеми парами складов то примерно 115740,7 компов нуна ))

(193)+ сорри ошибся )) 11574074,07 компов ))

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

(191) Вы о чем? Маршруты между всеми парами складов считаются за О(N^3), на одну пару О(N), за секунду средний комп считает 10^8 операций. Факториал то откуда?

100 000 складов. 10^15 операций для расчета кратчайшего пути между всеми парами складов. Метод Флойда совсем простой. Средний комп скорей всего потянет 10^9 операций. На полный расчет потребуется 10^6 секунд. 11,5 дней.
Памяти оперативной потребуется на матрицу 10^5 x 10^5, если каждая ячейка 8 байт (int64) - 8*10^10 байт, 80 гигабайт.
С учетом распараллеливания нормальный сервак почитает меньше чем за день.

(174) Ошибаешься. Для 100 000 складов см. (196), (197)

(196) Да, тупанул.

(197) не учтены затраты на подготовку матрицы (с предварительным построением и нумерацией списка складов), на восстановление пути из допматрицы


// Для начала подготовим маршруты
    тзМаршруты = ТаблицаМаршрутов.Скопировать();
    тзМаршруты.Колонки.Добавить("СкладОткудаКуда");
    
    // Строим список складов
    тзСклады = Новый ТаблицаЗначений;
    тзСклады.Колонки.Добавить("Склад");
    
    // Для запредельно большого значения
    СуммаВсехМаршрутов = 0;
    
    // Заполняем список складов
    // и заодно составную колонку для поиска по паре складов
    Для Каждого ТекМаршрут Из тзМаршруты Цикл
        НовСтр = тзСклады.Добавить();
        НовСтр.Склад = ТекМаршрут.СкладОткуда;
        НовСтр = тзСклады.Добавить();
        НовСтр.Склад = ТекМаршрут.СкладКуда;
        СуммаВсехМаршрутов = СуммаВсехМаршрутов + ТекМаршрут.Расстояние;
        ТекМаршрут.СкладОткудаКуда = СокрЛП(ТекМаршрут.СкладОткуда)+"_"+СокрЛП(ТекМаршрут.СкладКуда);
    КонецЦикла;
    тзСклады.Свернуть("Склад");
    тзСклады.Сортировать("Склад");
    тзСклады.Колонки.Добавить("Номер");
    Для Каждого ТекСклад Из тзСклады Цикл
        ТекСклад.Номер = тзСклады.Индекс(ТекСклад)+1;
        //Сообщить(""+ТекСклад.Номер+"-"+ТекСклад.Склад);
    КонецЦикла;



// Теперь знаем кол-во складов-вершин
    КоличествоСкладов = тзСклады.Количество();
    
    // Матрица исходная
    МатрицаСмежности = Новый Массив(КоличествоСкладов+1, КоличествоСкладов+1);
    
    // Матрица путей
    МатрицаПредков = Новый Массив(КоличествоСкладов+1, КоличествоСкладов+1);
    
    // Заполнение начальной матрицы
    // сначала 0 и заведомо большие расстояние
    Для i=1 По КоличествоСкладов Цикл
        Для j=1 По КоличествоСкладов Цикл
            Если i=j Тогда
                МатрицаСмежности[i][j] = 0;
            Иначе
                МатрицаСмежности[i][j] = СуммаВсехМаршрутов * СуммаВсехМаршрутов;
            КонецЕсли;
            // не забываем про матрицу предков для восстановления пути
            МатрицаПредков[i][j] = j;
        КонецЦикла;
    КонецЦикла;
    // затем сами расстояния
    Для Каждого ТекМаршрут Из тзМаршруты Цикл
        СтрокаОткуда = тзСклады.Найти(ТекМаршрут.СкладОткуда, "Склад");
        i = СтрокаОткуда.Номер;
        
        СтрокаКуда = тзСклады.Найти(ТекМаршрут.СкладКуда, "Склад");
        j = СтрокаКуда.Номер;
        
        МатрицаСмежности[i][j] = ТекМаршрут.Расстояние;
    КонецЦикла;



// номер начальной вершины - склада
    СтрокаОткуда = тзСклады.Найти(СкладОткуда, "Склад");
    i = СтрокаОткуда.Номер;
    // номер конечной вершины - склада
    СтрокаКуда = тзСклады.Найти(СкладКуда, "Склад");
    j = СтрокаКуда.Номер;
    
    // Ну и проверим что у нас насчитало
    Если Матрица[i][j] >= СуммаВсехМаршрутов Тогда
        // Если нет маршрута то вернем Неопределено
        Результат = Неопределено;
    Иначе
        // Если есть маршрут то
        // восстановим пусть через небольшие издевательства
                    
        // текущая вершина = начальной
        c = i;
        // Поехали
        Пока c<>j Цикл
            ТекСкладОткуда = тзСклады[c-1][0];
            //Сообщить(""+c + " - "+ ТекСкладОткуда);
            
            c = МатрицаПредков[c][j];
            ТекСкладКуда = тзСклады[c-1][0];
            //Сообщить(""+c + " - "+ ТекСкладКуда);
            
            // Найдем маршрут
            ТекСтр = тзМаршруты.Найти(СокрЛП(ТекСкладОткуда)+"_"+СокрЛП(ТекСкладКуда), "СкладОткудаКуда");
            // и добавим в результат
            НовСтр = Результат.Добавить();
            НовСтр.СкладОткуда = ТекСтр.СкладОткуда;
            НовСтр.СкладКуда = ТекСтр.СкладКуда;
            НовСтр.Расстояние = ТекСтр.Расстояние;
        КонецЦикла;
        //Сообщить(""+j);
    КонецЕсли;


(200) это O(N^2) - в 100000 раз меньше времени требуется, естественно для того сложность алгоритма и существует, чтоб незначащие операции убирать из расчета времени.

Восстановление пути требуется только в момент поездки, при расчете матрицы это не требуется. По готовой матрице это О(E)

+ (201) Это O(E) с очень маленькой константой.

(201) насчет восстановление пути немного неправда, потому что скажем "заказчик" хочет чтобы пути между каждыми складами уже "в готовом виде" хранились в базе

поэтому нужно для всех пар складов провести восстановление и перевести маршруты в "удобный формат"

(203) Для чего пути хранить в базе?!
Если пути хранятся в базе, то сложность алгоритма всё-равно О(N^3), только памяти потребуется не 80 гигов, а в предельном случае на 5 порядков больше (естественно вне зависимости от алгоритма построения пути).
Зачем заказчик ставит ненужную и невыполнимую задачу? Объясни заказчику что это глупое требование.

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

(204) да согласен

кста "заказчика" пока нету )) просто на ИС выложил готовый код, может кому и понадобится с адаптацией

ЗЫ не в курсе время модерации там сча какое?

(204) Веришь, а зря :)
Я вдруг сообразил, что путь можно хранить не как весь путь, а как первую вершину после стартовой, то гда на восстановление пути требуется такая-же сложность алгоритма как и на простое чтение пути при полном его хранениии. О(длиныпути). Соответственно на хранение пути между каждой парой складов достаточно int32, и всего нужно на хранение и построение и всех длин и всех путей - 120 гигов памяти.

(207) так сейчас так оно и есть по сути
просто развернуть из матрицы в тот же регистр

http://catalog.mista.ru/public/442306/

(208) в какой регистр? Кому пришло голову хранить путь в регистре?

Хотя, какая разница где хранить

(211) вот именно ))

вот сча думаю как эту штуку прикрутить к 2гис или другим картам

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

задача коммивояжера в миниатюре (до 5 точек), причем упрощенная так как можно несколько раз через точку проезжать возращаясь

а то так неудобно самому насчет маршрута думать когда на авто и нужно в несколько мест причем очередность неважна

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