Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2. Некоторые примеры ветвления

Рассмотрим задачу переменными, в которой некоторая переменная может принимать только четыре возможных значения, скажем,

(а) Возможно разбиение на четыре подзадачи причем для подзадачи мы полагаем для полагаем для и для

Рис. П.3. Три возможных способа ветвления в вершине

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

(б) Возможно другое разбиение на две подзадачи где для мы полагаем а для полагаем т. е. равно с или (рис. Еще одно возможное разбиение на две подзадачи где для или а для или (рис.

Все три ветвления являются допустимыми и удовлетворяют условию Какому из них отдать предпочтение — зависит от природы решаемой задачи, причем возможности типа (а) или (б) используются чаще остальных.

<< Предыдущий параграф Следующий параграф >>
Оглавление