Теория графов: лучший алгоритм для нахождения комбинации «направлений» ребер, где каждый узел имеет не более одного ребра, направленного на него
== проверяет ссылки на объекты, .equals() проверяет строковые значения.
Иногда кажется, что == сравнивает значения, потому что Java делает некоторые закулисные вещи, чтобы убедиться, что одинаковые строки в строке являются одним и тем же объектом.
Для Например:
String fooString1 = new String("foo");
String fooString2 = new String("foo");
// Evaluates to false
fooString1 == fooString2;
// Evaluates to true
fooString1.equals(fooString2);
// Evaluates to true, because Java uses the same object
"bar" == "bar";
Но будьте осторожны с нулями!
== обрабатывает строки null в порядке, но вызов .equals() из пустой строки приведет к исключению:
String nullString1 = null;
String nullString2 = null;
// Evaluates to true
System.out.print(nullString1 == nullString2);
// Throws a NullPointerException
System.out.print(nullString1.equals(nullString2));
Итак, если вы знаете, что fooString1 может но не менее очевидно, что он проверяет значение null (из Java 7):
System.out.print(Objects.equals(fooString1, "bar"));
3 ответа
Не полный алгоритм, но, учитывая ваше описание проблемы в комментариях, я чувствую, что эти шаги, вероятно, вернут проблему в грубую область.
Во-первых, вы должны «обрезать» свой график. Любые узлы первой степени следует обрезать так, чтобы их связанный край был направлен на обрезанный узел. Поскольку никакое другое ребро не может указывать на этот узел, мы знаем, что этот выбор является оптимальным. Промойте и повторяйте, пока все оставшиеся узлы не будут иметь два или более краев.
Далее, как вы упомянули, вы должны исключить любые изолированные узлы. На самом деле вы можете расширить это до подключенных компонентов из size <= 3. Это связано с тем, что для максимум трех узлов количество ребер не может превышать количество узлов, поэтому вы можете случайным образом назначить одно ребро, а остальные станут на свои места.
Теперь, что останется, это куча больших, сильно связанных, связанных компонентов. Вы могли бы на самом деле сделать еще одну проверку и посмотреть, образуют ли какие-либо из них один цикл (все узлы степени два), а затем случайным образом назначить одно ребро, но это, вероятно, довольно редкий случай. Вы, вероятно, просто захотите начать грубое форсирование каждого из них независимо. Вероятно, было бы лучше начать сначала с узлов с наименьшим числом ребер, обновляя степень узлов при назначении ребер (а также обрезая ребра в любом градусе, как раньше), возвращая при необходимости возврат.
Это продолжение ответа Диллона Дэвиса .
После удаления древовидных ветвей и разрешения простых циклов оставшийся граф имеет узлы степени 2 или более. Я предлагаю, чтобы (для анализа графа) все узлы степени 2 были удалены.
Позвольте мне объяснить на примере. В этом примере, когда узел представлен числом, это число является степенью узла. Когда узел представлен буквой, этот узел имеет степень 2. Таким образом, граф
3 - A - B - C - 4
представляет узел степени 3, связанный с цепочкой узлов степени 2, связанный с узлом степени 4.
Два идеальных варианта для этой части графика:
3 -> A -> B -> C -> 4
3 <- A <- B <- C <- 4
Они идеальны в том смысле, что каждый буквенный узел имеет ровно один входящий ребро. Я предполагаю, что это не просто идеальный выбор, это выбор только . Рассмотрим первое идеальное решение
3 -> A -> B -> C -> 4
Если узел 4 имеет слишком много входящих ребер, мы можем уменьшить его счет, вернув ребро в C, давая
3 -> A -> B -> C <- 4
Но это не имеет улучшив ситуацию, он торгует «слишком много ребер в 4» с «слишком много ребер в C» . Впоследствии изменение границы между C и B разрешает C, но разрывает B. Продолжайте двигаться по всей цепочке, и в конечном итоге связь между A и 3 меняется на противоположную, и мы пришли ко второму идеальному решению.
Что приводит меня к выводу, что (для целей анализа)
3 - A - B - C - 4
эквивалентно
3 - 4
Так как это полезно для упрощения проблемы. Рассмотрим следующий график:
Когда узлы A и B удалены, оставшийся край соединяет верхний узел 3 с самим собой, так что край может быть удален. Аналогично для C и D. Что оставляет график с одним ребром. Выберите любое направление для этого края. Затем завершите решение, выбрав направление для простого цикла A-B-3, и независимо выберите направление для простого цикла C-D-3.
Вот еще один пример:
В этом случае удаление A и B создает избыточные ребра между оставшимися узлами. После удаления лишних ребер выберите любое направление для ребра. Направление этого ребра определяет направление цикла 3-A-3 и цикла 3-B-3.
Я не был уверен в добавлении другого ответа, но ответ user3386109 дал мне понимание того, что я считаю полным решением, и я чувствовал, что оно слишком сильно отличается от духа моего оригинала. ответ включить в качестве правки.
Напомним, у нас есть несколько инструментов ниже пояса:
-
Мы можем оптимально обрезать узлы с одним ребром, повторяя процесс до завершения
[113 ] -
Узлы с двумя ребрами в более сложных циклах можно временно игнорировать, так как их направления ребер будут назначаться узлами более высокой степени.
Мы можем назначить направление любому ребру в простом цикле (связанные компоненты только с узлами степени 2), а остальные будут следовать (оптимально).
После прочтения последнего пункта, сама проблема становится немного более понятной. После того, как мы удалили узлы степени один в пуле один, все остальные узлы имеют как минимум два ребра. Мы можем с уверенностью сказать в оптимальном графе, что каждый из этих узлов будет иметь хотя бы одно направленное ребро, указывающее на них. В качестве доказательства, поскольку каждый узел имеет по крайней мере два ребра, но связанный компонент не является простым циклом (иначе это будет исключено в пуле 2), у нас больше ребер, чем узлов. Если какой-либо узел имеет нулевые ребра, направленные к нему, один из этих ребер может быть обращен вспять, чтобы уменьшить количество конфликтующих ребер или «освободить» другой узел, чтобы иметь нулевые внутренние ребра, чтобы затем сделать то же самое.
Вооружившись этим знанием, мы знаем, что минимальное число конфликтов (дополнительные ребра, направленные на узлы, у которых уже есть ребро, направленное на них), равно количеству ребер минус количество вершин в нашем обрезанном графе. Мы также можем сделать вывод, что до тех пор, пока нам удастся направить хотя бы одно ребро в каждый узел, у нас будет оптимальный граф, независимо от того, как мы рассеиваем конфликтующие ребра.
Первоначально я пытался составить алгоритм, основанный на пуле три, для выполнения этого задания, но оказалось, что ответ на самом деле намного проще, чем даже. Единственный способ, которым мы можем случайно создать узел без ребер, направленных от него, - это активное направление всех ребер от этого узла. Решение состоит в том, чтобы выбрать одно ребро в подключенном компоненте и назначить ему случайное направление. Затем выполните поиск (DFS, BFS и т. Д.) Вне узла, на который он направлен, назначая направления ребрам по ходу движения в том направлении, в котором вы их проходите. Любой узел, к которому вы достигнете, будет иметь ребро, направленное на него (ребро, которое вы использовали для его достижения), а корневой узел имеет ребро, которое вы ему назначили вручную.
В итоге получится граф с минимальным числом дополнительных ребер, направленных на узлы. Если вы вместо этого хотите минимизировать количество узлов, содержащих конфликтующие ребра, решите проблему, как указано выше, а затем сформируйте подграф узлов степени три или более и их соединительных ребер. Решите для минимального покрытия вершин этого подграфа, а затем измените направление ребер, соединяющих узлы, не находящиеся в минимальном покрытии вершин, но содержащие конфликтующие ребра, с соответствующими узлами в минимальном покрытии вершин.