Алгоритмы решения транспортной задачи алгоритм Литтла

Алгоритм Литтала является частным случаем применения метода "ветвей играниц" для конкретной задачи.

 Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами.

Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

Целью данного метода является поиск гамильтонового цикла с минимальной стоимостью в графе. Что бы найти его, нужно придерживаться следующим действиям:

1) В каждой строке матрицы стоимости найдем минимальный элемент и вычтем его из всех элементов строки. Сделаем это и для столбцов, не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.

2) Для каждого нулевого элемента матрицы, рассчитываем коэффициент k, который равен сумме минимальных элементов столбца и строки этого нуля. Выбираем нуль с максимальным коэффициентом (если таковых несколько выбираем любой из них). Вносим в гамильтонов контур соответствующую дугу.

3) Удаляем строку и столбец, на пересечении которого выбранный нами нуль.

4) Проверяем граф на наличие точек возврата, если есть таковые, то меняем их значение на максимальное. Повторяем предыд. действия пока не останется матрица порядка 2.

5) Вносим в гамильтонов контур недостающие дуги. Получаем искомый цикл.

Понятие класса. Инкапсуляция

Класс определяет новый тип данных, который задаёт формат объекта. Класс включает как данные, так и код, предназначенный для выполнения над этими данными. Объекты – это экземпляры класса. Класс – логическая абстракция, которая реально не существует, пока не будет создан объект этого класса.

Классы в программировании состоят из свойств и методов. Свойства — это любые данные, которыми можно характеризовать объект класса. Методы — это функции, которые могут выполнять какие-либо действия над данными (свойствами) класса.

Методы класса — это его функции. Свойства класса — его переменные.

Объявление класса начинается с ключевого слова class. Общий формат объявления класса:

Class имя_класса {

закрытые данные и функции

public:

открытые данные и функции

} список объектов

Все свойства и методы классов имеют права доступа. По умолчанию, все содержимое класса является доступным для чтения и записи только для него самого. Для того, чтобы разрешить доступ к данным класса извне, используют модификатор доступа public. Все функции и переменные, которые находятся после модификатора public, становятся доступными из всех частей программы.

Закрытые данные класса размещаются после модификатора доступа private. Если отсутствует модификатор public, то все функции и переменные, по умолчанию являются закрытыми. Обычно, приватными делают все свойства класса, а публичными — его методы. Все действия с закрытыми свойствами класса реализуются через его методы.

Инкапсуляция — это свойство, позволяющее объединить в классе и данные, и методы, работающие с ними, и скрыть детали реализации от пользователя. Более того, именно инкапсуляция позволяет создавать объект. Попросту говоря, объект представляет собой логическое целое, включающее в себя данные и код для работы с этими данными. Мы можем определить часть кода и данных как собственность объекта, которая недоступна извне. На этом пути объект обеспечивает существенную защиту против случайной модификации или некорректного использования таких частных (private) членов объекта.

Конструкторы и деструкторы

Конструктор – функция, которая вызывается при создании объекта. Это специальная функция, которая является членом класса и имя которой совпадает с именем класса. Конструкторы не возвращают значений, следовательно, в указании типов нет смысла, нельзя указывать даже void.

Пример:

Конструктор объекта вызывается при создании объекта. Это значит, что он вызывается при выполнении инструкции объявления объекта. Конструкторы глобальных объектов вызываются в самом начале выполнения программы, еще до обращения к функции main(). Конструкторы локальных объектов вызываются каждый раз при объявлении такого объекта. В классе допустимо создавать несколько конструкторов, если это необходимо. Имена будут одинаковыми. Компилятор будет их различать по передаваемым параметрам (как при перегрузке функций). Если мы не передаем в конструктор параметры, он считается конструктором по умолчанию.

Деструктор – функция, которая вызывается при разрушении объекта. Во многих случаях при разрушении объекту необходимо выполнить некоторое действие или даже некоторую последовательность действий. Локальные объекты создаются при входе в блок, в котором они определены, и разрушаются при выходе из него. Глобальные объекты разрушаются при завершении программы. Существует множество факторов, обуславливающих необходимость деструктора. Например, объект должен освободить выделенную ранее память. Имя деструктора совпадает с именем конструктора, но перед ним стоит символ ~. Как и конструкторы, ничего не возвращают.

Пример: (класс берётся из конструктора, но в него надо дописать ~queue();)

В классе может быть объявлен только один деструктор.

Шаблоны классов

Шаблоны позволяют определить конструкции (функции, классы), который используют определенные типы, но на момент написания кода точно не известно, что это будут за типы. Иными словами, шаблоны позволяют определить универсальные конструкции, которые не зависят от определенного типа. Шаблон класса (class template) задаёт тип для объектов, используемых в классе.

Для применения шаблонов перед классом указывается ключевое слово template, после которого идут угловые скобки. В угловых скобках после слова typename идет параметр шаблона. Можно определить несколько параметров шаблона.

Параметр шаблона представляет произвольный идентификатор, в качестве которого, как правило, применяются заглавные буквы. Параметр будет представлять некоторый тип, который становится известным во время компиляции. Это может быть и тип int, и double, и string, и любой другой тип.

Общая форма объявления класса-шаблона:

template < class птип> class имя_класса {

/*...*/

}

Здесь птип является параметром-типом, который будет указан при создании экземпляра класса. При необходимости можно определить несколько типов-шаблонов, используя список и запятую в качестве разделителя.

После создания класса-шаблона можно создать конкретный экземпляр этого класса, используя следующую общую форму:

имя_класса <тип> объект;

Здесь тип является именем типа данных, с которыми будет оперировать данный класс.