|
||||||||||||||||||||||||||
����� � �������, ��������, �������������������:
|
(45) |
���������� di,j ����� ����� �������� ��������, ����� �������, ����������� ����� ����� ���� �� d0,0 � dm,n � ����� �����������.
��� ����������� ������ �������� ���� � ����� (���, �������� � ������ [Aho, Hopcroft, Ullman, 1974]) ����� ������������ �������� �������� (Dijkstra), ������� ������� ��� �� ����� O(mn log mn). ������, ��������� ����� ��������� ����� � ����� ����������� �������, ��������, ����� ������������� ����������������. ���� ����� ��������, ��� ����� ��������� ����� ������ ������� d, ������� ����� ���������.
�������� dm,n ����������� ������ �� ������ di,j �� ��������� ���� �� (0,0) � (m,n). �������� ��������, ��� ��� ���������� ������� ������� O(n), ��� ��� ����� ����� ���� �������� �� ������ m+n ���. ���������� ������ ���������, ����������� �� dm,n ��������� �����, ������, h. �� 11 ����� ������, ��� �������� dij ��������� ���������� ����� ������ ���� � ����� �����������. ����� �������, ���� dm,n < h, � ��������� di,j > h, �� ��� di,j �� ����� �������� ������ ���� � (m, n).
��������� ����� wmin ����������� ���� ���� ������� � ��������, �� ����
![]() ![]() ![]() ![]() |
(46) |
��� �������� . ��� ��������� ������������� ����� wmin > 0. ����� ����, ����������� ��������� ������� ���������� ������ ������� k
[-m, n] ����� �������, ����� ��������� k �������� �� ��������� (i, j), � ������� j - i = k.
���������� ������������ ���� �� (i, j) � (i', j') � ����� �����������. ������� (i, j) ����� �� ��������� k = j - i, � (i', j') � �� ��������� k' = j' - i'. ���� k' - k < 0, �� ���� �������� �� ������ |k' - k| �������� (������������ ���), � ���� k' - k > 0, �� ������ |k' - k| ������� (�������������� ���). �� (45) �� ����� ���������:
(47) |
����� �������, di,j > |j - i|*wmin ��� ������� (i, j) �� ���� �� (0,0) � (m, n). ����� ����, ��� ��� di,j < dm,n ��� ������ (i, j) � ����, �� ����� ���������:
(48) |
��� ���������� dm,n ���������� ����������� �������� �� ������������ ����� dm,n/wmin < j - i < dm,n/wmin. �� ����� ����, ��� ����� ����� ������ ��� ������, ��� � ����� �������� ����.
���������� ���� �� (0, 0) � (m, n) � ����� �����������. ��� ����� ��������� �� ��� ����: �� (0, 0) � (i, j) � �� (i, j) � (m, n). �� (47) �� ����� ���������:
![]() |
(49) |
���������� ��� ������: ������, ����� j < i, � ������, ����� j > i. � ������ ������ (49) ��������� ���
![]() |
(50) |
� ������ ����, ��� j - i ����� �����!!!!!!!!!!!!!!!!� 0, ������ ��������
![]() |
(51) |
��� ������, ����� j > i, ���������� ��� �����������, � ������, n - m > j - i, � n - m < j - i. � ������ ������ (49) ��������� ���
![]() |
(52) |
� �� ������
![]() |
(53) |
� ������ ���� �����, ��� � ������ ������ j - i �������� ����� ������ > 0, ��������
![]() |
(54) |
��������� (51) � (54), �������� ��������� ����������� �� j - i ��� ����� (i, j), ������� �� ��������� ���� �� (0,0) � (m, n) � ����� �����������:
![]() |
(55) |
���������� �� (55) �������� ��, ��� ��� �������� ���������� ����������� d(x, y) < h ����� ������������ ����������� di,j, ������� �� ����� ����� ����������� -p � n-m+p, ��� p = [(h/wmin - (n - m))/2].
�������� ��� ���������� ����� ���������� �������� �������� �� ������� (19). �������� ���������� ������������� ��������, ���� �������� �� ����������, � �������� dm,n, ���� ��� ������ ��� ����� ����������. �������� �� ����������� � ����������� ������, ���������� ���������� (52), ��� ��� ���������� ������ ���� �� ������� ���� ����� �������� ���� ����� �������� �� ����������� ��������� ������� � ��������. � �� ����������� ������ ����������� �������� di,j �� ������������ �����, ���������� (55). �� ���������� ���� ���������� ������������� �������� dm,n ������������ � ���������.
������� 19: ��������� �������� ���������� ����� ����� ��������distance_test(h) if h/wmin < N - M - ����������� ������ RETURN(-1) else - ������������� P = INT((H/Wmin - (n - m))/2) d0,0 = 0 for j = 1 to min{n, n - m + p} d0,j = d0,j-1 + w( , yj) - ��������� dm,n for i = 1 to m for j = max{0, i - p} to min{n, i + n - m + p} if j = 0 di,0 = di-1,0 + w(xi,
) else di,j = min{di-1,j + w(xi,*), di,j-1 + w(
,yj), di-1,j-1 + w(xi,yj)} if dm,n > h return(dm,n) else return(-1)
������� 20: ���������� ���������� ����� �������� ��������h = (n - m + 1)wmin while (d = distance_test(h)) < 0 H = 2H
��� ������ �� m+1 ����� ���������� ����������� ��������� ������� �� ����������� n-m+2p+1, ��� �������� O(h), ��� �������� ����.
![]() ![]() |
(56) |
����� �������, ��������� �������� ����������� �� ����� O(hm), � ������� O(hm) ������, ���� ����������� ������ �������� �� ������������ �����. �������� ��������, ��� ���� ��������� ������ �������� ���������� ����� ��������, �� ���������� � ������ ����� ��������� �� O(h) �����, ��� ��� ��� ���������� ������� ������ ��������� ������ �������� ���������� ������ (�������� ��������� � �������� ��������).
����� ����� ����������� ���������� ����� ����� ��������, ����� �������� ��������� ���������� �������� � ��������������� ������������� ���������� h, ���� �������� �� ����������. �������� ��� ����� �������� �� ������� 20. � ������ ������ ������������� ����������� �� ��������� �������� ���������� ���� wmin, ������� ����� ��������������� �����������. �� ���������� d ��������� ���������� ����� ����� ��������.
��������� ��������� ��������� �������� h0, ���������, ������ 2h0, h1, ���������, ������ 22h0, h2, � �.�. ����� �������, r-� �������� hr ����� 2rh0. ���� ��� ����������� d(x, y) ��������� r ������� distance_test, �� ����� ��������� ����� , �� ���� O(m(2hr - 1)), ��� ����� O(mhr). ������, ��� ��� d > hr/2, ����� ��������� ��������� ����� O(dm). ����������� ������������������ �������������� ����� ���� ��������� �� ���������� ��� � ������ �������-������.
������� ���������� ����� ������� ������, ����� ���� ���� �������� �������������� ����� (�� ���� ���������� ���������� �����������), ��� �������� ����� ��������� ���������� � ������ � ��������� ����� �����������, �� �������� O(dm), ������ ����� ���������� d(x, y).