Описание алгоритма. Шаг 1. Присвоение начальных значений.Построить исходную таблицу и начать с частного решения: , ,

Шаг 1. Присвоение начальных значений. Построить исходную таблицу и начать с частного решения: , ,

и

Шаг 2. Расширение. Найти . Над блоком р поставить метку (над его первым множе ством, которое, как следует из построения, имеет наименьшую стоимость).

Шаг 3. Начиная с отмеченной позиции в блоке р, проверить его множество в порядке возрастания индекса j.

а) Если найдено и , где стоимость множества , то перейти к шагу 5.

б) В противном случае, т.е. блок р исчерпан или выбрано , такое, что , перейти к шагу 4.

Шаг 4. Шаг возвращения. В не может привести к лучшему решению. Если , то конец работы алгоритма и оптимальным, решением является . В противном случае удалить последнее множество, пусть , добавить его в В, положить , поставить метку над , удалить предшествующую метку в блок 1 и перейти к шагу 3.

Шаг 5. Проверка нового решения. Обновить данные: , , . Если найдено лучшее решение , то положить , и перейти к шагу 4. Иначе перейти к шагу 2.

Если поиск оканчивается с исчерпыванием блока 1 (шаг 4), то целесообразно переставить блоки в порядке возрастания числа столбцов (множеств) в каждом блоке.

В описанном выше алгоритме единственным шагом, характерным для ЗНР, является шаг 3 (а). Если удалить в этом шаге требование "неперекрываемости" , то алгоритм может быть использован для ЗНП. Однако в этом случае исходная таблица будет отличаться от табл. 2.1.

Приведенный алгоритм является достаточно примитивным поисковым алгоритмом без особых тонкостей, хотя при тщательном программировании будет весьма эффективен для ЗНР, но не особенно для ЗНП, даже при скромных размерах задачи.

II. Практическая