|
||||||
Smart Moves: Intelligent Pathfinding.'��������� ������ ����' Original
article � Brian Stout, 1997 ���� ����� ���� �� ����������� ������, ���������� ��������� �������, �������� ����������, ������� ����������� ������� ����������� � ���������� �������������. ��������� ��������� ������ ���� �� ����� ����������, �� �� �������� ��������� ���������� ������� ���������. ��� ����� ������, ��� �������� ��������� ��������. �������� ��������� � ������ ���� �������� ����� �����������. ������������� �������� � �������� �������� ������������� ����������� �� ������������ � ����. ����� �������� ����� ��������� �������� ���: ���� �� ���� �� ���������� ������� ����������� ��� �������� � ���� ���� ��� ����������� �������� ��� �������� ��������� ���� ����� ������� ������ ����������� � ����������� �� ���������� ������ ���� ������ �����, ��� ��� �� ����������� ������ ������� ����������: ���, ��� ���������� ����� - ��� ������������� ��������� ������� � ��� ����, � ������� ������������ ������������. ��� ������ ������� �������� ����� ����������. ��������� ��������� ������ ���������� �������� � ����: ���� ������� ������ ����������� ������������� ���� ����� ����� ��������� ���������� ��� ���� ���������� ������, ���������� ��������, � ������� ����������� �������� ������ ��� ������������ ����� ���� ����� ������� �����������. � ����������, ��� ������ �� ����� ������ �������� ���������� ��������, ������� ������� �� ������� � ������ �����������, ������� � ������ ���� � ���������� ���������� ����� ������ ���������, ��� ��������� ��������� ����� ����������. � �������, � �������� ������ ������ � �������� �� ������� ��������� ����������, ������� ����� ������ �������� � ������� ����������� � ���������� ��������. � ����������, ������ �� ���� ���������� ������������ � �������� ��������� ��������� ��� ������� �� ����� �����. ��� �������� ������������ ��� ������� ��������� �������, ������� "��������" � ����� ������, ��� ���������� �������� ��������� ���� ��� �������, � �������� ��������� (��� ������� ����) ���������� ����� ����������� ���� ��� �������� ������ ������. ���������� ���� ���������� � ������ ���� � �������������� ������������ ������� ������� ���������: ��������� ��� ���� ����� ������������ ������, ����������� � ������������ ������, � ������������ � �������� ������ ������������� ����������� � �������� ��������� ��� ������� ����. ������������ ��������� �� ���������� � ����� ��������, �����: �������� ���������������� ����������� ��� ������ � ������� (IDDFS). � ���������������� � ��������� ������ � ������� ���������� ��� ���� �������� - ����� ���������� ������� ���������. ���� ��� ����� ������� ���������, �� ���� �� ����� ������; ���� ������� �������, �� ������������ ����� ��������� ����� ������� �������, �������� ������� �������, ��� ����� ���� � ����� ������� ����������. ��� �������� �������� ����������� ����������� - �������, ��� ������� ����������� ����� � ������� � ��������������� �������� �� ��� ���, ���� ���� �� ����� ������. ��� ������ ���� �� ����� �� �������� � ������� ������ �������, � ����� ������ � ������� ������ ���������� �� ������ �� ������ � ����. ���� ����� �������� �������������� ����������� ����� ���� ���������� ���������� �� ������� � ������. ��������� ���������� ��� ������ ����������� ����� � ��������� ������������� �������� A* (�������� ��� "�-���������"). ���� ������������� ����� ��������� ��� ���� �� ����������� ���������� ��������, ������� ����� ���� ����. �������� ������� ��������� ���������� � ����: f(n) = g(n) + h(n) ���: f(n) �������� ������, ����������� ����
n
������������� �����. ���������� �������, ��� �������� �� A* ������� ������������� � ��������������� ��������. �������� ����� ������� ������������, ������� ������ ����� �������, �������� ���������������� �������� � ����� �������. �������������� - ��� ������������������ �����, ������� ����������� ���� ����� � ����� ���� ���������� � ���� ���, ��������� ����� ������ ������� ���� �� ���� ���. ��������, �������� ������ ����� ����� ��� ����, ����� �������� ���� ��������� � ������. ����� ������������������ ����� ���� ������������ ��� ���� ��������� ���������, ������ ��������� ��������� ��������� �����. � ���������� � ����������, ����� � ����� ������ ������� ����� ����� ���� ����������� ��������, ���� ��� ����� ������� �� ���������, �������������� ������� ������ �� ������� �������� �������. � ������ ������ ����, ����� ����������� �� ������� ����������� �������, ��� ��������� ��������. ���������� ���� ��� ��� ��������� ������, ������� ��������� ����� ����� �������� ���������; ����� ����� ������������ ����� �������� ���������, � ������ �� ������� ���� ��������� ��� ��������� �����. ��������, � �������������� ����� ������, ����������� ���� �������������� ���� �� ������� � ����� ����� � ������� ������������ ��������� ���� ������� �� ��������� ������������ "������". ��������� ������ � �������� ��������, ������������� ����������� ������� ���������, ��� ���� ������ ��������� �� ������� �� �������, ����� � ������, � �� ��������� (���� �������� �� ������ �����) � ������; � ����� ���� ����� ������ ������ ����� �� �������� ����� ������� � �������� �� ������� ����� ������� � ����������. � �������� ������� ������� ����� �������� ���� �� ����� ����� ������ � ������, ������� ����� ���� ������ �� ���� ����� ��������� � ���������� � ���� ����� ������� � ������ �������. ������� ����� �������� ������� � ���������������� ������, ��� ���������� ������ ��� ��������� �� �������� ��������������� ������. ���������� ��������, ��� ����������� ������� �������� � �������� � ������� �����������; ��� ���������� �������� ���������� ��������� �������� �������, �������� ��� ���������� (��� ����� ���� � �� ������ ��������). ���������� �* � �����. ���� ����� �* ��� �� ���� ���������� ����������, �� ����� ���� �������� �������������� ����������� ������ � ����������� ����������� ������. ��� ������ ������������ ��� �������� ��������� ������. ������ - ��� ������������� ������� �������. ��� ��������� ����� ��������. ��� ������� ������� ������ ���� ������������? ����� �� ������� �������� �� ������ �����? ��������� ����������� ����� ��������� ��������������� � ����� ��� ����� ����������� �� �������������? ��� ����� ������������ ��������� ��������� ����� � �������� �� �����? ����� �� ��� ������������ ��������������� �� ����� ��� � ��������� ����������? ��� �������� ������ ����� ������ �������� ����������� ����������? ������ �� ��� ������� ������� �� ���� ���� � ������������� ������������ � ����������� �����������. ������ �������� ������������ ��������� - ��� ���� ��� ��������� ������, ������� ����� ����������� ����� ��������. �� ������ ������ ��������� ��������� ��������� ������, � ������� ����������� ����� �������� �������� ��������� ����:
������ �������� �������� ������� - ����� ������������ ������ ��� ��� ���������? ����� ������� �� ���������� � ����������� ����, ����������� ����������� � ������������ �������. �� ������� ������ ��������� ����� ������� ��������� ������ - ������ Open � Closed. ���� �� ���������� �������� �������, ����� ������� �� ������, ��������� ������ � ���� ��� ����������� ������ ���� ���� ��� ���. ��� ���� ��������, ������� ���������� ��� ������ �� ������� Closed:
��� ������ Open ����� ����� �� ��������, ��� ��� ������ Close, ����:
������ Open ����� ������������� ��� ������������ �������, ��� ��������� ����������� ���� �������� ����� � ������ ����������� - � ����� ������ � ��������� �������. � ������������ � ���������� ���� ���������� ���� ��������� ��������� �������������: ��������, ��������������� ������; ��������������� ��������� ������; ������������� ������; ������������� ��������� ������; ���� (��������� ������������ � heapsort); ���������������� �������� �������. ���������� ��������� ����� �������� ��������: 2-3-4 �������, ������-������ �������, ���������������� �� ������� (AVL trees), � ���������������� �� ���� �������. ���� � ���������������� ������� ����� ������������ ��������������� ����������� ������� �������, �������� � ������; ������, ���� ���������� ����� ����� ������, ������� �� �� �������� ����� ��������� ��� ������������. ����������� �*. ���������� ��������� �������� �������� �������� ������, ����� �������� ������� ���������� ��� ������������� ������������ ��������: ������� �����. ����� �� �������� ������ � ������������ �� ������ �������� ��������� ����������� �� ���������� ����� � ������ Open; ����� ������ ����� � ���������� �������� ����� ����, ������ ������������� ���� � ��������� ���������. ������ Closed ����� ����� ���� ���������, ���� ������ ������ ������ � ���� ����� ���������� ���� � �������� ���������. ���� �������� �� ����������� ������������� ����, ��� ��� ���� ������� � ���� ����� ���� ��������, �� ��� ����� ����� ��������� ����� �������� ����. �������� ���������������� ����������� ��� A* (IDA*). �������� ���������������� �����������, �������������� ��� IDDFS, ��� ����������� �����, ����� ���� ����������� � ��� A*. ��� ��������� ��������� �� ������������� ������� ������ Open � Closed. �������� ������� ����������� �����, ���������� ���������� ��������� ���� g(n), � ����� ������������ ��� ���������� ��������� f(n) = g(n) + h(n) �������� ��������. �������� ����� � �������� ��������� ������ h(start), � � ������ ���������������� ��������, ������������� ����� ������ ��������� ������ ������������ �������� f(n), ������� ��������� ������� �������. ���������� ��� IDDFS ����� ������� ������� ��������, IDA* - �������������� ��������� � ������� ������� � ������ ����� ������������� �������. ������������ ��������� h(n). ��� ����������� ����, ���� ������������� ����������� ���������� ��������� ���� ������� ����, �� A* ����� ���� ����� �������������. �� ���� ����������� ������� ������, �� ��� ���������� ���� �� ������������� �������������. � ����� � ������� �������� ��������� ���������� ��������� ����� - �� ����� �� ��������� - ����� �������������������� � ���������� �������������� ����������, ����� ����� ������ ������ ����� �������������� ������ � ��������� ���������� ����. ���������� � ������ ����������� A*, ������ ��� �� ����������� ���� ���������� ��� ������ ���� � �������������� ������������. ����������� ������� ������������. ��� ����������� ���� ������ ������ ������������, ��� ������������ ������� �� ���������� ��� ������������� ������. �� ���, ���� ������� ������������ ����������? ���, ���� ������� � �������� � ����������� ��������� � ���� ����������� �������� � ����� ���� ��������� ����� ������������, ��� � ���������� ������? ������� 11A ���������� ��������� ������������ ��������. ��� ������ �� ��� ������� ������, ����� ��������� � ������� ������������� � ������� ����� ������� ������������ ��� ��������� �������. �� �����������, ��� ������ ������� ������� ������� ��� �������� ������������ ������������ � ���������� ���������� ���������. ����� �����, ��� ������ ���������� A* ��� ������ ��������� ����. ������� ������������� ������������ ��������: ������. ������� �������� �������� ��������� �������� ����� �� ����������� ������������ ������. ������, ���������� ����� ��� ��� �����������, ������������ ��������; ������� �����, ���������� ��������������� �����, ����� ���������� �������������� ��� ���������� ������������ ��� ������������. ��� ������������� ����� ������� ��� �������� ���������� ��������. (��. ���. 11B.) ����� ���������. ��� ������� ������ �����������, ����� ��������������� �� ����������� ������, � �������� �� ������������� ����� ������ ����������� (�� ����������� ����������, ����� �������� ������������), ��� ���� ����� ��������� ������������, ���� ��� ������ ����� ����� (�� ����, ����� ���� ��� �����������). ��� ������ ����, ����� ������������� � �������� ������������� ����� ����� ������� � ����� ������ ����������� �����. �������� ������� 11C. �������� ��������. ��� ������ �����������, ������������ �� ���������� �������������� ������������� ����������� �� �������� ��������; �������������� ������� ����� ���� ������ ��������� ��� ����� �� �������� ���������. ���������� ��������� ���� ������������ ������������: C-Cells (������ ������� ����������� � ��������� ������� ��������; ��� ����� ��������� ������������) � ���������� �� ������������ ������� (������ �������� ������� ����������� ����������� �����, ������������ �������, �� ��������� ����������� ��� �����; �� ���� ���� ��������� � �������� ������������ � ��������� ������� ������� ���������� ����������). (��. ���. 11D.) ��� �������� ���������� ��������, ������������ ����������� �� �������� � ���������� ���������� ������������. ����� ������������ ��� ����������� ������ ����������� �� ������ ����������� ������. ���� ������ ��������� �� ������������ �����, ��������� ������� ���������. ����������� �������. ������� �������� ��������� ������������ ����������� �� ��������. ������ �������, �� ���������� ����������, ����������� �� ������ ������� ��������. ������ ���� ��������� ������������ ��� ������ ����. (��. ���. 11E.) ���������� ��������. ������������ ����� �������� ������������� ��������������� ��� �������, ����� �������� ���������� ����� ��� ���. ����������� ���, ���������� ����� ������������ ����� ����� �������� ������������� (������� �����), � ��� ��� ������������ ��� ������ ����. (��. ���. 11F.) ������������� ����. ���� ������, �� ��������� �� ����������� ������������, �� ������ ��������������� ��������, �������, ��� ������ ����������� ����� ������ ���� ������������� ������������� ����, ���� �������� ������� ��������������� ���������� �� ����; ��� �� ���������� ���������� ���� ���������� � ����. ����� ������� ���������� ��������� ������� ����������� ����� ������������� � ������������� �������� � ������ ������������� � ���� �����������. �������� ����� ������� ������� � ��������� ������� � ��������� �������; ���������� ��������� ������� ������ �� ����� �����. ���. 11. Original
article � Brian Stout, 1997 |