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

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

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

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

(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 точек), причем упрощенная так как можно несколько раз через точку проезжать возращаясь

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

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