Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Поиск клики
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Всем привет,хотел разобрать этот алгоритм,но возникли некие трудности. Если кто-то может помочь,то скажите - зачем множество "NOT",описанное в этой статье?http://ru.wikipedia.org/wiki/%D0%90%D0% … 1%88%D0%B0
Каким образом оно помогает?Возможно кто-нибудь знает некоторые фичи этого алгоритма? При каких ограничения он должен работать за адекватное время и т.д.
Заранее спасибо.
Привет.
По работе тоже досталась задачка по нахождению максимального числа не связанных между собой вершин.
Реализацией пока не занимался, читаю книжки.
До конца алгоритм пока не понял.
Тоже очень интересно.
Множество NOT как я понял необходимо для исключения на следующих шагах части вершин из перебора, так как известно что на какой-то момент для данного подмножества они не дадут лучшего результата. (может быть я не прав)
С точки зрения оптимизации мне кажется эффективнее описать матрицу смежности битовыми строчками. (не везде использовать списки)
С битовыми строками можно очень быстро выполнять битовые операции & | и тд, что наверное в комбинации со списками даст лучший результат.
С удовольствием бы поучаствовал в разработке более оптимальной реализации предлагаемого в Wiki решения.
А как связать списки и битовые маски?
Думаю это не даст ощутимого преимущества,сперва нужно вникнуть в сам алгоритм,а с этим проблемы...:(
Сегодня занимался реализацией алгоритма поиска максимального множества не связанных вершин. На входе имею граф 1280 вершин.
Представил в виде массива unsigned int [1280][40] 1280 списков смежности по 40х32бита =1280бит
У меня есть своя библиотека хорошо оптимизированных с точки зрения быстродействия функций по работе с битовыми строчками (запись,удаление бита на нужной позиции , проверка бита по позиции, поиск первой 1, сложение умножение отрицание, сложение по модулю)
Работаю с битовыми строками и динамическими списками. Первое впечатление: операции исключения действительно получаются со строками гораздо эффективнее, чем работа со стандартными list списками смежности.
Множество NOT я так понял используется для шагов назад, по рассматриваемой ветке графа.
и для исключения части решений не из рассмотрения. (до конца пока не понял)
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Поиск клики