Используйте ветку и привязаны для решения проблемы раздела в 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, чтобы отслеживать общую сумму значения, которая еще не назначена в тестовом решении. Он рекурсивно называет себя только тогда, когда это значение может потенциально улучшить наилучшее решение.

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

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

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)

Add a Comment

Ваш e-mail не будет опубликован. Обязательные поля помечены *