Bellman-Ford с кучей не работает с пользовательской функцией сравнения - PullRequest
Новая
       71

Bellman-Ford с кучей не работает с пользовательской функцией сравнения

1 голос
/ 12 февраля 2012

Я реализовал алгоритм Беллмана-Форда для решения проблемы (с графиком), но это решение было слишком медленным, поэтому я заменил очередь Беллмана-Форда кучей (std :: set), поэтому решение самый короткий путь будет найден быстрее. (как-то близок алгоритм Дейкстры)

Теперь я вставляю номер узла в кучу, поэтому стандартный std :: set будет сортировать узлы по их номеру, а не по их стоимости. Все хорошо, и алгоритм дает ответы на все вопросы.

Если я реализую пользовательскую функцию сравнения для std :: set, так что узлы будут отсортированы по их расстоянию, а не по количеству, алгоритм больше не будет предоставлять кратчайшее расстояние до остальных узлов.

Это моя функция сравнения: 

 struct cmp{

    bool operator() (const int &a,const int &b) const{
        return (d[Q][a] < d[Q][b] );
    }
  };
 set <int,cmp> q;

Таким образом, будучи алгоритмом BF, алгоритм работает до тех пор, пока улучшения не будут сделаны. Может ли функция сравнения каким-то образом «испортить» std :: set, потому что это единственная причина, по которой я понимаю, почему добавление этой функции сравнения даст неправильные ответы ...

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

1 Ответ

2 голосов
/ 12 февраля 2012

Насколько я помню, алгоритм Беллмана-Форда обновляет расстояние до узла. Таким образом, использование веса в качестве ключа для std::set<T> не легко работает: поиск в std::set<T> не найдет соответствующее значение, если вы просто изменили расстояние. Чтобы выполнить это направление, вам необходимо удалить узел, подлежащий обновлению, изменить расстояние до узла и повторно установить его впоследствии. Также обратите внимание, что объекты в std::set<T> должны иметь уникальный ключ: вставка ключа, который уже существует, завершится неудачей.

Вы сказали, что используете std::set<int> в качестве некоторой очереди с приоритетами. Вы смотрели на std::priority_queue<T>? Это делает именно это, но имеет тенденцию быть более эффективным, чем использование std::set<T>. Проблема с std::priority_queue<T> заключается в том, что вы не можете изменить приоритет объектов: у вас есть доступ только к текущей вершине. Давным-давно я создал коллекцию очередей с приоритетами (куч), которые включали в себя версии очередей с приоритетами, позволяющие изменять приоритет объекта (они были частью исходных библиотек для Boost, но они никогда не делали это в процессе проверки). Я не знаю, как вы используете свою очередь приоритетов, и поэтому я не знаю, является ли это разумным направлением.

Тем не менее, я не понимаю, почему вы все равно захотите использовать std::set<T> для алгоритма Беллмана-Форда. Насколько я понимаю, алгоритм многократно проходит через граф и обновляет узлы с их новым кратчайшим расстоянием. Вы смотрели на Boost реализацию алгоритма Беллмана-Форда ?

...