Ответы пользователя по тегу Структуры данных
  • Сохранение древовидной структуры в файл, best way?

    @nirvimel
    для добавления произвольного узла в дерева, следует пройтись по всем узлам для коррекции смещений узлов в файле и перезаписать.

    Это в любом случае неизбежно. Единственно что можно сделать для сокращения дискового I/O - это, вместо записи множества кусков (через seek->write->seek->write), использовать встроенные в ОС механизм memory mapping (в Java он реализован через MappedByteBuffer), тогда проблема оптимизации кеширования и сброса буферов на диск ложится полностью на ОС.
    Ответ написан
    2 комментария
  • Как реализовать точный алгоритм правильной раскраски рёбер графа?

    @nirvimel
    Существуют алгоритмы полиномиального времени, создающие оптимальную раскраску двудольных графов и раскраску простого не двудольного графа с числом цветов {\Delta}+1.

    Однако, в общем случае, задача поиска оптимальной рёберной раскраски NP-полна и самый быстрый из известных алгоритмов для неё работает за экспоненциальное время.

    Рёберная раскраска

    Итак, можно найти раскраску в Delta + 1 цветов за полиномиальное время (что тоже может оказаться совсем не быстро). Но чтобы доказать, что не существует раскраски (иначе, найти ее) ровно в Delta цветов, необходимо решить NP-полную задачу за экспоненциальное время.
    (Delta - максимальная степень вершины).
    Ответ написан