Здравствуйте, коллеги!
В последнее время меня серьезно беспокоят матрицы.
Но не все, а матрицы смежности для представления графов.
В частности нахождение минимального остовного дерева в неориентированном взвешенном графе.
Например алгоритмом Прима.
Всё было бы хорошо, если бы не неприятие стандартного решения, когда мы бесконечность обозначаем большим числом.
Мне кажется это как–то неэтично. Как серпом по клюкве. Тяжёлые антибиотики не дают мне мыслить здраво, поэтому не поговорит ли кто со мной об этом?
Ведь можно булевыми эт самое…
Наверное. Или нет.
Спасибо, пожалуйста, извините.
Паранормальное/мозги напрокат/музыка
GD Star Rating
loading...
loading...
так ты ж считать это будешь на компьютере всё равно? на эвм это вполне приемлимо, там диапазон счёта как правило ограниченный и поэтому можно выбрать число, которое будет заведомо больше.
вот как бы для частного случая это решение, а для общего–некорректно, так как нет ограничения по входным данным.
мне просто не нравится этот вариант. хочу как –то иначе.
всё что могу, в данном случае это, — прислать чернил и бумаги…)
и линекса, апосля антибиотиков попей, + витаминку С на первой неделе. выздоравливай, лучиков (:
если вдруг кого обеспокоит таже фигня что и меня, то решение в частном случае будет:
представляем массив данных в виде двух матриц: смежности и матрицы весов.
далее простое if.
практический смысл возникает тогда, когда мы проверяем входные данные на длину числа веса ребра и вводим ограничение исходя из возможностей используемой памяти.
другой вопрос, что это всего лишь более строгое решение в качестве логики.
и в таких случаях как алгоритм дейкстры — просто никак.
но если кто сможет осилить реализацию алгоритма дейкстры без использования бесконечности — дайте знать.
(:
для антибиотиков отходняк слишком длинный…
возможно это пмс и гормональное.
но реализация дейстры без использования бесконечности пока не найдена в принципе.
но вдруг у кого что найдётся из идей.
но реализация дейстры без использования бесконечности пока не найдена в принципе.
Вот вам слету приблизительный вариант Дейкстры. О каких бесконечностях вообще речь?
pq.push(source, 0)
while (not pq.empty()) {
___(node, d) = pq.pop()
___yield(node, d)
___visited[node] = true
___for (v in node.neighbors()) {
______if (not visited[v]) pq.push_or_update(v, d + dist(node, v))
___}
}
эмнь.
что то он не шибко похож на дейкстру.
вы можете переписать это в псевдокоде?
Девушка, вы с каждым комментарием все забавнее и забавнее.
Вам в каком псевдокоде?
вобщепринятом
Девушка, вы прочитали Википедию, но не поняли суть алгоритма.
Я привел вам именно тот самый алгоритм, только в нормальном его виде.
Вариант в Википедии вместо priority queue использует фиксированный массив d[], который он инициализирует какими–то гипотетическими бесконечностями. Но позвольте заметить, что
* Значок «бесконечности» там обозначает просто отсутствие значения. С тем же успехом можно проставить null.
* На практике никто с таким вот фиксированным массивом не работает. Нужен priority queue, как я указал выше.
* Вообще Википедийный способ описания алгоритма Дейкстры, на мой взгляд, довольно плох, т.к. он скрывает суть концепции «проход по графу». Было б время и большое желание, переписал бы статью, да лень сейчас, честно говоря.
Вот вам задачка для общего развития:
* Напишите алгоритм прохода графа в ширину. Назовем его алгоритм А.
* Замените в алгоритме А одну строчку так, чтобы он стал проходом графа в глубину.
* Замените в алгоритме А две–три строчки так, чтобы он стал алгоритмом Дейкстры.
* Замените в алгоритме А две–три строчки так, чтобы он стал алгоритмом поиска A*.
данный алгоритм оперирует понятиями минимума и максимума.
максимум нам нужен чтобы отбросить не–кратчайший путь.
то что вы пишете очень симпатичный велосипед, но это не оно.
плюс увеличение временной сложности.
если вы уверены в своей правоте — попробуйте переписать программу на более низком уровне.
ОК. Упирайтесь и ищите ваши бесконечности дальше. Я не способен помочь человеку, который сам не хочет чтобы ему помогли. Когда надоест упираться, вернитесь, перечитайте мой симпатичный велосипед и подумайте над предложенной там задачкой.
В качестве последней наводки спрошу вас еще, как конкретно вы планируете находить в шаге 3 вершину, имеющую минимальный вес? Неужто перебирая каждый раз весь массив t?
да не нужна мне помощь.
та задача где мне максимум не понравился, решается через структурирование данных.
преобразовать алгоритм дейкстры без использования максимального значения — невозможно.
потому что алгоритм такой.
именно поэтому существует огромное количество других алгоритмов поиска кратчайшего пути.
так о чём разговор–то в итоге?
картинка в тему выпала:
это была типа шутка юмора.
но кажется хреновый из меня петросян.
да не нужна мне помощь.
Да вообще–то нужна на самом деле
именно поэтому существует огромное количество других алгоритмов поиска кратчайшего пути
Ах вот оно как оказывается–то! А пацаны–то и не знали!
Можно число для бесконечности в зависимости от входных данных генерировать (как сумму модулей рёбер + 1, например). Это сузит ограничения, ну и ладно.
> Всё было бы хорошо, если бы не неприятие стандартного решения, когда мы бесконечность обозначаем большим числом.
Ну используй опцион, если нет чего–то вроде Double.PositiveInfinity. Язык программирования в посте не указан; можно взять :option<T> ежели C++, или ‘T option в случае F#, или Maybe monad если Haskell.
спасибо.
приятно, когда тебя понимают.
S4off> Можно число для бесконечности в зависимости от входных данных генерировать (как сумму модулей рёбер + 1, например).
Это в общем случае операция порядка квадрата числа вершин.
Если у нас граф хранится матрицей смежности, то O(v^2) нас уже не пугает. Всё равно все пары просматривать придётся при апдейтах (точнее, либо просматривать, либо отклонять по проверке на то, что кратчайший путь до вершины уже сосчитали). А если граф хранится списками соседей или списком рёбер, то бесконечность вообще не нужна.
Более того, если, к примеру, данные надо прочитать, а не получить готовой матрицей, то можно сразу это число и сосчитать.
Пожалуйста. Кстати, решение товарища Peels тоже вполне подходит. У него там C++ и d_ary_heap из библиотек Boost.
У меня там не столько С++ сколько псевдокод (хотя мадам забраковала ибо некошерный у меня псевдокод видите–ли), в котором используется абсолютно классическая дубовая priority queue которая, если уж о C++ говорить, есть даже в STL. Без нее реализовывать алгоритм Дейкстры — тупак, простите.
Вопросы того, почему некоторые переменные иногда в процессе работы алгоритма должны принимать значение null или что–либо аналогичное — тоже тупак.
Ну и наконец то, что в Википедии (да и вообще много где) принято писать недосказаниями и загадками об алгоритме Дейкстры и тем самым смущать умы юных дам — прискорбно.
я так вижу что кроме гендерного вопроса аргументов нет вообще.
после того как мальчик, у которого самовлюбленность и уверенность в собственной божественности перестанет щипать глаза, посмотрит например в учебник Новикова, то может быть хоть капля сомнений появится, или мысль какая, что есть нюанс.
да, кстати, ещё где–то в 70–х годах стали печататься в СССР книги по инженерному анализу и никто не использовал термин data mining.
есть ещё книги по теории вычислительных процессов.
там вообще вместо алгоритмов формулы какие–то. ужас–ужас какой тупак и никаких сиплюсплюсов.
Если совсем точно, то нужна не очередь с приоритетами, а отсортированный словарь. Либо очередь из пар с компаратором, который сравнивает по первому элементу пары.
Ну а push_or_update — уж больно хитрый метод, которого, по–моему, нигде нет, кроме :d_ary_heap_indirect. Если контейнерами из STL реализовывать (например, map для словаря или priority_queue для очереди) или любой другой классической priority queue, то вместо него код подлиннее надо будет написать.
Хм, а для словесного описания алгоритма (без кода) граф и метки с бесконечностями (можно назвать их отсутствием пути или как угодно ещё) вполне подходят, по–моему.
Когда ты приводишь человеку в ответ на просьбу «поговорить с ней об этом» конкретный псевдокод конкретного алгоритма Дейкстры, в котором, о боже, оказывается и не нужно использовать столь ненавистные значки бесконечности, а он тебе начинает в ответ говорить что это не псевдокод оказывается, да и «не похоже» на алгоритм Дейкстры вообще потому что Википедия ему что–то там нашептала, а потом еще дундеть что–то про гендерные аргументы и какую–то божественность и учебник Новикова, возникают некоторые сомнения в адекватности собеседника.
Девушка, если вам говорят что вы пишете тупак, не надо первым делом думать что это случилось лишь потому что вы — девушка, вас хотят оскорбирь грубые мужланы, и вокруг ужасная половая дискриминация. Задумайтесь хотя бы о возможности того, что вы реально написали тупак.
Зачем я должен смотреть в какой–то там учебник какого–то Новикова, причем здесь 70е годы, теории вычислительных процессов и формулы с сиплюсплюсами я не вкурил, честно говоря, поясните. Вы там тоже нашли какой–то значок бесконечности, который вас волнует?
push_or_update это псевдокод, детальность которого примерно на том же уровне что и «найдем u[i] с минимальным значением» в конкурирующих источниках, только учитывая специфику структуры данных, тут понятно как это происходит и с какой сложностью реализация. Очередь можно реализовать и поверх отсортированного словаря, да, но это все равно будет по сути очередью.
Голым STL–ом операцию push_or_update делать конечно не очень удобно, но на практике для большинства встречающихся на практике типов графов (те, которые sparse) достаточно использовать обычный push() и добавить в начало while цикла проверку «if visited[node] continue». В результате некоторые вершины будут впихнуты в очередь по нескольку раз, тем самым добавляя лишних циклов, но т.к. взамен в алгоритме не нужно будет использовать push_or_update суммарно алгоритм будет работать даже быстрее.
«Девушка, если вам говорят что вы пишете тупак, не надо первым делом думать что это случилось лишь потому что вы — девушка, вас хотят оскорбирь грубые мужланы, и вокруг ужасная половая дискриминация. Задумайтесь хотя бы о возможности того, что вы реально написали тупак.» Золотые слова.
Если считаете уважаемого Peels’а идиотом, то рекоммендую обратиться к какой–нибудь солидной литературе. Желательно с систематичесим изложением алгоритмов (Кормен, например). Боюсь, правда, что все подобные книжки писали тоже злые мужики, пытающиеся обидеть девушку.
Честно сказать, до сих пор считаю, что сей пост – — толстый троллинг.