Бектрекинг – механизм решения переборных задач. Позволяет выбрать либо 1 приемлемую альтернативу, либо наилучшую.
Суть режима возвратов состоит в следующим. В программе встречаются точки «развилки» — точки в которых необходимо выбрать один из вариантов поведения («альтернатив»). В дальнейшим может оказаться, что выбранный вариант «неудачен» и нужно вернуться к точке развилки и выбрать какую-то другую альтернативу.
Особенность Бектрекинга состоит в том, происходит откат по управлению, а также по данным. При откате программа «забывает» все, что она сделала в результате выбора неудачной альтернативы — данные восстанавливают свои предыдущие значения, отменяются все последствия выбора альтернативы. После отката берем следующую альтернативу и заново выполняем все действия. Проверяем, какие альтернативы для нас приемлемы. Если в данной развилке все альтернативы оказываются неудачными, распространение неуспеха происходит на вышележащие развилки.
Бектрекинг обеспечивает:
— откат по управления;
— откат по данным;
— перебор списка альтернатив.
Существуют действия неподверженные откату. Пример: печать на экран, принтер и т. д.
Развилки можно разделить на локальные (видны только в своей подпрограмме) и глобальные (даже подпрограмма закончена развилка видна).
Поэтому возможно откатное вхождение в процедуру. Процедура полностью восстанавливается, восстанавливаются все локальные переменные, их значения и история их значений.
Варианты организации:
— в качестве альтернатив могут выбираться данные и действия; (массив из процедурных меток)
— список альтернатив: фиксированный, вычисляемый динамически, может не храниться вообще;
— автоматическое изменение порядка набора альтернатив.
Предсказать какая альтернатива принесет успех. (предсказание требует ресурсов.). но перебирая альтернативы в итоге придем к результату.
— возможно отсутствие конструкции “неудача”; (существует конструкция для установления точки развилки или не существует)
— откат возможен: к ближайшей развилке, к указанной статически / динамически, автоматическое определение нужной развилки;
Если перебрали все альтернативы, то неудачу распространяем наверх.
Чтобы не откатываться по шагам, а к той, которую хочешь необходимо:
1. отметить все развилки и откатываться туда
2. откат к развилке определяется динамически.
— автоматическое определение развилки.
Откат в пределах программы
Откат в вызванную подпрограмму
Откат в завершенную подпрограмму.
Если к развилке можно откатиться после завершения процедуры, то развилка наружная.
Необратимое действие – действия, не отменяемые при откате, могут существовать, могут не существовать.
— возможно отключение режима возвратов, динамически / статически, полностью / частично;
— можно связать с сигналом о неуспехе сообщения, и возможность программного анализа.
Существуют языки, которые в своей реализации поддерживают бектрекинг (Пролог, Плэнер). Я в рамках данной статьи рассмотрю эмуляцию режима возвратов на языках, не поддерживающих его в явном виде. В статье для написания листинга я буду использовать паскалеподобный псевдокод, дабы не отвлекаться на синтаксис.
Схема реализация бектрекинга на процедурно-ориентированном языке.
В данном подходе развилки эмулируются при помощи рекурсии, а перебор альтернатив при помощи цикла.
Задача о стабильных браках
Предположим, что даны два непересекающихся множества А и В равного размера n. Требуется найти набор из n пар <a,b>- таких, что а из А и b из B удовлетворяют некоторым ограничениям. Критериев распределения может быть много. Мы рассмотрим один из них, который называется правилом стабильных браков.
Пусть A – множество мужчин, а B – множество женщин. Каждый мужчина и каждая женщина указали предпочтительных для себя партнеров. Если пары сформированы так, что существуют мужчина и женщина, которые являются мужем и женой, но которые предпочли бы друг друга своим фактиче6ским супругам, то такое распределение будет нестабильным. Если таких пар нет, то распределение стабильно. Следует заметить, что список распределений остается неизменным и после того, как сделано распределение по парам.
Возможное направление поиска решения – пытаться распределять по парам членов двух множеств одного за другим, пока не будут исчерпаны оба множества. Для решения данной задачи используем схему бектрекинга, слегка модифицировав ее в сторону упрощения.
Исходные данные представим двумя матрицами, указывающими предпочтения мужчин и женщин.
Соответственно womanForMan[m,r] – женщина, находящаяся в списке мужчины m на r-м месте. Аналогично manForWoman[w,r] – мужчина, находящийся в списке женщины w на r-м месте.
Результат представим массивом woman так, что woman[m] обозначает супругу мужчины m. Для симметрии введем man так, что man[w] обозначает супругу мужчины w. На самом деле массив man избыточен, так как в нем содержится информация уже содержащиеся в woman. Информация в массивах man и woman нужна для определения стабильности предполагаемого множества браков. Поскольку это множество строится шаг за шагом посредством соединения индивидов в пары и проверки стабильности после каждого предполагаемого брака, массивы man и woman нужны еще до того, как будут определены все компоненты. Чтобы отслеживать, какие компоненты уже определены, мы введем булевские массивы:
singleMan, SingleWoman: array [1..n] of Boolean
истинность компонента означает то, что соответствующий мужчина (женщина) свободны.
с их помощью можно уточнить предикат допустима как конъюнкцию singleWoman[w] & брак стабилен, где предикат брак стабилен еще предстоит доопределить.
Ключевая задача теперь – уточнить алгоритм определения стабильности. Первая особенность, о которой нужно помнить, состоит в том, что по определению, стабильность следует из сравнения рангов (то есть позиций в списке предпочтений). Однако нигде в нашей коллекции данных, определенных до сих пор, нет непосредственно доступных рангов мужчин и женщин. Разумеется их можно вычислить по значениям womanForMan и manForWoman, но так как вычисление стабильности очень частая операция, целесообразно обеспечить более прямой доступ к этой информации. Для этого введем две матрицы,
Rmw: array [man,woman] of rang;
Rwm: array [woman,man] of rang;
При этом rmw[m,w] обозначает ранг женщины w в списке мужчины m, и rwm[w,m] – ранг мужчины m в списке женщины w. Значения этих вспомогательных матриц не меняются и могут быть определены в самом начале по значениям womanForMan и manForWoman.
Теперь предикат Брак стабилен может быть вычислен точно следуя его определению. Напомню, что нам нужно проверить возможность соединить браком m и w, где w=womanForMan[m,r]. Для начала предположим, что такой брак допустим, а потом попытаемся обнаружить помехи для стабильности этого брака. Таких помех может быть две:
1) Может найтись женщина pw с рангом более высоким, чем у w, по мнению m, и которая и сама предпочитает m своему мужу;
2) Может найтись мужчина pm с рангом, более высоким, чем у m, по мнению w, и который сам предпочитает w своей жене
Чтобы обнаружить помеху первого рода, сравним ранги rwm[pw,m] и rwm[pw,man[pw]] для всех женщин, которых m предпочитает w, то есть для всех pw=womanForMan[m,i] таких, что i<r. Нас самом деле все женщины pw уже замужем, так как, будь любая из них еще не замужем, m выбрал бы ее еще раньше. Чтобы обнаружить помеху второго рода, нужно проверить всех кандидатов pm, которых w предпочитает своей текущей паре m, то есть всех мужчин pm=manForWoman[w,i], i<rwm[w,m], по аналогии с первым случаем, однако нужно не забыть пропустить сравнения с теме woman[pm], где pm еще не женат. Это обеспечивается проверкой pm< m, так как мы знаем, что все мужчины до m женаты.
Полный текст процедуры проверки стабильности выглядит так
Данный алгоритм порождает все возможные варианты решений и его можно доработать таким образом, чтобы находилось либо решение оптимальное для мужчин, либо для женщин, либо среднее. Все зависит от того, для каких целей применяется данный алгоритм.
Суть режима возвратов состоит в следующим. В программе встречаются точки «развилки» — точки в которых необходимо выбрать один из вариантов поведения («альтернатив»). В дальнейшим может оказаться, что выбранный вариант «неудачен» и нужно вернуться к точке развилки и выбрать какую-то другую альтернативу.
Особенность Бектрекинга состоит в том, происходит откат по управлению, а также по данным. При откате программа «забывает» все, что она сделала в результате выбора неудачной альтернативы — данные восстанавливают свои предыдущие значения, отменяются все последствия выбора альтернативы. После отката берем следующую альтернативу и заново выполняем все действия. Проверяем, какие альтернативы для нас приемлемы. Если в данной развилке все альтернативы оказываются неудачными, распространение неуспеха происходит на вышележащие развилки.
Бектрекинг обеспечивает:
— откат по управления;
— откат по данным;
— перебор списка альтернатив.
Существуют действия неподверженные откату. Пример: печать на экран, принтер и т. д.
Развилки можно разделить на локальные (видны только в своей подпрограмме) и глобальные (даже подпрограмма закончена развилка видна).
Поэтому возможно откатное вхождение в процедуру. Процедура полностью восстанавливается, восстанавливаются все локальные переменные, их значения и история их значений.
Варианты организации:
— в качестве альтернатив могут выбираться данные и действия; (массив из процедурных меток)
— список альтернатив: фиксированный, вычисляемый динамически, может не храниться вообще;
— автоматическое изменение порядка набора альтернатив.
Предсказать какая альтернатива принесет успех. (предсказание требует ресурсов.). но перебирая альтернативы в итоге придем к результату.
— возможно отсутствие конструкции “неудача”; (существует конструкция для установления точки развилки или не существует)
— откат возможен: к ближайшей развилке, к указанной статически / динамически, автоматическое определение нужной развилки;
Если перебрали все альтернативы, то неудачу распространяем наверх.
Чтобы не откатываться по шагам, а к той, которую хочешь необходимо:
1. отметить все развилки и откатываться туда
2. откат к развилке определяется динамически.
— автоматическое определение развилки.
Откат в пределах программы
Откат в вызванную подпрограмму
Откат в завершенную подпрограмму.
Если к развилке можно откатиться после завершения процедуры, то развилка наружная.
Необратимое действие – действия, не отменяемые при откате, могут существовать, могут не существовать.
— возможно отключение режима возвратов, динамически / статически, полностью / частично;
— можно связать с сигналом о неуспехе сообщения, и возможность программного анализа.
Существуют языки, которые в своей реализации поддерживают бектрекинг (Пролог, Плэнер). Я в рамках данной статьи рассмотрю эмуляцию режима возвратов на языках, не поддерживающих его в явном виде. В статье для написания листинга я буду использовать паскалеподобный псевдокод, дабы не отвлекаться на синтаксис.
Схема реализация бектрекинга на процедурно-ориентированном языке.
В данном подходе развилки эмулируются при помощи рекурсии, а перебор альтернатив при помощи цикла.
procedure TryAlt(N:trazvilka; var uspeh:boolean);
begin
{Инициализировать перебор переменных}
uspeh:=false;
repeat {выбрать очередную альтернативу}
if {альтернатива приемлима} then begin {записать альтернативу}
if {решение полное(других развилок нет)} then
uspeh:=true
else begin
try(N+1;uspeh);{перейти к слудующей развилке}
if uspeh then
{ничего решение уже построено}
{стереть альтернативу}
end;
end;
until uspeh or альтернатив больше нет
end. Задача о стабильных браках
Предположим, что даны два непересекающихся множества А и В равного размера n. Требуется найти набор из n пар <a,b>- таких, что а из А и b из B удовлетворяют некоторым ограничениям. Критериев распределения может быть много. Мы рассмотрим один из них, который называется правилом стабильных браков.
Пусть A – множество мужчин, а B – множество женщин. Каждый мужчина и каждая женщина указали предпочтительных для себя партнеров. Если пары сформированы так, что существуют мужчина и женщина, которые являются мужем и женой, но которые предпочли бы друг друга своим фактиче6ским супругам, то такое распределение будет нестабильным. Если таких пар нет, то распределение стабильно. Следует заметить, что список распределений остается неизменным и после того, как сделано распределение по парам.
Возможное направление поиска решения – пытаться распределять по парам членов двух множеств одного за другим, пока не будут исчерпаны оба множества. Для решения данной задачи используем схему бектрекинга, слегка модифицировав ее в сторону упрощения.
Procedure tryMan (m : man);
Var
R : rang;
Begin
If m < n then
For r := 1 to n do begin
Взять r-ю кандидатуру из списка мужчины m
If допустима then begin
Записать супругов;
Try (следующий за m);
Отменить брак;
End;
end;
else
записать стабильное решение
end;
Исходные данные представим двумя матрицами, указывающими предпочтения мужчин и женщин.
Var
womanForMan : array [1..n,1..n] of woman
manForWoman : array [1..n,1..n] of manСоответственно womanForMan[m,r] – женщина, находящаяся в списке мужчины m на r-м месте. Аналогично manForWoman[w,r] – мужчина, находящийся в списке женщины w на r-м месте.
Результат представим массивом woman так, что woman[m] обозначает супругу мужчины m. Для симметрии введем man так, что man[w] обозначает супругу мужчины w. На самом деле массив man избыточен, так как в нем содержится информация уже содержащиеся в woman. Информация в массивах man и woman нужна для определения стабильности предполагаемого множества браков. Поскольку это множество строится шаг за шагом посредством соединения индивидов в пары и проверки стабильности после каждого предполагаемого брака, массивы man и woman нужны еще до того, как будут определены все компоненты. Чтобы отслеживать, какие компоненты уже определены, мы введем булевские массивы:
singleMan, SingleWoman: array [1..n] of Boolean
истинность компонента означает то, что соответствующий мужчина (женщина) свободны.
с их помощью можно уточнить предикат допустима как конъюнкцию singleWoman[w] & брак стабилен, где предикат брак стабилен еще предстоит доопределить.
Ключевая задача теперь – уточнить алгоритм определения стабильности. Первая особенность, о которой нужно помнить, состоит в том, что по определению, стабильность следует из сравнения рангов (то есть позиций в списке предпочтений). Однако нигде в нашей коллекции данных, определенных до сих пор, нет непосредственно доступных рангов мужчин и женщин. Разумеется их можно вычислить по значениям womanForMan и manForWoman, но так как вычисление стабильности очень частая операция, целесообразно обеспечить более прямой доступ к этой информации. Для этого введем две матрицы,
Rmw: array [man,woman] of rang;
Rwm: array [woman,man] of rang;
При этом rmw[m,w] обозначает ранг женщины w в списке мужчины m, и rwm[w,m] – ранг мужчины m в списке женщины w. Значения этих вспомогательных матриц не меняются и могут быть определены в самом начале по значениям womanForMan и manForWoman.
Теперь предикат Брак стабилен может быть вычислен точно следуя его определению. Напомню, что нам нужно проверить возможность соединить браком m и w, где w=womanForMan[m,r]. Для начала предположим, что такой брак допустим, а потом попытаемся обнаружить помехи для стабильности этого брака. Таких помех может быть две:
1) Может найтись женщина pw с рангом более высоким, чем у w, по мнению m, и которая и сама предпочитает m своему мужу;
2) Может найтись мужчина pm с рангом, более высоким, чем у m, по мнению w, и который сам предпочитает w своей жене
Чтобы обнаружить помеху первого рода, сравним ранги rwm[pw,m] и rwm[pw,man[pw]] для всех женщин, которых m предпочитает w, то есть для всех pw=womanForMan[m,i] таких, что i<r. Нас самом деле все женщины pw уже замужем, так как, будь любая из них еще не замужем, m выбрал бы ее еще раньше. Чтобы обнаружить помеху второго рода, нужно проверить всех кандидатов pm, которых w предпочитает своей текущей паре m, то есть всех мужчин pm=manForWoman[w,i], i<rwm[w,m], по аналогии с первым случаем, однако нужно не забыть пропустить сравнения с теме woman[pm], где pm еще не женат. Это обеспечивается проверкой pm< m, так как мы знаем, что все мужчины до m женаты.
Полный текст процедуры проверки стабильности выглядит так
Function stable(m, w, r : integer) : Boolean;
Var
Pw, pm, I, lim : integer;
S : Boolean;
Begin
I := 0; s := true;
Repeat
Inc(i);
If i<r then begin
Pw := womanForMan[m,i];
If not(singleWoman[pw]) then
S := rwm[pw,m] >rwmn[pw,man[pw]];
End;
Until (i=r) or (not(s));
I := ;0 lim := rwm[w,m];
Repeat
Inc(i);
If I < lim then begin
Pm := manForWoman[w,i];
If pm<m then
S := rmw[pm,w]>rmw[pm,woman[pm]
End;
Until (i=lim) or (nor(s));
End;
Заключение
Данный алгоритм порождает все возможные варианты решений и его можно доработать таким образом, чтобы находилось либо решение оптимальное для мужчин, либо для женщин, либо среднее. Все зависит от того, для каких целей применяется данный алгоритм.
