Tree

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

Возьми почти любую топологическую задачу. Если карта в длину имеет 20 тысяч клеток, то дерево кратчайших путей к одному из краёв определённо будет иметь много веток с глубиной не менее 20 тысяч.

не понял идеи. кратчайший путь - прямая. ей ветки не нужны.

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

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

не понял идеи. кратчайший путь - прямая. ей ветки не нужны.

Я понял основную вашу проблему

Я понял основную вашу проблему

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

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

monk предлагает строить его построить на «псевдографе» - то есть просто бумаге в клеточку размером 2* 10^4 x 2* 10^4. то есть вполне регулярной структуре.

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

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

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

ps. прошу пардону за описки, меня все время отрывают.

monk предлагает строить его построить на «псевдографе» - то есть просто бумаге в клеточку размером 2* 10^4 x 2* 10^4. то есть вполне регулярной структуре.

Для каждого узла есть пути в 6 или 8 соседних. В каждый со своим весом (учёт территории/препятствий/…).

И надо не из точки А в точку Б, а из любой точки в точку Б, поэтому дерево.

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

Это всего лишь 20-километровый маршрут по топографической карте с разрешением до метра.

гонишь! это 20 км маршрут, где на каждом метре мина, которую надо обходить, о чем написано у тебя в дорожной карте, куда на каждом метре поворачивать. и это - список.

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

гонишь! это 20 км маршрут, где на каждом метре мина, которую надо обходить, о чем написано у тебя в дорожной карте, куда на каждом метре поворачивать. и это - список.

Где-то склон, где-то овраг и на топографическом плане этой есть. Единичный маршрут = список, а маршрут из любой точки — дерево.

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

Верно. Потом упёрся бы в болото или овраг и топал бы лишних 5 километров. Ещё горные маршруты бывают, там кусочная аппроксимация приводит к тому, что назад возвращаться приходится и с совсем другой стороны идти.

Всё-таки оптимальней это сделать единожды компьютером, а не каждый раз ногами.

Единичный маршрут = список, а маршрут из любой точки — дерево.

список списков. чойта сразу дерево?

список списков. чойта сразу дерево?

Потому что let me google that for you AGAIN

Размер дерева кратчайших путей линейно зависит от размера графа. Представить то же самое списком списков — квадратично. Для карты 20`000x20`000 клеток в дереве будет всего лишь 400`000`000 вершин. Вы же предлагаете 400`000`000 списков по много (вплоть до 400`000`000) вершин в каждом.

Размер дерева кратчайших путей линейно зависит от размера графа.

перенумеруйте все точки натуральными числами. вопрос - как, идя к некоей точке Dst, и находясь в некой точке Curr, выбрать верное направление на вашем дереве,то есть точку, куда сделать шаг? у вас тут не хватает некоей информации.

в плюсах плохо => от функциональщиков вред один!

Без умения в логику и в других ЯП плохо.

перенумеруйте все точки натуральными числами. вопрос - как, идя к некоей точке Dst, и находясь в некой точке Curr, выбрать верное направление на вашем дереве,то есть точку, куда сделать шаг? у вас тут не хватает некоей информации.

Берём дерево кратчайших путей для точки Dst. Тогда в точке Curr нужное направление будет направлением к родительскому узлу.

Берём дерево кратчайших путей для точки Dst.

технически-то как это дерево выглядит для некой точки конечной точки X на области NN. это же матрица переходов в соседа из текущей точки Y, чтобы максимально быстро достичь X, из текущей Y. не пакуем представление. путь будет байт на точку. итого NN байт. это матрица, она же «дерево» кратчайших путей.

поскольку точек NN то таких матриц(деревьев) будет NN. то есть имеем NN * NN байт для всех точек области.

байт на точку можно сократить до 3 бит на точку, ибо соседей 8. то есть имеем N^4 *3/8 байт. меньше не получается.

на таких «деревьях» рекурсии нет. стартуя из точки A в конечную точку B, берем дерево(матрицу) для B, и итеративно идем из A по трех битовым переходам.

это то что вы говорите?

на таких «деревьях» рекурсии нет. стартуя из точки A в конечную точку B, берем дерево(матрицу) для B, и итеративно идем из A по трех битовым переходам.

Для этой задачи нет.

А для задачи «за какое максимальное время робот с карты придёт на базу» есть.

Потому что алгоритм выглядит так

максимальное-время точка =
  список-времён = отобразить 
    функция (точка)
      максимальное-время точка + расстояние-до-родителя точка
    дети(точка)
  если 
    пустой?(список-времен)
      0
    иначе 
      максимум список-времён

Для этой задачи нет.

а какое у вас физическое представление «дерева путей» для одной точки на N *N матрице? я счас пытаюсь обьем данных в байтах подсчитать.

а какое у вас физическое представление «дерева путей» для одной точки на N *N матрице? я счас пытаюсь обьем данных в байтах подсчитать.

У головы список детей. У ребёнка родитель и расстояние до него.

Если надо экономить байты, то список детей можно получить как список соседей, у которых родителем заданная точка.

У головы список детей. У ребёнка родитель и расстояние до него.

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

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

Если не экономить, то в точке до 8 детей, значит будет

8 * 8 = pointer ссылки на детей 8 = int количество ссылок 8 = double расcтояние 8 = pointer ссылка на родителя

Итого до 88 * N * N. Если дети связным списком, а не массивом, то будет 16 * 8 + 8 + 8 = до 144 * N * N.

Если экономить, то детей получаем перебором, в ребёнке нужно расстояние и направление на родителя. 4,5 * N * N.

На каких ЯП вы это делаете?

А какая разница. Ну ответят тебе «на рефале», и что дальше будешь делать?

Если экономить, то детей получаем перебором, в ребёнке нужно расстояние и направление на родителя. 4,5 * N * N.

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

и что? мое представление компактней, и чтобы по нему ходить не надо рекурсий.

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

и что? мое представление компактней, и чтобы по нему ходить не надо рекурсий.

Как максимальный путь без рекурсий будешь вычислять? Из каждой точки строить путь? Так тогда у тебя NNM операций, где M длина пути, а рекурсивно просто N*N, так как каждая точка будет посещена единожды.

а на ваших размерах 2*10^4, карта только для одной точки будет порядка гигабайта. так?

а на ваших размерах 2*10^4, карта только для одной точки будет порядка гигабайта. так?

Да. А что такого? Даже у сотового этих гигабайтов несколько.

Если памяти совсем мало, то расстояния могут не храниться, а вычисляться. Тогда будет 0,5 байта на точку. 0,2 гигабайта на пути и сколько-то на описание алгоритмов вычисления (векторное представление территории).

Тогда будет 0,5 байта на точку

полбайта на точку, это у вас будет 200 мб карта только для одной точки назначения.

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

Согласен. Собственно, суть контрпримера и была про то, что 10^4 уровней вряд ли хватит на всё, при том, что объёмы данных даже в памяти нынче легко достигают терабайта.

С тем, что, настраивая стек, можно любую рекурсивную задачу решить на Си++, я не спорю.

что 10^4 уровней вряд ли хватит на всё,

тогда я имел ввиду сортировки и передачу вложенных данных. но все равно 10^4 и 2*10^4 величины одного порядка.