История изменений
Исправление alysnix, (текущая версия) :
Я понял основную вашу проблему
дерево кратчайших путей строится на графе, где узлы - пункты назначения.
максимальная глубина такого дерева равна числу узлов - нахудший вариант.
monk предлагает строить его построить на «псевдографе» - то есть просто бумаге в клеточку размером 2* 10^4 x 2* 10^4. то есть вполне регулярной структуре.
тогда неясна постановка задачи. если ему надо пройти из точки А в точку Б, на клетчатой бумаге, то ему надо всего лишь алгоритмически нарисовать прямую. а не строить дерево.
а если ему надо строить дерево, то либо на этой области надо ставить какие-то препятствия, которые надо обходить, либо точки, через которые надо проходить… но тогда все выродится в классическое дерево пути на малом количестве узлов, и все его 20000 вложений пропадут.
вообще оптимальный путь через 20000 пунктов, выглядит устрашающе. вы бы поехали на велосипеде?
Исправление alysnix, :
Я понял основную вашу проблему
дерево кратчайших путей строится на графе, где узлы - пункты назначения.
максимальная глубина такого дерева равна числу узлов - нахудший вариант.
monk предлагает строить его построить на «псевдографе» - то есть просто бумаге в клеточку размером 2* 10^4 x 2* 10^4. то есть вполне регулярной структуре.
тогда неясна постановка задачи. если ему надо пройти из точки А в точку Б, на клетчатой бумаге, то ему надо всего лишь алгоритмически нарисовать прямую. а не строить дерево.
а если ему надо строить дерево, то либо на этой области надо ставить какие-то препятствия, которые надо обходить, либо точки, через которые надо проходить… но тогда все выродится в классической дерево пути на малом количестве узлов, и все его 20000 вложений пропадут.
вообще оптимальный путь через 20000 пунктов, выглядит устрашающе. вы бы поехали на велосипеде?
Исходная версия alysnix, :
Я понял основную вашу проблему
дерево кратчайших путей строится на графе, где узлы - пункты назначения.
максимальная глубина такого дерева равна числу узлов - нахудший вариант.
monk предлагает строить его построить на «псевдографе» - то есть просто бумаге в клеточку размером 210^4 x 210^4. то есть вполне регулярной структуре.
тогда неясна постановка задачи. если ему надо пройти из точки А в точку Б, на клетчатой бумаге, то ему надо всего лишь алгоритмически нарисовать прямую. а не строить дерево.
а если ему надо строить дерево, то либо на этой области надо ставить какие-то препятствия, которые надо обходить, либо точки, через которые надо проходить… но тогда все выродится в классической дерево пути на малом количестве узлов, и все его 20000 вложений пропадут.
вообще оптимальный путь через 20000 пунктов, выглядит устрашающе. вы бы поехали на велосипеде?