Я использую STL priority_queue в качестве структуры данных в моем графическом приложении. Вы можете смело считать это продвинутой версией алгоритма связующего дерева Прима. С помощью алгоритма я хочу эффективно найти узел в очереди приоритетов (а не только минимальный узел). [Это необходимо, потому что стоимость узла может измениться и должна быть исправлена в priority_queue] Все, что мне нужно сделать, это увеличить priority_queue и проиндексируйте его также на основе ключа моего узла. Я не считаю, что это можно сделать в STL. Может ли кто-нибудь лучше понять, как это сделать в STL?
увеличение / индексирование priority_queue в STL
14.11.2013
- Вместо этого вы можете использовать
std::map... более медленную и большую фрагментацию / использование памяти. Я не думаю, что вы можете делать то, что хотите, сpriority_queue. 15.11.2013 - @Dave Map не является решением, мне все время нужно находить минимальный ключевой узел. Карта этого не делает. 15.11.2013
- Тоже самое:
myMap.begin()- именно такой узел. 15.11.2013 - @ Игорь, нет, это не так. Мне нужно: 1) найти минимально взвешенный узел (обычно выполняется через очередь приоритетов) 2) найти место в структуре данных узла, обычно это делается через карту. 15.11.2013
- Вы используете минимальный ключ и минимальный вес как синонимы, но, похоже, вам не нравится идея использовать вес в качестве ключа. Здесь какое-то недоразумение? 15.11.2013
- Если вес является ключевым, то
myMap.begin()указывает на узел с наименьшим весом. Если вес не является ключевым, тогда как именно может помочь очередь с приоритетами? 15.11.2013 - @Igor, использование карты не решает проблему. это просто сдвигает его. Представьте, что у вас есть карта, в которой в качестве значения хранится некоторый GNode *, а ключ - это вес, связанный с GNode *. Теперь, если я попрошу вас найти мне конкретный GNode *, потому что я хочу его обновить / удалить. Разве он не будет говорить о линейном времени, и нам придется пересекать всю карту? 15.11.2013
- @Beta, я понял, что использовать в качестве ключа минимальный вес. Но цели это не решает. См. Мой ответ Игорю выше 15.11.2013
- Я понимаю. Вы ищете что-то вроде boost bimap 15.11.2013
- @IgorTandetnik: Нет. Он ищет Boost Куча Фибоначчи. 15.11.2013
- algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html. Это на Java, но вы можете переписать на C ++. 15.11.2013
Ответы:
1
std::priority_queue<T> не поддерживает эффективный поиск узлов: он использует d-арную кучу, обычно с d == 2. Это представление не удерживает узлы на месте. Если вы действительно хотите использовать std::priority_queue<T> с алгоритмом Prim, единственный способ - просто добавить узлы с их текущим кратчайшим расстоянием и, возможно, добавить каждый узел несколько раз. Это превращает размер в O(E) вместо O(N), т. Е. Для графов с большим количеством ребер это приведет к гораздо большей сложности.
Вы можете использовать что-то вроде std::map<...>, но это действительно имеет ту же проблему: вы можете либо найти следующий узел для эффективного извлечения, либо вы можете найти узлы для эффективного обновления.
«Правильный» подход заключается в использовании очереди приоритетов на основе узлов, например, кучи Фибаноччи : Поскольку узлы остаются на месте, вы можете получить дескриптор из кучи при вставке узла и эффективно обновить расстояние до узла через дескриптор. Доступ к ближайшему узлу эффективен с использованием нескольких верхних узлов в наборе деревьев кучи. Общая производительность основных операций с кучей (push(), top() и pop()) для куч Фибоначчи ниже, чем для d-арных куч, но эффективное обновление отдельных узлов делает их использование целесообразным. Мне кажется, я припоминаю, что алгоритм Прима в любом случае требовал кучи Фибоначчи для достижения жесткой границы сложности.
Я знаю, что есть реализация кучи Фибоначчи в Boost. Эффективная реализация куч Фибоначчи не совсем тривиальна, но они более эффективны, чем просто представляют теоретический интерес.
15.11.2013
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально
Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение
Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования
Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv)
Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..