Комментарии 34
Это, конечно, очень интересная история, но не могли бы вы немного рассказать о самом способе обхода графа?
По тому, как написана статья, могу только процитировать своего друга: «В этой статье я могу только отметить то, что охеренно студенты живут, ну и типа ты в цюрихе, этот в чехии, взяли встретились потусили, сгоняли в панаму». К сожалению, ребятам из России-матушки такое все менее доступно. Не в смысле, что у нас обсуждать не с кем, а в смысле открытости границ и опасности отмены «открытой науки» по месту рождения.
«Он очень быстрый, простой и лёгкий в реализации»
в этом месте я гоготнул, самый быстрый из самых медленных? Декстру практически всегда приходится упрощать за счёт предварительной работы с графом, чтобы обход был минимальным по данным, иначе добавление одного узла приводит к кратному усложнению расчёта.
например я прикручивал Декстру к LZSS для поиска оптимального решения, для файла всего в 6 Кб (6 тысяч узлов) на современном ПК расчёт длится около 40 минут. Выкинул Декстру и сам написал обход однонаправленного связного графа, вычисления длятся 20 секунд и моя реализация поддерживает многопоток и даёт два решения - оптимальное и неоптимальное, но самое быстрое.
Talk is cheap, show me the code)
И профиль!
Во-первых, я никому ничего не должен.
Во-вторых, как минимум BFS и A-star быстрее Дейкстры, так что Дейкстра это не про скорость и доказательства это не требует.
В-третьих, если вы уж собрались от кого-то что-то требовать, то для начала сами начните предоставлять код к своим комментариям. А то захожу в ваш профиль и вижу бла-бла-бла и без всякого кода. Нехорошо.
@Artyomcool, @MainEditor0 какой еще профиль и репозиторий? Если вы таким образом называете Github, то найти его не сложно, только зачем он вам?
Профиль - это результат профилирования. Без профиля утверждать, что проблема в алгоритме, а не в реализации, как минимум странно.
A* ищет кратчайшее расстояние только до одной точки, в отличие от Дейкстры, поэтому они не взаимозаменяемы. Кроме того, его качество сильно зависит от выбранной эвристики, которую построить таким образом, чтобы алгоритм всё ещё оставался корректным, не всегда вообще возможно.
Bfs же вообще не учитывает вес ребер.
Ваше оригинальное утверждение про 40 минут и 6к вершин предельно контринтуитивно, даже при квадратичной сложности так долго работать не должно, именно поэтому люди просят посмотреть код, чтобы понять, в чём же дело.
Вы бы статьи мои глянули что ли прежде чем чем так уверенно говорить)
BFS и A-star быстрее Дейкстры,
Вот только это алгоритмы для решения других задач. BFS ищет пути от одной ко всем в невзвешанных графах, а A-star ищет путь от одной вершины к одной заданной, а не ко всем.
То, что вы их по скорости сравниваете, говорит, что вам стоит подучить теорию графов.
Декстру к LZSS для поиска оптимального решения, для файла всего в 6 Кб (6 тысяч узлов)
Вы где-то сильно накосячили при реализации. На графе из 6000 вершин, даже если дам 18 миллионов ребер, дейкстра отработает за доли секунды. Ну, или, вы попытались применять Дейкстру к какой-то вашей задаче, где он вообще не применим. Вы там к алгоритму сжатия его как-то прикручивали? Тут больше структура данных Trie и какое-нибудь динамическое программирования применимы, чем поиск кратчайшего пути на графе.
BFS ищет пути от одной ко всем в невзвешанных графах
Картинка
Около года лежит в черновиках, может когда-то допишу. Там как раз модификация BFS, как видно из названия "иерархический направленный взвешенный граф", причем у рёбер могут быть не только данные о весе, это скорее целая характеристика, класс если хотите, которые влияют на прохождение.
Вот только это алгоритмы для решения других задач
Ну в своё время Дейкстру мне настоятельно рекомендовали использовать такие же люди как вы, программисты от бога, вас много, а я один. Вам нужно встретиться и пообщаться что там можно а что нельзя.
То, что вы их по скорости сравниваете, говорит, что вам стоит подучить теорию графов
Я учился последний раз 40 лет назад, сейчас я имею задачу на руках и ищу решение, часто, спрашивая о решении у таких людей как вы. Так что если кому-то что-то нужно подучить, то это тем, кто этого Дейкстру мне и советовал.
Вы где-то сильно накосячили при реализации. На графе из 6000 вершин, даже если дам 18 миллионов ребер, дейкстра отработает за доли секунды
Не отработает, там и для BFS долей секунд не будет.
Ну, или, вы попытались применять Дейкстру к какой-то вашей задаче, где он вообще не применим
Если данные можно представить в виде взвешенного графа, то в чем проблема применить там этот алгоритм?
Вы там к алгоритму сжатия его как-то прикручивали? Тут больше структура данных Trie и какое-нибудь динамическое программирования применимы, чем поиск кратчайшего пути на графе.
Меня не сильно волнует что там можно, я занимался исследованиями интересными мне, сжатие тут скорее как предметная область, а не как самоцель.
@MainEditor0я где-то написал что хочу делиться кодом?
Профиль - это результат профилирования. Без профиля утверждать, что проблема в алгоритме, а не в реализации, как минимум странно.
Я не знаю что такое профилирование.
В интернете достаточно много материала по Дейкстре, включая то, как именно реализуется та или иная его часть. Например я пользовался Фибоначчиевой кучей, вы считаете что есть что-то кратно более быстрое?
Bfs же вообще не учитывает вес ребер.
Наверное у меня неправильный BFS, так как он учитывает.
Ваше оригинальное утверждение про 40 минут и 6к вершин предельно контринтуитивно, даже при квадратичной сложности так долго работать не должно, именно поэтому люди просят посмотреть код, чтобы понять, в чём же дело.
Про лема в том, что на этапе конструирования графа 6000 ребер превращаются в 1.2 млн, так как каждое ребро приобретает определенные свойства. То есть кроме веса, как некоего числа, в качестве характеристики используется (условно) класс, описывающий определенные свойства и на основании этих свойств и принимается решение об оптимальности маршрута. Если перейти на термины A*, то для определения веса используется эвристика. Декстра не смог такое осилить, так как вместо поиска оптимального маршрута он ищет все возможные маршруты, а это долго. Используя BFS я это делаю сильно быстрее. Например Декстру я сильно ускорил когда научил его работать с иерархическим направленным взвешенным графом, коим и является задача. Прикрутив Фибоначчиеву кучу ускорил еще. Но скорость всё равно оставалась непотребной. Поэтому стал писать свою реализацию, сначала придумал, реализовал, но позже узнал что это все называют BFS, просто у меня он работает со взвешенным графом.
Код я практически никогда не показываю, в редких случаях - для статей. Если не жалко времени - напишите через Дейкстру обход иерархического направленного взвешенного графа. Выглядит он вот так
Или для того самого файла на 6К:
Скрытый текст
Это только стартовый граф, после он преобразуется в другой сильно большего объёма, к сожалению как и зачем я уже не скажу.
Дело не в том, считаю ли я, есть ли что-то более быстрое с алгоритмической точки зрения. Дело в том, что без кода и/или профиля рассуждать в воздухе что быстрее абсолютно бесперспективно.
Разумеется есть частные случаи, когда разные алгоритмы, как тот же волновой, эффективнее Дейкстры. Но не в общем случае.
Если мы говорим, что что-то работает медленно, совершенно не факт, что это вообще как-то связано с алгоритмом. Часто (чаще всего) - дело в реализации. Способ организации данных, например, влияет на работу кэшей, а это, извините, несколько порядков по разнице производительности.
В общем, утверждения характера "я написал А, оно медленнее Б, и все кто утверждает обратное - дураки и не лечатся" без возможности "дуракам" проверить, в чем дело, почему у них с А всё в порядке, а у автора сложности, выглядят... Ну мягко скажем, не обоснованно.
тем, кто этого Дейкстру мне и советовал.
Из всяких упоминаний вами "иерархического графа", каких-то характеристик ребер и построения нового графа по заданному становится очевидно, что у вас какая-то другая задача а не просто "дан взвешанный граф, найти в нем кратчайший путь из S во все вершины". Из того, что вы за всю ветку так никаких деталей вашей задачи и не раскрыли, а лишь таинственно намекали, что задача у вас сложная и интересная и мы тут все ничего не понимаем, видно, что вы не хотите ей делиться с общественностью. Если вы точно так же задавали вопросы, то понятно, почему вы не получили удовлетворяющих вас ответов.
Если данные можно представить в виде взвешенного графа, то в чем проблема применить там этот алгоритм?
Алгоритм Дейкстры ищет путь от одной вершины ко всем, при этом длина пути - просто сумма фиксированных весов ребер в нем. К тому же ребра должны быть неотрицательные. У вас, судя по всему, что-то более хитрое. Возможно длина ребер зависит от предыдущего пути, или еще что-то.
Раз у вас алгоритм Дейкстры выродился в полный перебор всех путей, значит условия для применения алгоритма не выполняются. При выполнении этих условий он работает, как написанно в википедии за O((V+E)logV), отработав за секунду для десятков миллионов ребер и вершин.
Наверное у меня неправильный BFS, так как он учитывает.
Да, у вас какой-то свой алгоритм, основанный на BFS, а не обход в ширину. В алгоритме "обхода в ширину" вообще понятие длин ребер нигде не встречается.
Вообще, есть обобщение BFS с несколькими очередями, и оно ищет пути от одной вершины ко всем в графе со взвешенными ребрами, когда все веса целые неотрицательные и ограниченные какой-то константой М за O(MV+E). Чуть более простая его версия 0-1-BFS Работет с ребрами длинами 0 и 1 и там используется дек вместо очереди. Возможно вы додумались до них, это круто. Но эти алгоритмы нельзя просто называть "BFS". Это именно обобщения BFS с несколькими очередями или деком. Без уточнений о том, что у вас за граф, какие там особые ограничения, об этих алгоритмах нет смысла говорить.
То есть кроме веса, как некоего числа, в качестве характеристики используется (условно) класс, описывающий определенные свойства и на основании этих свойств и принимается решение об оптимальности маршрута
Ну вот, т.е. в вашей задаче Дейкстра не применима. Повторю, там длина пути - тупо сумма фиксированных длин ребер. Если же у вас там какая-то более сложная функция вычисления длины пути, то в некоторых случаях туда еще можно прикрутить обобщение Дейкстры, работающее почти за то же самое время. Но надо знать как именно у вас считается длина пути.
напишите через Дейкстру обход иерархического направленного взвешенного графа. Выглядит он вот так
Глядя на картинку закрадывается мысль, что вы под "иерархическим" графом имеете ввиду "ациклический" - в графе нет циклов, т.е. все вершины можно упорядочить так, что все ребра идут сверху вниз. Я правильно понимаю, или "иерархический" - это что-то другое?
Тут можно применить еще и динамическое программирование. Если у вас длины пути считаются как суммы. Со стороны это, действительно, может походить на обход в ширину или обход в глубину, потому что все вершины будут обходиться в порядке сверху вниз или снизу вверх. Это будет побыстрее Дейкстры, для таких графов, но не на порядки.
Но, пока вы не объясните как именно у вас строится граф и как именно в нем считаются длины пути, вам никто не сможет сказать, какой алгоритм тут будет лучше всего.
Если мы говорим, что что-то работает медленно, совершенно не факт, что это вообще как-то связано с алгоритмом. Часто (чаще всего) - дело в реализации. Способ организации данных, например, влияет на работу кэшей, а это, извините, несколько порядков по разнице производительности.
Не совсем понимаю о чем вы, но порассуждаю, а вы напишете так ли это. Например во многих алгоритмах при описании есть фраза "берём оставшиеся", а при реализации получается так, что чтобы взять те самые оставшиеся нужно сломать мозг, так как на пальцах всё красиво, а на деле всё не так просто. Только дело в том, что если у меня данные представлены определенным образом и никак иначе, то и сами данные будут влиять на скорость и если Дейкстра тут проседает, то разве дело в самих данных? Просто в Дейкстре насколько я могу вспомнить сама нагруженная часть это как раз брать оставшиеся соседние рёбра и если их очень много, то и брать и вы будете очень долго. Причем Фибоначчиева куча, как я могу судить по разным гайдам в сети, даёт хорошие результаты (фактически лучшие), так что это максимум, который вы можете вытащить из этого алгоритма.
В общем, утверждения характера "я написал А, оно медленнее Б, и все кто утверждает обратное - дураки и не лечатся" без возможности "дуракам" проверить, в чем дело, почему у них с А всё в порядке, а у автора сложности, выглядят... Ну мягко скажем, не обоснованно.
Поступим иначе, дайте мне ссылку на код хорошей реализации Дейкстры на C#, я попробую её и посмотрим есть ли разница между моей и чужой реализацией.
Из всяких упоминаний вами "иерархического графа", каких-то характеристик ребер и построения нового графа по заданному становится очевидно, что у вас какая-то другая задача а не просто "дан взвешанный граф, найти в нем кратчайший путь из S во все вершины".
Мне нужен оптимальный маршрут, по сути Дейкстра это и делает: Алгоритм Дейкстры — это алгоритм, предназначенный для нахождения кратчайших путей от одной вершины графа (начальной) до всех остальных вершин. Он работает только для графов с неотрицательными весами рёбер.
Я начала именно с графа, который расползался на N маршрутов, иногда они встречались снова и т.д. Дейкстра делал своё дело, но всё было медленно. Тогда я стал работать над самим данными и при шёл к некоторым упрощениям.
Во-первых граф иерархический: Иерархический граф — это тип графа, который организует свои вершины (узлы) в виде иерархической структуры, где вершины имеют различные уровни или степени важности. В иерархическом графе связи между вершинами часто описывают отношения «родитель-потомок» или «более высокий уровень — более низкий уровень».
Это позволяет организовать перемещение по графу только сверху-вниз, исключая любое движение вправо или влево.
Во-вторых, он направленный: Направленный граф (или ориентированный граф) — это структура, состоящая из множества вершин (или узлов) и рёбер (или дуг), где каждое ребро имеет направление, указывающее от одной вершины к другой. Это означает, что ребра в направленном графе имеют начало и конец, и порядок вершин важен.
Причем направление задано только сверху вниз.
В-третьих, он связный, то есть мы можем получить доступ ко всем вершинам.
Такая характеристика графа и учет этого в реализации Деёкстры сильно упростили обход графа и всё стало несколько поживее работать.
Находить путь ко всем вершинам как было так и осталось, только на определенных этапах "все" приобретало разное значение, то есть движение вниз уменьшало число вершин. Это точно не делало Дейкстре хуже, скорее наоборот.
Из того, что вы за всю ветку так никаких деталей вашей задачи и не раскрыли, а лишь таинственно намекали, что задача у вас сложная и интересная и мы тут все ничего не понимаем, видно, что вы не хотите ей делиться с общественностью
Это мои исследования и я имею право их не публиковать, независимо от того насколько они важны для вас лично или для человечества в целом. Не всем близка идея опенсорса или фриваре. Насчёт того что она сложная я бы не сказал, я же задачу решил, а учитывая мой весьма низкий уровень программирования - задача точно не сложная. Интересная она скорее всего только для меня.
Если вы точно так же задавали вопросы, то понятно, почему вы не получили удовлетворяющих вас ответов.
Я не мог задавать точно так же вопросы просто потому, что на момент задавания вопросов у меня не было кода, а был лишь вопрос - как обойти все вершины графа и получить оптимальный маршрут.
Алгоритм Дейкстры ищет путь от одной вершины ко всем, при этом длина пути - просто сумма фиксированных весов ребер в нем. К тому же ребра должны быть неотрицательные. У вас, судя по всему, что-то более хитрое. Возможно длина ребер зависит от предыдущего пути, или еще что-то.
и как хитрость влияет на что-то? какая разница алгоритму переменная Weight является константной переменной INT или функцией, возвращающей INT? Да, учитываются многие параметры.
Раз у вас алгоритм Дейкстры выродился в полный перебор всех путей, значит условия для применения алгоритма не выполняются. При выполнении этих условий он работает, как написанно в википедии за O((V+E)logV), отработав за секунду для десятков миллионов ребер и вершин.
Ну до того как вес стал функцией у меня дейкстра бегал просто по INTам, скорости это не сильно много прибавляло, даже прикручивание Фибоначчиевой кучи которая из N*N делает logN всё равно не сильно поменяло что-то (думаю вам нет разницы что вместо 60 минут у вас что-то считается 40 минут). Могу лишь списать на C# как таковой, но по ситуации с черепашками вы сами видели, что при хорошей реализации на C# легко можно обойти C++, так как тут будет решать алгоритм как таковой. Вот и в этой ситуации я изменил подход к обходу графа и получил хорошие результаты.
Да, у вас какой-то свой алгоритм, основанный на BFS, а не обход в ширину. В алгоритме "обхода в ширину" вообще понятие длин ребер нигде не встречается.
То есть если я к велосипеду прикручу корзинку, то он сразу перестанет быть велосипедом?
Вообще, есть обобщение BFS
не важно как это называется, зачем играть в термины. Модифицированный BFS. Можете называть "Великим алгоритмом обхода иерархического ориентированного взвешенного графа имени Zara6502" если вам так будет комфортнее.
Ну вот, т.е. в вашей задаче Дейкстра не применима
Почему?
Повторю, там длина пути - тупо сумма фиксированных длин ребер
Так и у меня они фиксированные, просто фиксация происходит на этапе выполнения в зависимости от предыдущих данных. У нас нигде не сказано что Дейкстра работает только на топологиях звезда например, граф может быть любой, главное что? Правильно, чтобы это был взвешенный граф с неотрицательными весами. У меня это условие выполняется. А то что я на этапе выполнения могу пару рёбер убрать (или не могу?) как-то никто не написано. Ну вот простой пример, у вас есть граф:
A-B-C-D
\EИ вот мы пошли по A-B-C и приняли решение что C-E нам не нужно и убрали ребро. А C-D посчитали. Всё. Что не так? Ну умерла какая-то ветка, выкинули её. Это же простейшая оптимизация, мы так можем выкинуть до 99% графов, ну цель у нас такая или если не всё обсчитываю то это типа "низзя" никак? Почему нельзя? Кто так решил? Почему если я Дейкстре помогаю это уже не Дейкстра? Алгоритм же остаётся прежним и даже его реализация той же.
Глядя на картинку закрадывается мысль, что вы под "иерархическим" графом имеете ввиду "ациклический" - в графе нет циклов, т.е. все вершины можно упорядочить так, что все ребра идут сверху вниз. Я правильно понимаю, или "иерархический" - это что-то другое?
Определение гуглится, не я же его придумал, я только использую. Иерархия подразумевает то, что одно выше другого, а в моём случае направленность еще и не позволяет двигаться "против шерсти". К иерархии я пришёл из-за того, что обработка файла происходит от начала к концу и когда я прошёл N-ый элемент мне уже нет дела до него, в том смысле что как элемент графа он уже не нужен и вершина умирает.
У меня кстати сначала были и вершины и рёбра, но потом так получилось что мне стало достаточно вершин и указания в вершине на то, с какой другой вершиной она соединяется.
Тут можно применить еще и динамическое программирование
Я такое не понимаю.
Если у вас длины пути считаются как суммы
Вы про то что длина пути это сумма весов рёбер? А бывает иначе?
Со стороны это, действительно, может походить на обход в ширину или обход в глубину, потому что все вершины будут обходиться в порядке сверху вниз или снизу вверх. Это будет побыстрее Дейкстры, для таких графов, но не на порядки.
Ну тут ведь все и так пишут что всё зависит от реализации, ну вот модифицированный BFS и делает всё то же самое но быстрее и ощутимо, в данном случае сам принцип обхода другой, если у Дейкстры мы работаем с рёбрами, то в модифицированном BFS рёбер нет вообще, а есть вершины имеющие линк на следующую ступень иерархии. Там сразу много разных оптимизаций вылезает которые всё сильно упрощают. Чтобы в Дейкстру что-то интегрировать приходилось много чего переписывать, а тут получался один метод который обрабатывал вершины и вся логика была в нём, он за проход генерировал новый набор вершин для следующей ступени и переходил на неё, то что в Дейкстре получалось костылём тут работало как влитое из коробки.
Но, пока вы не объясните как именно у вас строится граф и как именно в нем считаются длины пути, вам никто не сможет сказать, какой алгоритм тут будет лучше всего.
Мне нравится (нет) что вас устраивает положение вещей когда я могу быть дураком, но задевает, когда ими можете быть вы. Как-то странно так себя вести вы не находите?
PS: мы уже проходили с вами этап дискуссии где я вам доказал вашу неправоту даже написав целую статью и вы продолжаете настаивать что в диалоге я должен отталкиваться от предпосылки что вы говорите правильные вещи, а я заблуждаюсь? Вы серьёзно? Я не отказываюсь от того что я многие вещи не знаю и не понимаю, но это совсем не значит что от моих слов можно отмахиваться.
Показывать мне вам пока нечего, примите как данность мои слова. Не хотите - не заставляю. Но буду рад заполучить реализацию Дейкстры с Фибоначчиевой кучей на C#, мне как-то не удалось такое найти в готовом виде и таким, чтобы был понятен механизм использования.
Иерархический граф — это тип графа, который организует свои вершины (узлы) в виде иерархической структуры,
Это не общепринятый термин. Общепринятый - ориентированный ациклический граф. DAG по английски.
дайте мне ссылку на код хорошей реализации Дейкстры на C#
https://rosettacode.org/wiki/Dijkstra's_algorithm#C#
Там достаточно хорошая реализация самого алгоритма, но есть лишние проверки в интерфейсе, все-таки это довольно обобщенная реализация. Закомментируйте вызов HasEdge() в AddEdge().
Там обычная куча. Фиббоначиева куча теоретически быстрее, но на практике будет полезна только для очень больших графов. У вас, по описанию, не достаточно большой граф. И судя по тому, что вы говорили, что у вас Дейкстра все пути перебирала - у вас неправильная реализация.
Мне нужен оптимальный маршрут, по сути Дейкстра это и делает:
Дейкстра ищет кратчайший* маршрут, а не "оптимальный". Если у вас критерий оптимальности не тупо "сумма чисел на ребрах минимальна", то вам надо подумать прежде чем применять дейкстру. Вы писали, что у ребер есть какие-то свойства, которые влияют на то, можно ли по ним проходить - это звучит как противопоказание к Дейкстре. Если вы, таки, напишите наконец-то условие вашей задачи, я смогу вам точно сказать.
*Вообще, Дейкстра обобщается на целый класс функций расстояния, например, если у вас длина пути - это длина минимального ребра в пути. Но должны выполнятся особые свойства, чтобы алгоритм был применим. Пока вы не расскажите вашу задачу, и судя по тому, что у вас алгоритм выродился в перебор всех путей, как вы написали, нужные свойства не выполняются.
и как хитрость влияет на что-то? какая разница алгоритму переменная Weight является константной переменной INT или функцией, возвращающей INT?
Нет же, если у вас просто длина ребра как-то считается от фиксированных параметров, то это и есть фиксированная длина ребра и все ваши параметры - это лишь мишура и деталь реализации. Речь шла а том, что длина ребра может менятся, например, от того по каким ребрам вы прошли раньше. Или от времени.
Определение гуглится, не я же его придумал, я только использую.
Дайте, пожалуйста, ссылку, если вам не сложно. Я не нагуглил.
Вы про то что длина пути это сумма весов рёбер? А бывает иначе?
Конечно, бывает. Бывает как угодно. Скажем, у вас граф описывает дорожную сеть, и если вы по перекрестку прямо едете, то у вас "длина" следующего ребра короче, ибо вам тормозить не надо, а если вы поворачиваете, то вам еще надо скорость набрать. Бывает, что у вас граф представляет остановки общественного транспорта, и вам надо будет ждать следующего автобуса, так что тут длина следующего ребра зависит от того, в какое время вы оказываетесь в вершине, т.е. от длины предыдущего пути. Или у вас лабиринт с дверьми и ключами, и вы вообще не можете по какому-то ребру пройти, если не посетили вершину с нужным ключем до этого. А в каких-то задачах в качестве длины пути берут максимальное ребро в пути, а не сумму.
Именно про что-то такое я и думал, раз у вас там какие-то параметры и свойства ребер повылезали. Но похоже все гораздо проще. Это вы детали вашей передметной области тащите в граф, хотя они там не нужны. Высчитали вы длину ребра и все, можно про все ваши свойства забыть, это на алгоритм никак не влияет.
И вот мы пошли по A-B-C и приняли решение что C-E нам не нужно и убрали ребро. А C-D посчитали. Всё. Что не так? Ну умерла какая-то ветка, выкинули её. Это же простейшая оптимизация, мы так можем выкинуть до 99% графов, ну цель у нас такая или если не всё обсчитываю то это типа "низзя" никак? Почему нельзя? Кто так решил? Почему если я Дейкстре помогаю это уже не Дейкстра? Алгоритм же остаётся прежним и даже его реализация той же.
А если в графе есть ребро E-D? Вдруг оно короче будет? Вообще, раз вам можно какие-то вершины выбрасывать из графа, у вас задача поиска пути из одной вершины в другую, а не до всех? Это другая задача. Дейкстра лучший алгоритм, если вам надо найти путь до всех вершин в произвольном графе. Тут нельзя ничего выбрасывать.
Вообще, вы сказали, что динамическое программирование вам не знакомо, но в вашей задаче, похоже самым быстрым решением будет именно оно:
Рекурсивная функция, которая выдает кратчайшее расстояние до конца от заданной вершины. Функция сохраняет свой результат и при повторном вызове ничего не считает, а просто возвращает уже подсчитанный результат. Функция перебирает исходящие ребра, вызвается рекурсивно от концов и выбирает лучший вариант ребро+длина оставшегося пути. Если вариантов нет, то возвращает "бесконечность" (можно взять достаточно большое число, или возвращать -1. Только помните, что бесконечность+x=бесконечность).
Если вам нужна не только длина, но и весь путь, то функция еще дополнительно запоминает по какому ребру был кратчайший путь. Для восстановления пути надо от начальной вершины по этим сохраненным ребрам пройтись. Есть еще и нерекурсивная реализация с очередью.
https://rosettacode.org/wiki/Dijkstra's_algorithm#C#
Там достаточно хорошая реализация самого алгоритма, но есть лишние проверки в интерфейсе, все-таки это довольно обобщенная реализация. Закомментируйте вызов HasEdge() в AddEdge().
Посмотрел, простите, но это рукалицо, списки и linq, это же тормозилка педальная. Я решаю задачи по highload и ни одно решение где я бы применил List<T> или LINQ никогда не возьмёт хоть какой-то балл, скорее всего даже в лимиты по времени не пройдёт. Всё пишется самостоятельно, как говорят японцы - селяви, но это C#, детка, только unsafe, только хардкор. Еще ребра в string/char, в общем пока как-то всё странно, тем более использование linq для чего-то помимо <T> потребует реализации разных компараторов и т.п. В общем такое я даже не стану адаптировать, но гарантирую что это ОЧЕНЬ медленная реализация Дейкстры. Можно конечно ради теста засунуть туда 2 млн рёбер и посмотреть как оно отработает, сделать выгрузку из моих данных, но оно же не понимает ничего про иерархию и направленность, не, не буду такое трогать.
Это не общепринятый термин
не считаю что это важно.
И судя по тому, что вы говорили, что у вас Дейкстра все пути перебирала - у вас неправильная реализация.
А как вы хотите получить все расстояния не перебрав все пути? Дейкстра приходит в узел, берёт рёбра и идёт по всем, посещенные отмечает, собственно узкое место как раз в том чтобы отсеивать ребра.
Дейкстра ищет кратчайший* маршрут, а не "оптимальный"
Вы опять играетесь с терминами? Для LZSS кратчайший маршрут == оптимальный, что очевидно для сжатия.
Если у вас критерий оптимальности не тупо "сумма чисел на ребрах минимальна"
Вес ребра, это количество бит, которое будет затрачено для кодирования, соответственно результирующая сумма всех бит (длина маршрута) и будет оптимальным решением.
Из-за особенностей сжатия выбор в начале влияет на выбор в конце, так как вес меняется, например, если у вас в начале просто литералы парами и кодируются они например в 9 бит каждая, а потом у вас повтор на 4 одинаковых знака, то вы кодируете их например в 7 бит. Но если у вас в начале были такие 4 знака и вы их кодировали в 7 бит, то по определенному алгоритму вы можете следующие 4 знака закодировать как повтор например всего в 2 бита. То есть у вас есть вариативность. Пример тупой и просто взят из головы, не нужно его оптимизировать или изучать, просто он упрощённо показывает как всё работает. То есть на определенных участках ребра из литералов могут кратно увеличиться на рёбра из разных кодирующих механизмов. Поэтому то что было в начале как одна штука после обработки становится как 32 штуки. На картинке что я давал выше если бы просто построили граф из литералов, то это была бы прямая сверху вниз где вес ребра был бы всегда 9 бит. А в реальности там пузатые наросты из кучи ребёр.
Вы писали, что у ребер есть какие-то свойства, которые влияют на то, можно ли по ним проходить - это звучит как противопоказание к Дейкстре
а противопоказание в чём? Дейкстра из коробки не запрещает убирать узлы (сиречь рёбра) из списка доступных, это же его суть работы - посчитал, убрал, посчитал, убрал, что плохого в том чтобы что-то убрать еще? Возможно в если бы граф был звездой какой-то, то у вас поломался бы какой-то путь, но в моём случае вы движетесь сверху вниз, то есть убрав что-то впереди вы просто никогда туда не придёте, то есть не будет ситуации когда вы убрали узел из маршрута и в финале просто не сможете вернуться.
Если вы, таки, напишите наконец-то условие вашей задачи, я смогу вам точно сказать.
Во-первых парой слов не описать, во-вторых, выше я написал примерный ход мыслей, в-третьих, я не делюсь своими "изобретениями", какими бы они ненужными и дурацкими не были, мои мысли это единственное что у меня есть и оно моё.
*Вообще, Дейкстра обобщается на целый класс функций расстояния, например, если у вас длина пути - это длина минимального ребра в пути. Но должны выполнятся особые свойства, чтобы алгоритм был применим. Пока вы не расскажите вашу задачу, и судя по тому, что у вас алгоритм выродился в перебор всех путей, как вы написали, нужные свойства не выполняются.
Не особо понимаю о чем вы. Дейкстра считает маршруты для всех узлов, в этом же его смысл. Я наоборот после оптимизаций научил его не ходить по всем, то есть научил его убирать узлы которые остались на предыдущем уровне иерархии.
Нет же, если у вас просто длина ребра как-то считается от фиксированных параметров, то это и есть фиксированная длина ребра и все ваши параметры - это лишь мишура и деталь реализации. Речь шла а том, что длина ребра может менятся, например, от того по каким ребрам вы прошли раньше. Или от времени.
Ну так и смысл функции в том чтобы учитывать прошлые ребра, прошли по A-B у вас путь B-C стал 10, прошли E-B у вас путь B-C стал 7. То есть важно откуда вы пришли.
Дайте, пожалуйста, ссылку, если вам не сложно. Я не нагуглил.
Я гуглом не пользуюсь лет 12 именно по причине отсутствия нормального поиска, ну и есть чаты с ИИ.
Конечно, бывает. Бывает как угодно. Скажем, у вас граф описывает дорожную сеть, и если вы по перекрестку прямо едете, то у вас "длина" следующего ребра короче, ибо вам тормозить не надо, а если вы поворачиваете, то вам еще надо скорость набрать. Бывает, что у вас граф представляет остановки общественного транспорта, и вам надо будет ждать следующего автобуса, так что тут длина следующего ребра зависит от того, в какое время вы оказываетесь в вершине, т.е. от длины предыдущего пути. Или у вас лабиринт с дверьми и ключами, и вы вообще не можете по какому-то ребру пройти, если не посетили вершину с нужным ключем до этого. А в каких-то задачах в качестве длины пути берут максимальное ребро в пути, а не сумму.
Ничего не понял, все что вы перечислили это и есть сумма состояний, не важно как вы их назвали, это всё равно свойства (сумма свойств) характеризующие путь. Вот вы про ключи пишете и вам вроде бы самому всё понятно, так я не могу понять почему моя реализация того же самого у вас вызывает вопросы? То есть в вашем же примере вы описываете то, как ребро может быть непроходимым и вам это делать можно, а почему я если так делаю то это неправильно?
Это вы детали вашей передметной области тащите в граф, хотя они там не нужны. Высчитали вы длину ребра и все, можно про все ваши свойства забыть, это на алгоритм никак не влияет.
Нет, это я вам объясняю что такое у меня вес ребра.
Вообще, вы сказали, что динамическое программирование вам не знакомо, но в вашей задаче, похоже самым быстрым решением будет именно оно:
Рекурсивная функция, которая выдает кратчайшее расстояние до конца от заданной вершины
Любая рекурсия может быть представлена в виде цикла. Но не сильно понимаю в чем различия того что пишете вы и того что делал я или то, о чем вы думаете когда говорите про Дейкстру.
Функция сохраняет свой результат и при повторном вызове ничего не считает, а просто возвращает уже подсчитанный результат
Зачем мне такой функционал? Мне не нужно вызывать функцию два раза, всё считается один раз.
Функция перебирает исходящие ребра, вызвается рекурсивно от концов и выбирает лучший вариант ребро+длина оставшегося пути
Перебирает, это так, но зачем рекурсивно? Зачем мне информация "ребро+длина оставшегося пути"? У меня ищется маршрут от начала по всем ребрам, в финале при обратном ходе мы получаем путь, длина которого и будет оптимальным размером сжатого файла. Прелесть алгоритма в том, что на него можно навешивать любые эвристики и в зависимости от них, но всегда будет искать оптимальный маршрут. А количество рёбер зависит от алгоритма сжатия.
то функция еще дополнительно запоминает по какому ребру был кратчайший путь
оно так и работает, без рекурсий.
Декстра просто работает сразу со всем графом, а мой алгоритм модифицированного BFS работает только с одним уровнем иерархии, а в самой последней реализации я пересадил всё на многопоток и теперь у меня бегут независимые потоки, которые считают определенные маршруты, некоторые умирают, некоторые сливаются и превращаются в один (это кстати частое явление, если посмотреть на картинку то там ветвление всегда приводит к конечному узлу). Так же потоки умирают если на промежуточном узле, куда они пришли уже есть отметка с меньшей длиной пути, то есть например один поток прошел маршрут за 200, а второй пришёл и у него уже 202, то он просто умирает как ненужный или если проще, они сливаются в один поток с весом 200, то есть с минимальным). Вообще от многопотока я решил отказаться, так как ветвления короткие и на производительность это не влияет в лучшую сторону никак, а код усложняется сильно, а я тот еще кодер.
Но в общем случае, когда о данных ничего не известно, Дейкстра вполне себе оптимален (а как показано в статье, не вполне себе, а оптимален).
Я же ничего не говорил о том что Дейкстра неоптимален, я сказал "фи" по поводу того что он быстрый.
и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные (d-ичные[англ.]) кучи на практике эффективнее.
Я прошёл этап работы от O(n*n) без куч, потом до двоичной и Фибиначчиевой, последняя показала хорошие результаты, но проблема отсеивания ребёр как была так и осталась самой сложной/тяжёлой для производительности.
списки и linq, это же тормозилка педальная. Я решаю задачи по highload и ни одно решение где я бы применил List<T> или LINQ
Вы запускали? Linq там используется только в hasEdge, который я попросил закоменнтировать и removeEdge, который вам не нужен. Да в выводе ответа. Это погрешности, даже если оно тормозит. А List<T> - это не список, а массив. Тормозит не сильнее vector в С++, который я всю жизнь использую даже на олимпиадах, где скорость ой как важна. Список в C# - это LinkedList.
Я решаю задачи по highload и ни одно решение где я бы применил
Highload у вас, ха! С жалкими миллионами ребер. Highload, это когда данных столько, что надо запускать на кластере, ибо они в RAM одной машины не помещаются. И при этом надо выдавать ответ в течении миллисекунд. Это точно не ваш случай.
А как вы хотите получить все расстояния не перебрав все пути? Дейкстра приходит в узел, берёт рёбра и идёт по всем, посещенные отмечает, собственно узкое место как раз в том чтобы отсеивать ребра.
Опять у вас с терминологией проблемы. Перебирать все ребра - это не перебирать пути. Перебирать пути, это пробывать a->b->c->d, a->e->d, a->f->c->d... Путей в графе экспоненциально много. Ребра вам итак все придется просмотреть хотя бы по разу, а дейкстра именно столько раз их и смотрит. Меньше уже никак. Их отсекать смысла нет.
а противопоказание в чём? Дейкстра из коробки не запрещает убирать узлы (сиречь рёбра) из списка доступных, это же его суть работы - посчитал, убрал, посчитал, убрал, что плохого в том чтобы что-то убрать еще?
Дейкстра "убирает" вершины, до которых путь уже найден. Дейкстра ищет путь до всех вершин, если вы их как-то еще убираете, вы уже решаете другую задачу, ибо вы не ищите путь до убранных вершин. Для такой задачи A* или какие-то другие отсечения могут быть применимы.
Ну так и смысл функции в том чтобы учитывать прошлые ребра, прошли по A-B у вас путь B-C стал 10, прошли E-B у вас путь B-C стал 7. То есть важно откуда вы пришли.
Это нарушает принципы, на которых Дейкстра строится. Он перебирает вершины в порядке возрастания растояния и считает, что можно приписать новое ребро и путь изменится на фиксированную длину ребра. Потому что если в обрабатываемую сейчас вершину можно было бы прийти несколькими способами, может быть, взяв не самый короткий можно прийти в следующую вершину короче из-за изменчивости следующего ребра. И уже надо хранить все возможные пути в данную вершину и это уже не Дейкстра, а полный перебор с отсечениями. И все, вместо охренительно быстрого O(V log V + E) у вас O(V**V). И тут
Иногда такую задачу можно переформулировать в виде обычного графа с фиксированными ребрами: Для каждой вершины вы создаете кучу вершин - по одной на каждое входящее ребро и делаете из них ребра для каждого исходящего ребра нужной длины. Но это только если длина следующего ребра зависит только от одного предыдущего.
Я гуглом не пользуюсь лет 12 именно по причине отсутствия нормального поиска, ну и есть чаты с ИИ.
О боже, вам даже сам яндекс пишет "возможны неточности". Эти ИИ галюционируют. Но на будущее, не удивляйтесь, если ваши собеседники не будут в курсе, что за "иерархический" граф у вас.
это всё равно свойства (сумма свойств) характеризующие путь
Дейкстра накладывает важные требования на эти характеристики. Она требует:
1. Если к двум путям, заканчивающимся в одной и той же вершине приписать одно и то же ребро, то короткий путь все еще будет короче более длинного.
2. Если к пути приписать ребро, то он не может стать короче.
3. Если к двум путям одинаковой длины приписать одно и то же ребро, то итоговая длина будет одинаковой.
Именно на этих свойствах строистя алгоритм Дейкстры, именно по ним он позволяет себе хранить для каждой вершины лишь расстояние, а не весь путь, потом брать наиближайшую к началу вершину и через нее персчитывать пути к остальным вершинам. Эти свойства, очевидно, выполняются, если у вас все ребра имеют фиксированные и неотрицательные веса и вы просто считаете сумму для пути, как это делается в классических задачах на поиск кратчайшего расстояния в графе, для которых алгоритм и был придуман.
Нельзя взять произвольную функцию высчитывания длины пути, прикрутить ее к дейскстре, а потом ругаться, что дейкстра - плохой, медленный алгоритм. Вы его применили не там, не туда и не так, не понимая как он работает. При этом ругаясь на "всяких как вы", которые вам что-то там не так сказали. Я от вас лишь спустя несколько дней и кучу простыней текста узнал про такую вот маленькую незначительную деталь, что у вас не обычный взвешанный граф, а какая-то хитрая функция расстояния.
Зачем мне такой функционал? Мне не нужно вызывать функцию два раза, всё считается один раз.
У вас граф же не дерево? В вершины же можно прийти несколькими способами с предыдущих "уровней"? Судя по вашим картинкам выше это так. Обычная рекурсивная функция ходя по этим ребрам придет в одну и ту же вершину несколько раз. Но, если у вас функция расстояния от пути классическая аддитивная, то можно результат работы функции не считать второй раз, ведь он будет точно такой же. Именно так и работает динамическое программирование. Но, как вы пояснили, у вас все-таки какая-то сложная функция вычисления длины пути, так что этот метод тут не применим (Также, как и дейкстра).
Если у вас длина следующего ребра зависит только от одного предыдущего ребра, то вы еще можете применить тут дейкстру, построив обычный взвешанный граф на основе вашего. Иначе вы на вашем графе не можете запускать ни один из существующих алгоритмов поиска кратчайшего пути. Они на такое не рассчитаны вообще. Если вы там все-таки запустили дейкстру, то она каждую вершину может обрабатывать кучу раз и она действительно вырождается в перебор почти всех путей в графе. И поэтому работает так долго для такого маленького графа.
Единственный вариант решать вашу задачу через графы: у вас вершины в графе должны соответствовать всем возможным путям, и вам в этом очень большом графе надо запускать A* (не храня сам граф, конечно).
А List<T> - это
несписок, амассив
Ну вы хотя бы дословно можете перевести слово List, но и доступно же определение, в чём спор?
Список в C# - это LinkedList
Нет ) Это связный список (перевод так же вам должен быть понятен).
В C# есть отличия в изменении размера массива и списка, и соответственно из-за этого разница в скорости работы этих коллекций. Очевидно что массив быстрый, но дорого обходится изменение его размера, а список медленный, но изменение размера обходится дешевле. Но в любом случае скорость работы медленная и для highload решений приходится писать свою реализацию.
На Хабре есть статья по List.
Highload у вас, ха! С жалкими миллионами ребер
С чего вы решили что задачи highload и задача с Дейкстрой как-то связаны? Мы же говорим про List и Linq.
Highload, это когда данных столько, что надо запускать на кластере, ибо они в RAM одной машины не помещаются. И при этом надо выдавать ответ в течении миллисекунд. Это точно не ваш случай.
ну началось, давайте не будем спорить что такое highload
Опять у вас с терминологией проблемы. Перебирать все ребра - это не перебирать пути. Перебирать пути, это пробывать a->b->c->d, a->e->d, a->f->c->d... Путей в графе экспоненциально много
Путь состоит из рёбер, перебирая все рёбра вы переберёте все пути, в этом смысл Дейкстры.
Ребра вам итак все придется просмотреть хотя бы по разу, а дейкстра именно столько раз их и смотрит. Меньше уже никак. Их отсекать смысла нет.
Ну для вас смысла нет, а для меня есть, зачем мне перебирать 2 млн рёбер если я могу перебрать 1?
Дейкстра "убирает" вершины, до которых путь уже найден. Дейкстра ищет путь до всех вершин, если вы их как-то еще убираете, вы уже решаете другую задачу, ибо вы не ищите путь до убранных вершин
То есть если я режу мясо вдоль волокон, то я режу мясо, а если поперёк, то я уже нарезаю? Это игра в термины, смысла в этой игре никакого. Я убираю то что мне не нужно, Дейкстра даже не знает об этом, а значит он всегда в момент времени решает свою задачу, то что он решит в итоге задачу не для 2-х, а для 1 млн вершин алгоритму вообще поровну.
Это нарушает принципы, на которых Дейкстра строится
нет, это только добавляет условие. Принципы работы какие были такие и остались.
Он перебирает вершины в порядке возрастания растояния и считает, что можно приписать новое ребро и путь изменится на фиксированную длину ребра. Потому что если в обрабатываемую сейчас вершину можно было бы прийти несколькими способами, может быть, взяв не самый короткий можно прийти в следующую вершину короче из-за изменчивости следующего ребра. И уже надо хранить все возможные пути в данную вершину и это уже не Дейкстра, а полный перебор с отсечениями. И все, вместо охренительно быстрого O(V log V + E) у вас O(V**V). И тут
я не понял что именно вы тут написали и откуда у вас взялся O(n*n). Конкретно у меня будет ровно N итераций, то есть O(n), но если вам интересны константы, то будет O(n+k), где k - это дополнительное число пройденных рёбер. Все мои оптимизации ровно для того чтобы уменьшить k и согласитесь, даже сложность O(V log V + E) для Дейкстры, плюс медленность убирания рёбер как таковая (ну ладно, вершин, хотя какая разница) - дают в итоге падение производительности такое, что моё O(n+k) работает сильно быстрее (вы же понимаете что O(n) это про сложность алгоритма, а не про скорость?).
Иногда такую задачу можно переформулировать в виде обычного графа с фиксированными ребрами: Для каждой вершины вы создаете кучу вершин - по одной на каждое входящее ребро и делаете из них ребра для каждого исходящего ребра нужной длины. Но это только если длина следующего ребра зависит только от одного предыдущего.
Не особо понимаю о чем вы, но звучит похоже на то что делаю я.
О боже, вам даже сам яндекс пишет "возможны неточности". Эти ИИ галюционируют. Но на будущее, не удивляйтесь, если ваши собеседники не будут в курсе, что за "иерархический" граф у вас.
Пусть пишет, я вам показал только на выдачу поиска, а первоначально я информацию читал в другом источнике. Вот вам ссылки на другие материалы с применением этого термина:
https://habr.com/ru/companies/JetBrains-education/articles/529432/
https://pco.iis.nsk.su/grapp/index.php?title=Иерархический_граф&mobileaction=toggle_view_mobile
https://github.com/Salagaeva/Graf
меня мало волнует если кто-то упоротый настолько что не в состоянии понять о чем речь, особенно когда вы разговариваете с незнакомым человеком, а не обмениваетесь мнениями в кругу коллег.
Нельзя взять произвольную функцию высчитывания длины пути, прикрутить ее к дейскстре, а потом ругаться, что дейкстра - плохой, медленный алгоритм.
Почему нельзя? Дейкстра пока не пришёл в вершину хотя бы один раз абсолютно ничего не знает об этой вершине и соответственно любые веса всех ребёр я могу менять как захочу в любое время, но как только вершина была взята в работу - эта возможность пропадает, что очевидно. Но тут вопрос, почему это очевидно мне, такому глупому, а неочевидно вам?
Вы его применили не там, не туда и не так, не понимая как он работает
Ну ваше мнение я услышал, но поскольку вы для меня неавторитетный собеседник по объективным причинам, то и рассматриваю я ваши слова сугубо из вежливости к дискуссии. Алгоритм Дейкстры не такой сложный чтобы я не разобрался в нём и не такой чтобы я не смог его модифицировать под себя. Как я уже сказал - основная проблема у дейкстры - это то, как будет реализовано отсечение вершин, это медленно. Я переделал так, чтобы стало быстрее, и не вижу, почему я не имею права сказать в таком случае что Дейкстра медленный, для меня это объективная оценка.
При этом ругаясь на "всяких как вы", которые вам что-то там не так сказали
Я не ругаюсь, я вам озвучиваю факты. Если у вас есть претензия к выбору алгоритма, то вы её адресуйте к точно таким же анонимусам в сети, которые точно так же как вы раздают горы бесплатных советов о том как же оно должно быть. Для меня и они и вы не более чем одно и то же лицо.
Я от вас лишь спустя несколько дней и кучу простыней текста узнал про такую вот маленькую незначительную деталь, что у вас не обычный взвешанный граф, а какая-то хитрая функция расстояния.
Ну изначально это константы так как работа над алгоритмом велась и многое менялось. Позже, после усложнения части, которая занимается кодированием у меня появилась потребность менять количество бит для кодирования исходя из предыдущего пути, ну как бы ведь в этом смысл кодирования (сжатия) - взять контекст и исходя из контекста придумать что-то, что выдаст нам меньше бит кода. Ну теперь это функция, не вижу ничего экстраординарного в этом, для Дейкстры это всё равно недостижимая информация, он про это ничего не знает и знать ему это не нужно. Учитывать при отсеивании вершин - легко, какая разница алгоритму что отсеивать? Добавили еще один if и всё. А ему легче, так как теперь вершин обходить в 2 раза меньше.
Ну да, граф необычный, а именно иерархический направленный взвешенный граф и никак иначе.
У вас граф же не дерево? В вершины же можно прийти несколькими способами с предыдущих "уровней"? Судя по вашим картинкам выше это так. Обычная рекурсивная функция ходя по этим ребрам придет в одну и ту же вершину несколько раз. Но, если у вас функция расстояния от пути классическая аддитивная, то можно результат работы функции не считать второй раз, ведь он будет точно такой же
Не дерево. В вершины можно прийти несколькими способами. Функция не придёт, точнее одна функция придёт по одному пути а другая по другому, причем вторая функция повлияет на то что дальше по иерархии исчезнет ребро. Я не знаю что такое "функция расстояния от пути" и "аддитивная". Результат работы второй раз никто и не считает, всё считается один раз. Ну если вы посчитаете его второй раз, то да, результат будет такой же, что очевидно (было бы странно если бы 2+2 в первый раз выдало 4, а во второй 4.1526).
Именно так и работает динамическое программирование
Ну может быть, я не знаю что это, поэтому не могу обсуждать, но видя что вы очень сильно неправильно делаете выводы о других вещах, не могу вам доверять в точности суждений.
Но, как вы пояснили, у вас все-таки какая-то сложная функция вычисления длины пути, так что этот метод тут не применим (Также, как и дейкстра).
Ну вот смотрите, у вас есть метод, который возвращает вес ребра. Вызов метода при вычислении в Дейкстре происходит элементарно:
int totalWeight += Method(array, i);int Method(int[] array, int index)
{
return array[index];
}Выше простой метод который возвращает константу. Но что мешает мне этот метод сделать более сложным? Дейкстра вообще не в курсе, он всегда получит свой int и будет работать с ним, какая разница как именно этот int сформирован?
Если у вас длина следующего ребра зависит только от одного предыдущего ребра, то вы еще можете применить тут дейкстру, построив обычный взвешанный граф на основе вашего. Иначе вы на вашем графе не можете запускать ни один из существующих алгоритмов поиска кратчайшего пути
Мне так нравится ваша категоричность ) Это называется - горе от ума.
Если вы там все-таки запустили дейкстру, то она каждую вершину может обрабатывать кучу раз
Вершина обрабатывается ровно до тех пор, пока не закончатся рёбра в неё ведущие, после этого вершина выпадает из списка.
и она действительно вырождается в перебор почти всех путей в графе. И поэтому работает так долго для такого маленького графа.
скорее перебор всех рёбер, но это его обязанность как бы, а зачем перебирать все пути? Ни в алгоритме ни в реализации вообще нет такого понятия как путь. Путь строится в конце из конечной точки к началу, собственно это и есть то ради чего всё затевалось. (да-да, я знаю что в Дейкстра пути можно взять в конце из любой вершины, но меня это не интересует же).
Единственный вариант решать вашу задачу через графы: у вас вершины в графе должны соответствовать всем возможным путям, и вам в этом очень большом графе надо запускать A*
Ну сейчас в каком то смысле у меня BFS с эвристикой, наверное это и есть A*, я тут спорить в названиях не стану, но в отличии от A*, где, как я помню, точность поиска пути напрямую завязана на эвристику, то есть путь совсем не обязательно будет оптимальным. У меня путь как раз оптимальный из коробки. Причем из особенности реализации я всегда имею два решения - быстрое и оптимальное. Эффективность быстрого на самом деле не сильно страдает, по тестам на разных типах файлов это в пределах 1-3%, но по скорости до 2х раз. Я даже свой Progress Bar делал, чтобы в одном боксе рисовать положение быстрого и оптимального результатов. Но это только на определенных данных где высокая вариативность, на чем-то не слишком хорошо сжимаемом разница по скорости практически отсутствует, но это очевидно, так как поиск оптимального и быстрого пути практически ничем не будут отличаться.
(не храня сам граф, конечно)
не знаю как у вас, но у меня сначала строится граф, это отдельный процесс хотя и довольно быстрый, а уже потом с самим графом работает алгоритм, так что как искать путь не имея входящих данных я не представляю. Граф это и есть то, что позволяет манипулировать файлом данных, без графа это просто набор байтов, а граф - это уже аналитика со своими свойствами.
Ну вы хотя бы дословно можете перевести слово List, но и доступно же определение, в чём спор?
Почитайте какую-нибудь книжку по структурам данных. Почитайте вашу же ссылку. Там написано: что этот List дает доступ по индексу. Ну и дальше в документации написано, что этот доступ идет за O(1). Так что это выглядит и крякает, как массив. Массив и есть. Динамический, правда, а не фиксированного размера, но от этого работа с ним не начинает тормозить. Максимум, там проверка выхода за границы массива. Вон, в С++ это называют vector. В java ArrayList.
Очевидно что массив быстрый, но дорого обходится изменение его размера
На самом деле не дорого. Ассимптотически за O(1).
С чего вы решили что задачи highload и задача с Дейкстрой
Ну я же попросил вас этот код в "задаче с дейкстрой" применить, а вы отказались, потому что у вас highload.
Путь состоит из рёбер, перебирая все рёбра вы переберёте все пути, в этом смысл Дейкстры.
Тут разница как в переборе кода на кодовом замке целиком или по цифре. Дейкстра перебирает только одно ребро в пути, находит лучшее и фиксирует его. Как если бы вы в замке по какому-нибудь щелчку могли понять, что вот вы первую цифру правильно набрали. И в итоге вам для отгадывания N цифр надо 10*N попыток а не 10^N. Всех путей в графе экспоненциально много, поэтому дейкстра, которая работает за полиномиальное время никак не может их перебирать.
Поэтому надо разделять, что вы там перебираете - все пути, или все ребра, продолжающие оптимальный путь в данной вершине.
Ну для вас смысла нет, а для меня есть, зачем мне перебирать 2 млн рёбер если я могу перебрать 1?
Скажите, как вы остекаете ребро даже не смотря на него? У вас какая-то особая структура графа, что вы в момент его построения можете заранее понять как не строить какие-то ребра? Причем сразу пачками? Если же у вас в коде есть хоть одна строчка, которая определяет, надо ли вот это ребро выкинуть, то вот вы уже на это ребро посмотрели. А сделали ли вы это один раз при отсечении ребра, или один раз внутри дейкстры - не особо большая разница.
Потом, у вас не столько отсечение ребер, сколько вы выбрасываете из рассмотрения какие-то вершины? Это значит, что у вас не задача найти пути до всех вершин, которую и решает лучше всего дейкстра, а задача найти путь до одной конкретной.
нет, это только добавляет условие. Принципы работы какие были такие и остались.
Вы понимаете, почему Дейкстра не работает, например, с отрицательными ребрами? Что в алгоритме сломается? Это же всего-лишь дополнительне условие!
Вот с изменением длин ребер в зависимости от прошлого пути сломается вот что:
Вот вы в алгоритме дейкстры делаете "релаксацию" ребра, когда обрабатываете какую-то вершину: если путь по ребру из вершины в следующую вершину короче чем то, что у вас записано, вы этот путь запоминаете как новый кратчайший. В обычных взвешанных графах вы тут просто берете и прибавляете длину ребра к пути. В вашем случае, раз у вас длина зависит от предыдущего ребра, вам надо взять весь путь. Ну и допустим в текующую вершину есть 2 пути, один длиной 10 через вершину A, другой длины 8 из вершины B. Вы запомните путь через B, так, ведь он короче?
Допустим ребро в следующую вершину будет длиной 10, если вы пришли из B и длиной 1, если вы пришли из А. Вот вы и начитаете путь длины 18 в следующую вершину, через B, хотя есть путь длины 11, через А. Потому что алгоритм дейкстры хранит только одно кратчайшее растояние до вершины, и пытается вот этот один кратчайший путь продолжить всеми ребрами.
Выше простой метод который возвращает константу. Но что мешает мне этот метод сделать более сложным? Дейкстра вообще не в курсе, он всегда получит свой int и будет работать с ним, какая разница как именно этот int сформирован?
Дейкстре важно, что этот int будет один и тот же независимо от того, как вы в вершину пришли. Зависит только от последней вершины в пути, и вершины в которую вы путь продолжаете. За счет этого допущения он позволяет себе фиксировать для каждой вершины один кратчайший путь и забывать про все остальные. Выше я привел пример, почему в вашем случае это делать нельзя. Может быть так, что кратчайший путь в вершину U + ребро UV не обязательно кратчайший путь в V через ребро UV. А это основной принцип на котором основан алгоритм - он хранит только кратчайший путь в каждую вершину. Потому что в взвешанных графах не важно, как вы в вершину пришли: если вам нужно получить кратчайший путь через вершину, вы можете просто продолжыть самый короткий путь в нее.
Вершина обрабатывается ровно до тех пор, пока не закончатся рёбра в неё ведущие, после этого вершина выпадает из списка.
Это в нормальной дейскстре. В вашем графе может быть что угодно. Ибо, если запустить на вашем графе обычную реализацию, она найдет не оптимальный путь, а восстановление ответа вообще может зациклится.
не знаю как у вас, но у меня сначала строится граф, это отдельный процесс хотя и довольно быстрый, а уже потом с самим графом работает алгоритм, так что как искать путь не имея входящих данных я не представляю.
Граф, где вершины - это все возможные пути - он слишком большой, чтобы его в память засунуть. Но A* не надо знать весь граф целиком для работы. Ему надо лишь уметь получать ребра исходящие из заданной вершины. Их можно генерировать на лету. Берете текущий путь, продолжаете всеми возможными способами, смотрите в какой-нибудь хеш-таблице, какой номер у вершины для получившегося пути. Если его там нет, назначаете следующий свободный номер. В результате весь этот расширенный граф не хранится, а хранятся только данные относящиеся к вершинам, которые алгоритм посетил. За счет отсечения A* посещает лишь малую долю вершин.
Почитайте какую-нибудь книжку по структурам данных
Вы адресуйте эти предложения тем кто его так назвал. Это список, в описании он фигурирует как список, не вижу смысла об этом спорить, если внутри он является динамическим массивом - да ради бога, от этого он не перестаёт называться списком.
но от этого работа с ним не начинает тормозить
А вы им пользуетесь?
Вон, в С++ это называют vector. В java ArrayList.
Мне абсолютно фиолетово что где как называется вне рамок разговора.
На самом деле не дорого. Ассимптотически за O(1).
Вы точно понимаете о чем пишете? В C# любое изменение размера массива приводит к выделению памяти для нового, копированию данных из старого и удаления старого (не сразу конечно, а как там сборщик мусора решит).
Ну я же попросил вас этот код в "задаче с дейкстрой" применить, а вы отказались, потому что у вас highload.
Я не знаю как в вашей жизни всё устроено, но я не занимаюсь программирование тогда, когда кто-то в сети прокукарекал.
Тут разница как в переборе кода на кодовом замке целиком или по цифре. Дейкстра перебирает только одно ребро в пути, находит лучшее и фиксирует его. Как если бы вы в замке по какому-нибудь щелчку могли понять, что вот вы первую цифру правильно набрали. И в итоге вам для отгадывания N цифр надо 10*N попыток а не 10^N. Всех путей в графе экспоненциально много, поэтому дейкстра, которая работает за полиномиальное время никак не может их перебирать.
Аналогия мне непонятна. Дейкстра берет веса всех рёбер что есть в графе, он в принципе не сможет ничего посчитать если этого не сделает, а значит если в графе N рёбер, то и будет N действий, откуда там взяться N в квадрате я вас не понимаю.
Поэтому надо разделять, что вы там перебираете - все пути, или все ребра, продолжающие оптимальный путь в данной вершине.
Перебирая все рёбра я переберу все пути автоматически, вы можете задать любой критерий оптимальности и получить результат. То что у вас в самом конце не будет возможности брать любой из путей - это логичное следствие работы моего алгоритма, так как он перебирая пути смотрит на выполнение условия функции, а функция может делать что угодно.
Скажите, как вы остекаете ребро даже не смотря на него? У вас какая-то особая структура графа, что вы в момент его построения можете заранее понять как не строить какие-то ребра? Причем сразу пачками? Если же у вас в коде есть хоть одна строчка, которая определяет, надо ли вот это ребро выкинуть, то вот вы уже на это ребро посмотрели. А сделали ли вы это один раз при отсечении ребра, или один раз внутри дейкстры - не особо большая разница.
То есть для вас нет разницы будет ли работа идти сейчас с 2 млн рёбер, потом с 1, потом с 200к, потом 50к и т.д.? Вас устроит что работа всегда идёт с 2 млн ребёр с последовательным отсечением тех что обработаны? Здесь всё точно так же как в ситуации с черепашками, вы все черепашки проходите, а я выкидываю ненужные. Вот и получается у меня с рёбрами:
2000К -> 1000K -> 200K -> 50K
а у вас
2000K -> 1999K -> 1998K -> 1997K
Потом, у вас не столько отсечение ребер, сколько вы выбрасываете из рассмотрения какие-то вершины? Это значит, что у вас не задача найти пути до всех вершин, которую и решает лучше всего дейкстра, а задача найти путь до одной конкретной.
Не важно что нужно мне, важно что делается это медленно.
Вы понимаете, почему Дейкстра не работает, например, с отрицательными ребрами? Что в алгоритме сломается? Это же всего-лишь дополнительне условие!
Абсолютно всё равно почему, я отрицательные веса рёбер не использую.
Вот с изменением длин ребер в зависимости от прошлого пути сломается вот что:
Вот вы в алгоритме дейкстры делаете "релаксацию" ребра, когда обрабатываете какую-то вершину: если путь по ребру из вершины в следующую вершину короче чем то, что у вас записано, вы этот путь запоминаете как новый кратчайший. В обычных взвешанных графах вы тут просто берете и прибавляете длину ребра к пути. В вашем случае, раз у вас длина зависит от предыдущего ребра, вам надо взять весь путь. Ну и допустим в текующую вершину есть 2 пути, один длиной 10 через вершину A, другой длины 8 из вершины B. Вы запомните путь через B, так, ведь он короче?
Вес зависит от того откуда вы пришли. Вы прибавляете к оптимальной длине маршрута вес ребра. Зачем мне брать весь путь? Да, я запонмю путь из вершины Б длиной 8.
Допустим ребро в следующую вершину будет длиной 10, если вы пришли из B и длиной 1, если вы пришли из А. Вот вы и начитаете путь длины 18 в следующую вершину, через B, хотя есть путь длины 11, через А. Потому что алгоритм дейкстры хранит только одно кратчайшее растояние до вершины, и пытается вот этот один кратчайший путь продолжить всеми ребрами.
Нет, такие коллизии невозможны, именно поэтому из оригинальных данных строится граф на первом этапе, он учитывает все условия и если такая коллизия могла бы появиться то алгоритм просто не создаёт их в принципе, то есть у вас всегда будет путь через Б отдельно от пути через А, они не встретятся. Если смотреть картинку выше то там видно как из одной вершины выходит масса рёбер, вот тут как раз и происходит магия.
Дейкстре важно, что этот int будет один и тот же независимо от того, как вы в вершину пришли
Он и будет один и тот же, если бы он имел возможность в этой вершине быть более чем одним значением, то у вас было бы две разные вершины и соответственно пути не пересекутся. Это делается в самом начале до запуска Дейкстры.
В вашем графе может быть что угодно. Ибо
А вы уже спец по моим графам? XD Судя по написанному вы не понимаете что происходит и пытаетесь придумать какое-то решение исходя из той скудной информации что узнали.
Граф, где вершины - это все возможные пути - он слишком большой, чтобы его в память засунуть
Если вы про что-то своё пишете, то там может быть что угодно, а для моего решения вы не сможете получать новую вершину по ходу действия, так как появление такой вершины зависит от прохода от начала до текущего элемента данных, а значит генерация каждой вершины будет требовать прохода от начала. Можно конечно как-то хитро кешировать прошлые вершины в местах ветвлений и считать от них, да, я думаю можно так сделать, но для меня 2 Гб ОЗУ не та цена. Думаю я просто увязну в дебаге этого кода.
Вы точно понимаете о чем пишете? В C# любое изменение размера массива приводит к выделению памяти для нового, копированию данных из старого и удаления старого (не сразу конечно, а как там сборщик мусора решит).
Именно по этому почти во всех популярных языках есть динамический массив, реализующий одну и ту же идею: есть две величины capacity и length. Последняя -- это реальное количество элементов, первая -- это текущий размер массива, где элементы хранятся. Выделение памяти происходит только если мы пытаемся добавить элмент при length=capacity, в этом случае capacity увеличивается в два раза. Соответственно с таким подходом количество аллокаций при добавлении N элементов -- это log(N), количетсов перемещений <= 2N. Конкретно в List<T> эта логика реализована вот тут, аллокации вот тут.
Как уже было сказано, в C++ это std::vector, в Java ArrayList, в Python это стандартный список. Идея является стандартом индустрии и поэтому почти ни у кого не возникает опасений о том, что добавление в массив -- это постоянные переалокации.
Вы точно понимаете о чем пишете? В C# любое изменение размера массива приводит к выделению памяти для нового, копированию данных из старого и удаления старого (не сразу конечно, а как там сборщик мусора решит).
Вам выше уже написали. Понимаю. Почитайте про свойство capacity у этого list. Пока добавляемые элементы помещаются в capacity, все происходит за O(1). Если нет, то вот тогда происходит реаллокация. Но трюк в том, что выделяемый размер примерно удваиваится. В результате, если вы в массив N раз чего-то добавили у вас суммарно будет выделено максимум 2N байт памяти за log(N) аллокаций и все элементы суммарно будут скопированы максимум 2N раз. Что дает в среднем O(1).
Аналогия мне непонятна. Дейкстра берет веса всех рёбер что есть в графе, он в принципе не сможет ничего посчитать если этого не сделает, а значит если в графе N рёбер, то и будет N действий, откуда там взяться N в квадрате я вас не понимаю.
N обычно обозначают количество вершин, но ладно. Дейкстра выполняет O(V log V + E) операций. Но в графе O(V^V) путей. Не квадрат, а в степени. Если считать за N ребра, то путей получается O(sqrt(N)^sqrt(N)). Например полный граф, тут количесество путей - это все упорядоченные наборы разных чисел от 1 до V, ведь вы можете в каком угодно порядке обходить какие хотите вершины. Их O(V!). Так что дейкстра никак не может рассматривать все пути, их на много много порядков больше чем ребер. Еще раз аналогия - комбинаций в замке с N цифрами - 10^N. Но, если вы умеете по началу комбинации понимать правильная ли она, то вы можете подобрать код за 10*N операций. На много порядков быстрее, фиксирую правильные цифры слева на право. Вот и Дейкстра так же: вместо перебора всех путей, он перебирает только "начала" путей, фиксируя кратчайшие пути и продлевая их. Но это работает только если кратчайший путь в вершину V через U точно совпадает с кратчайшим путем в U в начале.
Перебирая все рёбра я переберу все пути автоматически, вы можете задать любой критерий оптимальности и получить результат
Нет. Еще раз, кодовый замок: Вы не перебираете комбинации, вы перебираете только одну цифру. Вот попробовали вы цифры 0-9 в самой первой позиции, услышали щелчек на цифре 7 - вы знаете, что код начинается с 7. Вы уже не будете перебирать 9*10^(N-1) комбинаций, начинающихся с любой другой цифры. Так же и дейкстра - он никогда не перебирает заведомо не оптимальные пути. Найдя один кратчайший путь в какую-то вершину он уже никогда не будет перебирать ни один путь, проходящий через эту вершину и не начинающийся точно так же. Именно так он среди O(V^V) путей находит лучшие всего-то за O(VlogV + V^2) операций.
Нет, такие коллизии невозможны, именно поэтому из оригинальных данных строится граф на первом этапе, он учитывает все условия и если такая коллизия могла бы появиться то алгоритм просто не создаёт их в принципе, то есть у вас всегда будет путь через Б отдельно от пути через А, они не встретятся.
У вас в одну и ту же вершину можно прийти разными способами. Это видно на картинке. И вы сами сказали, что длина следующего ребра из этой вершины зависит от всего пути, вы сами сказали.
Я так понимаю, количество бит, чтобы закодировать кусок данных, сответсвующий ребру, зависит от того, что у вас там в словаре уже раньше записано, а это определяется ребрами, по которым вы сюда пришли. И вполне может быть так, что записав ту же самую прошлую часть файла но менее оптимально, у вас можно следующий кусок закодировать гораздо компактнее. Это именно так коллизия, о которой я рассказал.
Он и будет один и тот же, если бы он имел возможность в этой вершине быть более чем одним значением, то у вас было бы две разные вершины
Но тогда длина ребра не зависит от того как вы в вершину пришли, почему вы говоли выше, что зависит? Вы же писали, что длина может быть разной:
Ну так и смысл функции в том чтобы учитывать прошлые ребра, прошли по A-B у вас путь B-C стал 10, прошли E-B у вас путь B-C стал 7. То есть важно откуда вы пришли.
Если же у вас для этих двух случаев будут разные вершины, то у вас вершины графа соответствуют различным путям в графе, и вы тут путаете два графа. В первом графе у вас вершины соответствуют, я полагаю, позициям в файле, а ребра - записи куска файла. Тут длина зависит от того, как вы в вершину пришли. И есть второй граф, где вы каждому возможному пути в первом графе ставите в соответстве вершину. Этот второй граф будет взвешанным, в нем длина ребра константна, и на нем можно запускать Дейкстру. Это именно тот граф, на котором я вам предложил запускать А*.
Вот и Дейкстра так же: вместо перебора всех путей, он перебирает только "начала" путей, фиксируя кратчайшие пути и продлевая их
мне кажется это вопрос терминологии. для меня "перебрать" - это учесть в алгоритме, а не запустить цикл на все элементы. Если алгоритм может выполнить 10 действий и получить результат эквивалентный полному перебору в 1000 элементов, то алгоритм перебирает все маршруты, а как он это делает и с какой скоростью уже не важно. Если бы Дейкстра не перебирал все маршруты, то он и не мог бы их предъявить, это же очевидно.
Нет. Еще раз, кодовый замок
Да-да, это вопрос того как вы понимаете слово "перебирать", ваш алгоритм нахождения кода замка базируется на щелчках, фиксируя щелчки вы следуете определенному алгоритму и перебираете все комбинации, которые и приводят вас к результату, если бы вы пропустили хоть одну - то вы не нашли бы искомое.
У вас в одну и ту же вершину можно прийти разными способами. Это видно на картинке. И вы сами сказали, что длина следующего ребра из этой вершины зависит от всего пути, вы сами сказали.
Я знаю что сказал, и на картинке вы видите то, где работал Дейкстра, картинки, которая изображает граф для работы моей реализации у меня просто нет. Конкретно эту картинку рисовал не я, я списывался с владельцем сайта и он добавлял отрисовку такого вида графа. Нарисовать сам такое я не смогу, а нарисовать то, о чем я говорю как о своей реализации алгоритма - не смогу тем более. Ближайшая графическая аналогия - мышцы человека - много параллельных независимых линий, которые иногда могут встречаться вместе в одном узле. Смысл разделения веток именно в невозможности встретиться разным частям друг с другом, чтобы не было коллизий. Если алгоритм пошёл по одной ветке то он будет идти по ней до общего узла (которого может и не оказаться до конца графа). Чем выше вариативность данных, тем больше параллельных нитей. На рисунке выше в алгоритме присутствует только два типа данных - литерал (это просто чистый символ, на рисунке это одинокий узел соединённый ребром вниз по прямой) и ссылка на предыдущие данные (это представлено выгнутым ребром).
Я так понимаю, количество бит, чтобы закодировать кусок данных, сответсвующий ребру, зависит от того, что у вас там в словаре уже раньше записано, а это определяется ребрами, по которым вы сюда пришли. И вполне может быть так, что записав ту же самую прошлую часть файла но менее оптимально, у вас можно следующий кусок закодировать гораздо компактнее. Это именно так коллизия, о которой я рассказал.
нет там коллизий. не придумывайте что-то сами.
Но тогда длина ребра не зависит от того как вы в вершину пришли, почему вы говоли выше, что зависит?
Потому что вы не понимаете как это работает. У вас 2843756563738 веток, вы проходите по ним одновременно и имеете на руках результат, который влияет на то, сколько веток будет дальше, что-то будет удалено навсегда, что-то поменяет вес. На следующем шаге всё повторяется. Никто не возвращается назад, никогда никто не приходит из одной ветки в другую. В единицу времени у вас будет быть только меньше веток чем было изначально, новые ветки не добавляются.
Представьте сеть параллельных путей железных дорог, которые иногда пересекаются и на равных интервалах, например в 1 км у вас станции выстроенные по линейке, все поезда выезжают одновременно и проезжают своё расстояние вместе, но скорость у всех разная (это и есть вес). Таким образом один из поездов может по своей ветке проехать мимо 10 других станций, а остальным поездам придется на них останавливаться. Когда он приедет на свою станцию он оставит информацию о себе, когда придет туда другой поезд (или 500 поездов) то он/они будут сверяться с теми, кто там был до них и если их вес выше, то эти поезда будут просто сняты с линии. Если поезд приехал в узел и там 2 пути, то он запустит своё клон по второму маршруту.
Вообще когда я писал свою реализацию то я убрал из обращения и поезда и ветки, у меня всё происходит только с самими узлами. Узлы знают в какой следующий узел можно попасть из этого, а вот узел, который будет оптимальным у них всего один и он меняется в зависимости от приехавшего поезда.
В коде это выглядит вот так:
public class Node
{
public int ParentThreadId { get; set; }
public int SelfThreadId { get; set; }
public int Weight { get; set; }
public bool Delete { get; set; }
public Node MinPathParentNode { get; set; }
public CodeSequence cs { get; private set; }
public Node(int _parentthreadid, int _selfthreadid, CodeSequence codeSequence, int weight, bool delete = false)//, CodeSequenceRecord id)
{
ParentThreadId = _parentthreadid;
SelfThreadId = _selfthreadid;
Weight = weight;
Delete = delete;
this.cs = codeSequence;
}
public Node()
{
}
}
public class CodeSequence
{
public int id { get; set; }
public int letterpos { get; set; }
public int currentpos { get; set; }
public int len { get; set; }
public int elias { get; set; }
public LiteralType litType { get; set; }
public CodeSequence(int ID, int LETTER_POS, int CURRENT_POS, int LEN, int ELIAS, LiteralType LT)
{
id = ID;
letterpos = LETTER_POS;
currentpos = CURRENT_POS;
len = LEN;
elias = ELIAS;
litType = LT;
}
public CodeSequence(int ID, int LETTER_POS, int CURRENT_POS, int ELIAS) // literal
{
id = ID;
letterpos = LETTER_POS;
currentpos = CURRENT_POS;
len = 1;
elias = ELIAS;
litType = LiteralType.Literal;
}
};Node - узел, которым я манипулирую с помощью алгоритма, а CodeSequence - это описание типа данных. Это код, с которым работал Дейкстра, тут ничего секретного, а код с которым работает мой алгоритм я не публикую (да я и это показал лишь потому что оно имеет нулевую ценность и для меня и для вас, здесь по сути то что вы можете встретить например в исходниках ZX0, не в таком виде конечно, но тип данных схожий).
Если же у вас для этих двух случаев будут разные вершины, то у вас вершины графа соответствуют различным путям в графе, и вы тут путаете два графа. В первом графе у вас вершины соответствуют, я полагаю, позициям в файле, а ребра - записи куска файла. Тут длина зависит от того, как вы в вершину пришли. И есть второй граф, где вы каждому возможному пути в первом графе ставите в соответстве вершину. Этот второй граф будет взвешанным, в нем длина ребра константна, и на нем можно запускать Дейкстру. Это именно тот граф, на котором я вам предложил запускать А*.
Нет, ничего такого нет и близко.
Вы читали ваши ссылки-то?
Я много чего читал и как-то не замечал проблем с таким термином. Не нравится то что нагуглил - ищите сами, я не навязываю вам этот термин. Вот что выдал ИИ:
@malkovskyхорошо, мне неправильно объяснили работу List в C#, буду иметь в виду, что не всякий, считающий себя умным анонимус в интернете - прав. Осталось только понять как вас всех сортировать. Тот же @wataru уже спорил со мной по черепашкам, аж пришлось целую статью писать чтобы показать что он не прав, что не мешает ему продолжать настойчиво учить меня.
https://habr.com/ru/companies/JetBrains-education/articles/529432/
https://pco.iis.nsk.su/grapp/index.php?title=Иерархический_граф&mobileaction=toggle_view_mobile
Вы читали ваши ссылки-то?
В первой статье иерархия исходит из строки, над которой строится граф, ведь подстроки можно организовать в некоторую иерархию по вложению. Это не какой-то тип графа. И там нет никакого определения иерархических графов.
По второй ссылке действительно есть некоторое определение, вот только оно к вашему графу не имеет никакого отношения. Там иерархия - это отдельная структура, заданная над графом - дерево, в которое организованы "фрагменты", подграфы исходного графа. При чем этому определению вполне подходят и графы с циклами, где нельзя, как вы говорите "выстроить вершины по уровням".
Третья - какой-то студент отсебятину какую-то написал.
Например во многих алгоритмах при описании есть фраза "берём оставшиеся", а при реализации получается так, что чтобы взять те самые оставшиеся нужно сломать мозг, так как на пальцах всё красиво, а на деле всё не так просто.
Направление мысли верное, но выводы не до конца точные.
Давайте в качестве примера.
array[0] + array[1] может работать на порядки быстрее чем array[0] + array[1000000000], потому что array[0] и array[1] скорее всего будут находиться в одной кэш-линии, а во втором случае мы вылетаем даже за L3 кэш.
Таких загагулин в современных процессорах вагон и парочка тележек. Конвейеры, предсказание ветвлений, префетч памяти и т.д.
Поэтому выбор правильного алгоритма - только первый шаг. Дальше, если производительность проседает неадекватным образом, обычно смотрят почему, а не сразу меняют алгоритм. Для этого существуют инструменты профилирования, которые показывают какие участки кода занимают наибольшее время (в идеале - результирующего, ассемблерного кода). Также они часто могут показывать с чем это связано, например, отдельно можно профильтровать выходы за кэш, ошибки предсказания ветвления и так далее.
Алгоритмы часто могут быть ускорены и замедлены на порядки тем, как именно данные "упакованы" в памяти и как (в том числе в каком порядке) к ним осуществляется доступ.
При этом так же отмечу, что поскольку у вас некоторый частный случай, разумеется, в этом частном случае может существовать (а может и не существовать) алгоритм, который ведёт себя лучше.
Но в общем случае, когда о данных ничего не известно, Дейкстра вполне себе оптимален (а как показано в статье, не вполне себе, а оптимален).
Кстати, я только обратил внимание, что вы используете Фибоначчиеву кучу, на wiki поговаривают, что с ней не всё так однозначно:
скрытые константы в асимптотических оценках трудоёмкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные (d-ичные[англ.]) кучи на практике эффективнее.
Альтернативами им служат толстые кучи, тонкие кучи и кучи Бродала[англ.], обладающие теми же асимптотическими оценками, но меньшими константами[4].
Ну скиньте тогда через Pastebin, облачный диск какой-то, способов делиться кодом нынече масса...
Скиньте ссылку на репозиторий, пожалуйста
Очень интересная оригинальная статья. Жаль, что ни этот перевод, ни её оригинал не отражают её сущности. Попробую взять на себя роль пояснительной бригады.
Есть алгоритм Дейкстры. Он ищет кратчайшие пути от одной вершины до всех остальных в графе с неотрицательными рёбрами. В процессе работы он переберает каждую вершину и каждое ребро ровно один раз. Теоретически он мог бы работать за O(n+m) -- лучшую асимптотическую оценку не получить ибо это размер входных данных, тем не менее ни одна реализация алгоритмы Дейкстры её не достигает.
Попутно с нахождением кратчайших путей алгоритм Дейкстры также косвенно упорядочивает все вершины по отдалению от исходной вершины. Если предположить, что веса рёбер можно только складывать и сравнивать, то нижняя оценка Дейкстры ухудшается до O(nlogn+m), так как задача упорядочивания вершин в топологии "звезда" эквивалентна сортировке, которую при использовании только сравнений нельзя решить быстрее nlogn. Оценка O(nlogn+m) для Дейкстры достигается при использовании кучи Фибоначчи в качестве очереди с приоритетом.
Оценка O(nlogn) неулучшаема для звезды, но очевидным образом, если граф -- один единственный путь, то там легко получить упорядочивание за линейный проход. Вот здесь кроется тонкость в понимании оптимальности оригинальной статьи (universal optimality). Если обозначить за OPT(G) минимальное число сравнений задачи упорядочивания вершин по отдалению от заданной для фиксированной топологии G (минимум берётся по всем возможным весам ребер в этой топологии), то Дейкстра со специальной кучей работает за время O(OPT(G)+n+m), т.е. например для линейного графа он сделает линейное число O(n) сравнений, а не O(nlogn).
Специальная куча -- это "Fibonacci-like priority queue with the working set property". Её отличие от обычной кучи Фибоначчи в том, что удаление минимума делается не за logn, где n -- количество элементов в куче на момент удаления, а log W(x), где x -- удаляемый минимум, а W(x) -- количество элементов, которые попали в очередь после х и еще находятся в ней на момент удаления. Построение такой кучи -- значительная часть статьи и скорее всего она относится к галактическим алгоритмам
Дейкстра. Он такой один.
Учёные нашли оптимальный способ обхода графа