Используйте ветку и привязаны для решения проблемы раздела в C#

Сообщение Используйте исчерпывающий поиск для решить проблему раздела в C# , объясняет проблему раздела и то, как вы можете использовать исчерпывающий поиск для поиска решений для него.

К сожалению, количество возможных решений огромно. Если вы делите N элементов, то есть 2 ^{N возможных способов разделить их на две группы. Это означает, что существует слишком много возможных решений, чтобы попробовать их всех, если N не очень мало. Например, если вы можете исследовать 1 миллион возможных решений в секунду, потребуется 18 минут для изучения каждого возможного решения для 30 пунктов, 12,7 дней для 40 предметов и 35,7 года для 50 предметов.}

Ветвь и граница - это метод сокращения количества ветвей, которые вам нужно посетить, при поиске дерева. Вы можете рассматривать проблему секционирования как поиск дерева, если вы рассматриваете каждое решение о том, следует ли поместить элемент в набор 1 или установить 2, выбрав ветку в дереве. Если есть N элементов, то дерево является полным двоичным деревом с N уровнями, поэтому оно содержит 2 ^{N листовые узлы, соответствующие возможным решениям.}

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

Например, предположим, что вы уже нашли деление на 30 элементов, где значения двух наборов отличаются на 10. Теперь предположим, что вы рассматриваете тестовое решение, которое уже назначило 20 элементов, поэтому наборы в тестовом решении так значительно отличаются на 20, а общая стоимость остальных 10 предметов равна 5. Даже если вы добавите все оставшиеся предметы в меньший из двух наборов, лучшее, что вы могли бы сделать, это сделать, чтобы наборы отличались на 15. Это не улучшение по сравнению с лучшим решением, найденным до сих пор, поэтому нет смысла продолжать рассмотрение этого тестового решения. Это позволяет пропустить рекурсивные вызовы, которые будут посещать остальную часть дерева, и это может потенциально сэкономить огромное количество времени.

Следующая версия метода PartitionValuesFromIndex принимает дополнительный параметр unassigned_value, чтобы отслеживать общую сумму значения, которая еще не назначена в тестовом решении. Он рекурсивно называет себя только тогда, когда это значение может потенциально улучшить наилучшее решение.

// Разделяем значения с теми, которые были установлены до индекса start_index.
// test_assignment - это тестовое задание.
// test_value = общее значение первого набора в test_assignment.
// Изначально наилучшее назначение и его ошибка в
// best_assignment и best_err.
// Обновляем те, которые отражают любое улучшенное решение, которое мы находим.
private void PartitionValuesFromIndex(int[] values,
    int start_index, int total_value, int unassigned_value,
    bool[] test_assignment, int test_value,
    ref bool[] best_assignment, ref int best_err)
{
    // Если start_index находится за пределами массива,
    // тогда все записи были назначены.
    if (start_index >= values.Length)
    {
        // Были сделаны. Посмотрите, лучше ли это назначение
        // что у нас есть.
        int test_err = Math.Abs(2 * test_value - total_value);
        if (test_err < best_err)
        {
            // Это улучшение. Сохрани это.
            best_err = test_err;
            best_assignment = (bool[])test_assignment.Clone();

            Console.WriteLine(best_err);
        }
    }
    else
    {
        // Смотрите, есть ли способ, которым мы можем назначить
        // остальные элементы для улучшения решения.
        int test_err = Math.Abs(2 * test_value - total_value);
        if (test_err - unassigned_value < best_err)
        {
            // Есть шанс, что мы сможем улучшить ситуацию.
            // Теперь мы назначим следующий элемент.
            unassigned_value -= values[start_index];

            // Попробуйте добавить значения [start_index] для установки 1.
            test_assignment[start_index] = true;
            PartitionValuesFromIndex(values, start_index + 1,
                total_value, unassigned_value,
                test_assignment, test_value + values[start_index],
                ref best_assignment, ref best_err);

            // Попробуйте добавить значения [start_index] для установки 2.
            test_assignment[start_index] = false;
            PartitionValuesFromIndex(values, start_index + 1,
                total_value, unassigned_value,
                test_assignment, test_value,
                ref best_assignment, ref best_err);
        }
    }
}

Если вы сравниваете этот пример с предыдущий , вы обнаружите, что это намного быстрее, потому что он посещает только небольшую часть дерева поиска.

Источник: http://csharphelper.com/blog/2015/01/use-branch-and-bound-to-solve-the-partition-problem-in-c/

(Пока оценок нет)