2 c127:
А насколько заливка будет быстрее волнового алгоритма?
И почему Дейкстра будет быстрее их обоих? Ведь волновой алгоритм есть в оптимизированном варианте, когда идёт при распространении волны не просматривается не вся матрица, а только волновой фронт. Вроде даёт преимущество в 3-4 раза по сравнению с базовым вариантом.
Правда, при реализации оптимизированного волнового алгоритма на Яве встаёт вопрос - как хранить этот самый фронт? Я делал так:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
List[] front = new List[] { new ArrayList(), new ArrayList()};
byte [][] mapCopy;
private void expandFront( int fIndex, int iteration, int i, int j)
{
if (mapCopy[i][j] == PASSABLE) // Поле проходимо
{
mapCopy[i][j] = ( byte ) iteration;
front[fIndex].add( new Pair(i, j));
}
}
...
// В методе поиска пути
class Pair
{
int x, y;
Pair( int x, int y)
{
this .x = x;
this .y = y;
}
}
front[ 0 ].add( new Pair(endI, endJ)); // Добавляем конечную точку к фронту
int frontIndex = 0 ;
int nextFrontIndex = 0 ;
Pair pair;
while (nI < MAX_ITERATION && !found)
{
nextFrontIndex = (frontIndex + 1 ) % 2 ;
front[nextFrontIndex].clear();
// Проходим по текущему фронту волны
for ( int i = 0 ; i < front[frontIndex].size(); i++)
{
pair = (Pair) front[frontIndex].get(i);
/* Если при распространении фронта попадём
* в начальную точку, то прекращаем
* распространение волны
*/
if (mapCopy[pair.x + 1 ][pair.y] == START ||
mapCopy[pair.x - 1 ][pair.y] == START ||
mapCopy[pair.x][pair.y + 1 ] == START ||
mapCopy[pair.x][pair.y - 1 ] == START)
{
found = true;
break ;
}
expandFront(nextFrontIndex, nI + 1 , pair.x + 1 , pair.y);
expandFront(nextFrontIndex, nI + 1 , pair.x - 1 , pair.y);
expandFront(nextFrontIndex, nI + 1 , pair.x, pair.y + 1 );
expandFront(nextFrontIndex, nI + 1 , pair.x, pair.y - 1 );
}
frontIndex = nextFrontIndex;
nI++;
}
Но есть подозрения, что на матрицах порядка 50x50 и меньше это работает дольше, чем если бы проход шёл по всей матрице в поисках фронта. Предполагаю, что время тратится на new Pair(x, y) и вызовах expandFront - наверное, всё ж было бы лучше не оформлять его в отдельный метод.
Или, может, я выбрал порочный путь?
