Рассмотрим задачу о наборе заданного веса с помощью имеющегося разновеса всеми возможными способами. Отдельно рассмотрим два случая:
1) отсутствие в разновесе кратных гирь, то есть гирь с одинаковым весом;
2) наличие в разновесе кратных гирь.
РАЗЛИЧНЫМИ будем считать наборы с точностью до перестановки гирь. Для этого генерировать наборы будем в ЛЕКСИКОГРАФИЧЕСКОМ порядке (вернее, в порядке обратном лексикографическому), т. е. вначале найдем все наборы, содержащие самую тяжелую гирю, затем наборы, содержащие вторую по тяжести гирю и.т.д. Внутри наборов гири будут упорядочены таким же образом в порядке убывания.
Алгоритм с возвратом будет генерировать наборы следующим образом:
если очередная гиря G меньше текущего веса VES, который нужно набрать, то
— переносим гирю G из разновеса в решение;
— пытаемся набрать уменьшенный вес VES1 (VES-G) гирями весом не более G.
Если для VES1 в разновесе нет подходящей гири или VES1=0 (нашли решение), то происходит ВОЗВРАТ:
— последняя добавленная гиря G из решения возвращается в разновес;
— текущим весом становится VES (VES1+G), а текущей гирей — гиря весом G-1. Если такой гири в разновесе нет, то берем гирю G-2 и т.д.
Различие в работе алгоритма для случая кратных и однократных гирь заключается в следующем:
1) в случае кратных гирь после добавления G к решению уменьшенный вес набирается гирями веса £ G,
2) в случае однократных гирь уменьшенный вес набирается гирями веса <G (начиная с G-1).
При возврате (после генерации всех наборов веса VES, начинающихся с гири G) и в первом, и во втором случае дальнейшие разложения веса VES строятся, начиная с гири G-1. Благодаря этому, в случае кратных гирь мы избегаем повторяющихся наборов.
Для разновеса [5,4,3,2,1,1,1] алгоритм с возвратом построит следующие решения:
[5] [4,1] [3,2] [3,1,1 ] [2,1,1,1]
Дерево поиска, которое строит алгоритм с возвратом, изображено на рис. 8.1.
рис. 8.1
Запрограммируем случай однократных гирь (программа 8.1). Разновес и решения будем хранить в виде списков, упорядоченных в порядке убывания.
Идея поиска:
1. Нулевому весу соответствует решение — пустой список.
2. При наборе непустого веса берем первую гирю из текущего разновеса. Хвост разновеса становится текущим разновесом, а уменьшенный вес — текущим весом.
3. При возврате (или закончились гири, или первая гиря разновеса оказалась недопустимой) первую гирю разновеса убираем и набираем текущий вес с помощью хвоста разновеса.
Таким образом, для непустого веса имеются два неисключающих друг друга правила:
или берем первую гирю, или пропускаем ее.
Благодаря этим трем правилам, мы получим всевозможные наборы веса без повторений.
/* Программа 8.1 «ВЕСЫ». Назначение: */
/* демонстрация алгоритма с возвратом */
domains
list=integer*
predicates
solve1(list,integer,list) % однократные гири
goal
write("Вес ",5," можно набрать: "),nl,
solve1([5,4,3,2,1], 5, S),
write(S),nl,fail.
clauses
/*** Правила однократной процедуры solve1 ***/
solve1(_,0,[]):-!.
solve1([H|T],Ves,[H|T1]):-
H <= Ves,
Ves1=Ves-H,
solve1(T,Ves1,T1).
solve1([_|T],Ves,S):-
solve1(T,Ves,S).
/* Конец программы */
Если убрать ! из правила для нулевого веса, в последнее правило нужно добавить условие Ves>0. Иначе после печати найденного решения произойдет возврат на последнее правило solve1 и это решение будет повторено столько раз, сколько гирь в хвосте T.
Рассмотрим случай кратных гирь.
Согласно алгоритму, при возврате должен происходить сдвиг с гири G на гирю G-1(или меньшую), иначе мы будем получать повторяющиеся решения (например, для трех гирь 1 решение [4,1] будет повторено три раза). В первом случае это происходило автоматически, когда при возврате пропускалась голова разновеса. Если в разновесе будут стоять подряд повторяющиеся гири, то, пропустив голову, мы можем попасть на гирю такого же веса.
Будем хранить разновес в виде двух списков:
в первом — различные веса, имеющиеся в разновесе,
во втором — их кратности.
Так, разновес [5,4,3,2,2,1,1,1] будет представлен в виде двух списков: [5,4,3,2,1] и [1,1,1,2,3].
Правило выбора первой гири преобразуется в правило для однократной гири и правило для кратной гири.
/* Программа 8.2 «КРАТНЫЕ ВЕСЫ». Назначение: */
/* демонстрация алгоритма с возвратом */
domains
list=integer*
predicates
solve(list,list,integer,list) % кратные гири
goal
write("Вес ",5," можно набрать: "),nl,
solve([5,4,3,2,1],[2,1,1,2,3], 5, S),
write(S),nl,fail.
% 1-й список solve содержит веса гирь.
% 2-й список solve содержит кратности гирь.
% 3-й список solve содержит разложение веса.
clauses
/*** Правила кратной процедуры solve ***/
solve(_,_,0,[]):-!.
% 1-я альтернатива: набрали нужный вес.
% Переход на нижние правила solve запрещен.
% Возврат на цель solve верхнего уровня.
% ! можно заменить условием Ves>0 в последнем правиле.
solve([H|T],[1|CT],Ves,[H|T1]):-
H <= Ves,
Ves1=Ves-H,
solve(T,CT,Ves1,T1).
% 1-я альтернатива: однократная гиря H.
solve([H|T],[N|CT],Ves,[H|T1]):-
N>1,
N1=N-1,
H <= Ves,
Ves1=Ves-H,
solve([H|T],[N1|CT],Ves1,T1).
% 2-я альтернатива: N-кратная гиря H.
% Набор Ves1 начинается N-1-кратной H.
solve([_|T],[_|T1],Ves,S):-
solve(T,T1,Ves,S).
% Возврат для 1 и 2 альтернатив:
% H пропускается, берется следующая гиря.
/* Конец программы */
Из приведенных примеров видно, что ПРОГРАММИСТУ НЕ НУЖНО СЛЕДИТЬ ЗА ВОССТАНОВЛЕНИЕМ ИСХОДНОЙ СИТУАЦИИ ПРИ ВОЗВРАТЕ:
удаление гири из решения и возвращение ее в разновес, восстановление текущего веса — это при возврате АВТОМАТИЧЕСКИ ДЕЛАЕТ САМА СИСТЕМА. Для того чтобы система могла осуществить возврат, правило solve было сделано НЕДЕТЕРМИНИРОВАННЫМ (или берем первую гирю, или пропускаем ее).
