Задать вопрос

Mercury13

Программист на «си с крестами» и не только
Ответы пользователя по тегу Графы

  • Как в графе найти самый "большой" полный подграф?

    @Mercury13
    Программист на «си с крестами» и не только
    Это штатная задача, т.н. «задача о клике», NP-полная. Ничего лучше усовершенствованного перебора не существует.
    https://ru.wikipedia.org/wiki/Алгоритм_Брона_—_Кербоша
    Ответ написан
    Комментировать
    Комментировать

  • Что такое проекция на множество узлов в графе?

    @Mercury13
    Программист на «си с крестами» и не только
    Двудольный граф можно представить как соответствие R ⊆ A×B. Тогда проекция двудольного графа на долю A (или B) — это те вершины из A (или из B), из которых идёт ребро.
    Ответ написан
    Комментировать
    Комментировать

  • Как нужно изменить алгоритм Дейкстры чтобы он искал самый длинный путь?

    @Mercury13
    Программист на «си с крестами» и не только
    Варианты.
    1. Если граф циклический, максимальный путь — ∞.
    2. Если циклический, но путь обязан быть несамопересекающимся — Дейкстра не подойдёт. Подобную олимпиадную задачу я решал и там решением был перебор с кэшированием (вершин вроде до 15).
    3. Если граф циклический, но есть отрицательные веса, которые в определённых случаях дают-таки точный максимум — меняем знак, применяем модификацию Дейкстры для отрицательных весов. Он либо скажет, что есть цикл, позволяющий сколь угодно уменьшить сумму, либо даст точный минимум.
    4. Если ациклический ненаправленный — то либо один, либо нет вообще (т.н. лес);
    5. Если ациклический направленный — должен работать совсем другой алгоритм: отсортировать в топологическом порядке, убрать те элементы, которые перед началом и за концом, а на оставшихся пустить динамическое программирование.
    Ответ написан
    Комментировать
    Комментировать

  • Как построить N-дерево и найти самую длинную ветвь без ветвлений?

    @Mercury13
    Программист на «си с крестами» и не только
    Что-то типа

    максРазмер : целое
началоМаксВетви: узел

проц максВетвь(узел : Узел, началоВетви: Узел, текРазмер: целое)
  в зависимости от степени узла «узел»
    если 0:
      если текРазмер > максРазмер
        максРазмер = текРазмер
        началоМаксВетви = началоВетви
    если 1: максВетвь(единственныйCын, началоВетви, текРазмер + 1)
    если 2+:
      для всех сыновей
        максВетвь(сын, сын, 1)

максВетвь(корень, корень, 1)


    Считает макс. ветвь, кончающуюся листом; если может кончаться и развилкой — оставляю как домашнее задание.
    Ответ написан
    Комментировать
    Комментировать

  • Алгоритмы: Задача о назначениях, как реализовать множественные назначения?

    @Mercury13
    Программист на «си с крестами» и не только
    Непонятно, как вы в такой ситуёвине считаете штраф. Ведь если штраф считается как раньше, а загрузка работника не ограничена, и задачи-то нет — каждую из работ можно дать тому работнику, который выполняет её лучше всех.

    Если же загрузка работника ограничена m работами — тогда решите задачу о максимальном потоке.

    Исток → работник: пропускная m
    работник → работа: пропускная 1
    работа → сток: пропускная 1
    Ответ написан
    Комментировать
    Комментировать

  • Как дополнить топологическую сортировку?

    @Mercury13
    Программист на «си с крестами» и не только
    С двузначными метками посещения (bool used[]) — никак.

    Надо перейти на трёхзначные метки (UNVISITED, PARTLY_VISITED, VISITED).

    void dfs (int v) {
  state[v] = PARTLY_VISITED;
    .....
  state[v] = VISITED;
  ans.push_back (v);
}


    Неплохой пример есть в вашем предыдущем вопросе.
    Ответ написан
    Комментировать
    Комментировать

  • Как применить топологическую сортировку?

    @Mercury13
    Программист на «си с крестами» и не только
    Нужно переписать под матрицу смежности вот этот участок кода.
    for(int i = 0;i < Edges[v].size();i ++){
          if(dfs(Edges[v].get(i)))return true;
      }

    Что-то типа этого.
    цикл (i : все вершины)
   если матрица_смежности[v, i]
         если dfs(i)
             return true;

    Ещё мне не нравятся константы 0, 1 и 2. Объявить бы их как
    UNVISITED = 0;
PARTLY_VISITED = 1;
VISITED = 2;

    Или WHITE, GRAY и BLACK, если хотите — в учебниках по алгоритмам их красят в три цвета.
    Ответ написан
    Комментировать
    Комментировать

  • Алгоритм поиска кратчайшего пути в графе

    @Mercury13
    Программист на «си с крестами» и не только

    Если подвижных мостов мало, можно каждую вершину размножить в 2b экземплярах (b — кол-во мостов). Тогда пойдёт даже не Дейкстра, а обычный поиск в ширину.

    Если два моста «сцеплены» друг с другом и наводятся/разводятся одновременно, то в b они идут одной штукой.

    А если мостов много и 2b — непозволительная трата, тогда интересно. Думаю, ничего, кроме эвристик, не поможет. Например, может случиться так, что кратчайший путь от включателя до всех мостов, которыми он управляет, посуху. Или мосты (в смысле управляемые) — это мосты (в смысле теории графов). Или что-нибудь ещё.

    Ответ написан
    1 комментарий
    1 комментарий