Мой отчёт по курсовику запилили на литературно-художественных выражениях и личных местоимениях; я честно постаралась переделать, но мозг уже не способен воспринимать текст, поэтому очень прошу:

Если не очень сложно, ПРОЧИТАЙТЕ ПОЖАЛУЙСТА и скажите, прокатывает ли этот текст для технического отчёта или нет. Если нет, желательно указать непонравившиеся места. Очень нужно!!! (с коментами, плиз)



Описание алгоритма



Метод ветвей и границ – это один из методов исчерпывающего поиска. Сама суть этого метода состоит в таком построении дерева поиска, чтобы с помощью граничных условий (некий параметр, присваиваемый каждой ветви дерева) можно было сократить число просматриваемых вариантов в поисках оптимального. Полный перебор – это тоже исчерпывающий поиск, но в этой задаче, действуя перебором, придётся просматривать n! вариантов, что невозможно при достаточно больших n. В данном случае решение практически сводится к решению Задачи коммивояжёра, за рядом нескольких отличий.

• 
  Работник и работа между собой не связаны до той поры, пока их не распределят, поэтому нет запрета на главную диагональ матрицы стоимостей.

• 
  Конечным результатом является таблица соответствий людей и их работ, а не маршрут кратчайшего объезда.

Граничными условиями для данной задачи являются верхняя и нижняя границы.

• 
  Верхняя граница – это некий уже имеющийся результат. Чаще всего получают с помощью «жадного» алгоритма с маленькой сложностью. Соответственно, если в процессе обхода дерева поиска выясняется, что по всему поддереву любой результат будет хуже уже имеющегося, то такую ветвь можно сразу исключить из обхода.
  В этой задаче верхняя граница находится методом ближайшего соседа – простым поиском минимума в каждой строке среди незанятых столбцов (то есть, если в первой строке выбран третий элемент, то ни в какой другой строке выбирать его уже нельзя). Алгоритм эвристический, как правило, даёт неплохой результат, но этот результат может довольно сильно отличаться от искомого, а в данном случае цель – найти именно оптимальное распределение.
  

• 
  Нижняя граница – это такое число (границы могут измеряться и не в числах, но возьмём простейший случай), лучше которого в данном случае быть не может. Например, если есть массив из 500 элементов и точно известно, что все они больше 100, то, выбирая из них 10 любых, можно со стопроцентной уверенностью сказать, что сумма будет не менее 1000.
  Но здесь не простой массив, а матрица (правда, в программном коде это всё-таки массив, но того требует реализация). Нижнюю границу в матрице мы будем искать, находя минимумы в каждой строке и вычитая их из каждого элемента данной строки (то есть в каждой строке уже будет как минимум один ноль), потом так же проходя все столбцы, а получившаяся сумма вычтенных локальных минимумов и будет искомой нижней границей.
  

После того, как определились с границами, следует продумать, как их можно использовать в построении и обходе дерева исчерпывающего поиска. Задача – откинуть как можно больше неудачных вариантов распределений, чтобы не тратить время на их просмотр. Было бы удобно, чтобы в строящемся бинарном дереве нас всё время интересовала только одна ветвь, а избавиться от второй, как уже говорилось, можно, если будем уверены, что все варианты распределений из нежелательного поддерева будут хуже, чем уже известный результат.

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

В данном алгоритме можно добиться такого эффекта, выбирая или запрещая некоторую ячейку. Если выбрать некоторую ячейку, то можно смело вычёркивать из матрицы строку и столбец, в которых она находится, а если запретить, то на её место просто ставится некое большое число (в идеале – бесконечность, но в данном варианте просто большое число). Соответственно, чтобы граница росла как можно медленнее, следует выбирать ячейки с нулевой стоимостью. А чтобы при этом граница другой ветви увеличилась на как можно большее число, запрещаем ту нулевую ячейку, при подставлении большого числа в которую из её столбца (и/или строки) можно будет вычесть максимальное число, которое прибавится к нижней границе этой ветви.

Нетрудно понять, что если всё время выбирать такие вот «нулевые» ячейки, то результат будет равен или крайне близок оптимальному.

Когда, действуя таким вот методом, алгоритм доходит до последнего шага (всего нужно n-1 шагов, последний очевиден), можно «обновить» верхнюю границу на получившуюся. Затем, рекурсивно возвращаясь, сравнить нижние границы «нежелательных» поддеревьев с получившейся новой верхней границей. В большинстве случаев оказывается, что больше никуда заходить не нужно – достаточно одного спуска по дереву, чтобы найти интересующее нас решение. В противном случае необходимо рассмотреть и те ветви дерева, в которых даже после обновление границ нижняя всё равно остаётся меньше верхней.

Тем не менее, применение метода ветвей и границ в среднем не снижает сложность решения задачи до уровня ниже экспоненциальной. Известно, что для случайной

(n×n)-матрицы стоимости эта сложность составляет O(〖1,26〗^n), что всё равно много меньше, чем n! при поиске решения полным перебором.





Очень-очень-очень надо