2. Восстановление ответа.
Но помимо нахождения наименьшей стоимости маршрута, разумеется, хотелось бы найти и сам маршрут минимальной стоимости.
Такая задача называется задачей «восстановления ответа».
Для восстановления ответа будем для каждой точки i запоминать номер точки Prev[i], из которой кузнечик попал в точку i,
если он будет передвигаться по пути минимальной стоимости.
То есть Prev[i] — это точка, предшествующая точке с номером i на пути минимальной стоимости (также говорят, что Prev —
это массив предшественников).
Как определить Prev[i]?
Если C[i − 1] < C[i − 2], то кузнечик попал в точку i из точки i - 1, поэтому Prev[i] = i - 1,
иначе Prev[i] = i - 2.
Модифицируем алгоритмы вычисления значений целевой функции, одновременно вычисляя значения Prev[i].
Пример программы на языке Python:
C = [0] * (n + 1)
C[1] = Price[1]
Prev[1] = 0
for i in range(2, n + 1):
if C[i — 1] < C[i — 2]:
C[i] = C[i — 1] + Price[i]
Prev[i] = i — 1
else:
C[i] = C[i — 2] + Price[i]
Prev[i] = i — 2
Пример программы на языке Pascal:
var
C, Price, Prev: array[0..100] of longint;
j, i, n: longint;
begin
readln(n);
for i := 1 to n do
read(Price[i]);
for i := 0 to n do
C[i] := 0;
C[1] := Price[1];
Prev[1] := 0;
for i := 2 to n do
if C[i - 1] < C[i - 2] then begin
C[i] := C[i - 1] + Price[i];
Prev[i] := i - 1;
end else begin
C[i] := C[i - 2] + Price[i];
Prev[i] := i - 2;
end;
end.
Теперь для восстановления пути необходимо начать с точки n и переходить от каждой точки к ее предшественнику, пока путь
не дойдет до начальной точки с номером 0.
Номера всех вершин будем добавлять в список (массив) Path.
Пример программы на языке Python:
Path = []
i = n
while i > 0:
Path.append(i)
i = Prev[i]
Path.append(0)
Path = Path[::-1]
Пример программы на языке Pascal:
i := n;
j := 1;
while i > 0 do
begin
Path[j] := i;
i := Prev[i];
inc(j);
end;
Path[j] := 0;
for i := j downto 1 do
write(Path[i], ' ');
В конце в список Path добавляется начальная вершина номер 0, которая не была обработана в основном цикле, а затем весь
список Path разворачивается в обратном порядке (т. к. вершины добавляются в обратном порядке, от конечной к начальной).
Но можно обойтись и без списка Prev.
Мы в любой момент можем определить, из какой точки кузнечик пришел в точку i, если сравним C[i - 1] и C[i - 2].
Поэтому решение о том, к какой вершине переходить при восстановлении ответа можно принимать непосредственно при
восстановлении ответа, сравнив C[i - 1] и C[i - 2].
Путь восстанавливается через ту вершину, для которой значение C будет меньше.
Пример программы на языке Python
Path = []
i = n
while i > 0:
if C[i — 1] < C[i — 2]:
prev = i — 1
else:
prev = i - 2
Path.append(prev)
i = prev
Path.append(0)
Path = Path[::-1]
Пример программы на языке Pascal:
var
C, Price, Path: array[-1..100] of longint;
j, i, n, prev: longint;
begin
readln(n);
for i := 1 to n do
read(Price[i]);
for i := 1 to n do
C[i] := 0;
C[-1] := -1;
C[0] := 0;
C[1] := Price[1];
for i := 2 to n do
C[i] := min(C[i - 1], C[i - 2]) + Price[i];
i := n;
j := 1;
Path[j] := i;
while i > 0 do
begin
inc(j);
if C[i - 1] < C[i - 2] then
prev := i - 1
else
prev := i - 2;
Path[j] := prev;
i := prev;
end;
Path[j] := 0;
for i := j downto 1 do
write(Path[i], ' ');
end.