powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на матрице - алгоритм Дейкстры или что-то ещё?
22 сообщений из 22, страница 1 из 1
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32771718
ponomarevvb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Доброго всем времени суток.
Есть такая задача. Дана матрица из 0 и 1. Из данной клетки с нулём нужно найти путь (если таковой есть) по нулевым клеткам до другой нулевой клетки. Перемещение по клеткам - верх-низ, право-лево.
Как решить такую задачу (как она хотя бы называется, чтобы в Инете посмотреть)?

Единственное, что кроме перебора пришло на ум - составить соответствующий граф (клетка - вершина) и использовать алгоритм Дейкстры, но это, наверное, будет небыстро - при матрице, например, 20х20 (примерно такие будут в реальных условиях) получится граф из 400 вершин, да ещё и сложность алгоритма o(n^2)!
Заранее спасибо.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32771721
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
подойдёт вариация на тему "поиск в ширину" в неориентированных графах, если нужно найти минимальный путь.

Суть подхода в том, что бы на каждом шаге итерации
определять набор клеток достижимых из стартовой за k-шагов(k-номер шага).
Следующий шаг использует реультаты предыдущего.
Cложность алгоритма порядка n^2 (матрица nXn);
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32771730
ponomarevvb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
NotGonnaGetUsподойдёт вариация на тему "поиск в ширину" в неориентированных графах, если нужно найти минимальный путь.
Мне необязательно нужен минимальный. Моя задача - найти любой путь с обходом препятствий. Наверное, мне больше подойдёт поиск в глубину, а не в ширину. Но пока что-то не нашёл его толковых описаний - всё больше листинги, а хочется вникнуть в суть :-)
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32771776
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Можно и поиск в глубину.
Он существует в двух варинтах, поиск по всем путям в графе и поиск по всем вершинам в графе.

В обоих случаях при поиске в глубину скачут от узла к узлу в определённом порядке, как только двигаться становится не возможно (некуда или упёрлись в уже пройденный узел) возращаются назад и согласно порядка пробуют выбрать другой узел и т.д.
Уже пройденный узел это либо узел на текущем пути(1ый вариант), либо когда-то уже посещённый узел(2ой вариант).

Во втором варианте сложность порядка n^2, в первом много больше.

В среднем теже самые n2 с точностью до константы.

Можно сделать оба и протестировать :)
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32772097
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если в матрице достаточно много препятствий то подойдет алгоритм, предложеный NotGonnaGetUs. Я бы еще добавил "волновой алгоритм" описаный на www.codenet.ru. как вариации на тему.
Лично для меня больший интерес представляет случай, когда препятствий мало и они сгруппированы в области (наподобие непроходимых гор или болот). В этом случае я бы предложил ввести функцию "опасности" или "близости препятсвия" выразив ее аналитически. А дальше - вспоминать алгоритмы поиска локальных экстремумов в условиях двух переменных. Может она и не всегда даст результат. Зато появится выбор.
1) Использовать в игре рекурсивный алгоритм который всегда даст результат но может скушать процессорное время.
2) Попробовать нацелить на лабиринт алгоритмы нечеткой логики, нейроные сети и т.п.
А если распараллелить два алгоритма и ожидать первого результата то вообще здорово!
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32772111
ponomarevvb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Всем большое спасибо.
2 mayton: codenet - рулит! Жаль, раньше про него не знал.
2 NotGonnaGetUs: заставили покопаться в конспектах. Вспомнил много инетерсного :-)
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32772656
c127
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
2 ponomarevvb

>Единственное, что кроме перебора пришло на ум - составить соответствующий граф (клетка - вершина) и использовать алгоритм Дейкстры, но это, наверное, будет небыстро - при матрице, например, 20х20 (примерно такие будут в реальных условиях) получится граф из 400 вершин, да ещё и сложность алгоритма o(n^2)!

Не слушай глупости, ты все правильно сказал, используй алгоритм Дейкстры. Это будет ОЧЕНЬ быстро. Поверь мне или почитай оценки алгоритма и посмотри для своего случая раздяженной (4 соседа) матрицы. Его еще можно улучшить до O(n*ln(n)), точно не помню. Но это наверняка не понадобится, ведь это оценка самомого плохого случая, а у тебя случай очень хороший. Дейкстра легко работает на матрицах порядка 10^3*10^3.

Есть еще алгоритм, который тебе подойдет, если я правильно понял задачу. Это алгоритм заливки односвязной области G цветом. Идея следующая. Выбрать точку G, построить горизонтальный отрезок до пересечения с границей. Множество точек, отрезка граничащих с G назвать S. Для каждой точки S построить вертикальный отрезок до пересечения с границей G или с S, включить граничные точки в S. И т.д., пока есть что добавлять в S.

Посмотри в кингах по компьютерной графике. Этот алгоритм вроде бы самый быстрый. Он быстрее Дейкстры, но Дейсктра универсальнее, например работает для всех графов, я использую его.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32772823
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Т.е. n^2*ln(n^2) это лучше чем n^2?
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32772854
Фотография Timm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2 mayton: Волновой алгоритм и поиск в ширину - это одно и то же.
Его использование, на мой взгляд, наиболее логичное решение.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32772876
Дмитрий Валуев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Для этой задачи пожалуй лучше алгоритм кратчайшего пути Дейкстры.
Есть опыт его использования на сильно разряженных матрицах примерно 900х900. Дает приемлимое быстродействие даже на медленных компьютерах, если не хранить нулевые элементы матрицы смежности.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32773318
ponomarevvb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2 c127:
А насколько заливка будет быстрее волнового алгоритма?
И почему Дейкстра будет быстрее их обоих? Ведь волновой алгоритм есть в оптимизированном варианте, когда идёт при распространении волны не просматривается не вся матрица, а только волновой фронт. Вроде даёт преимущество в 3-4 раза по сравнению с базовым вариантом.
Правда, при реализации оптимизированного волнового алгоритма на Яве встаёт вопрос - как хранить этот самый фронт? Я делал так:
Код: plaintext
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 - наверное, всё ж было бы лучше не оформлять его в отдельный метод.
Или, может, я выбрал порочный путь?
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32773742
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Твой алгоритм:

матрица 3000x3000, заполнение единичками 30%,
поиск от одного угла, до противоложного занимает ~3.6сек.

матрица 4000x4000, заполнение единичками 30%,
поиск от одного угла, до противоложного занимает ~7сек.

n^2 на лицо, а чего ещё ожидать от простого решения?


Правда тупые эвристики будут на порядки быстрее, если процент невелик... (тот же поиск в глубину с выбором следующей клетки в направлении ближайшем к финишной точке) , а в худшем случае теже самые n^2 :)
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32774512
ponomarevvb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
NotGonnaGetUs
матрица 3000x3000, заполнение единичками 30%,
поиск от одного угла, до противоложного занимает ~3.6сек.

матрица 4000x4000, заполнение единичками 30%,
поиск от одного угла, до противоложного занимает ~7сек.

Хм, интересно...
А можно подробнее об условиях тестирования? У меня, например, на матрице 4000x4000 при заполнении единичками где-то на 33-34% (заполнял ramdom'ом, каждый 3-й 0 менял на 1) ищет путь из угла в угол ~ 500 мсек. В неоптимизированном варианте (тупой проход всей матрицы) ~ 30 сек.
У меня:
CPU Celeron 600 MHz
RAM 128 Mb
Win 2000
JDK 1.4.2
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32774539
c127
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
2 NotGonnaGetUs

>Т.е. n^2*ln(n^2) это лучше чем n^2?

Нет, это хуже. А n*ln(n) - лучше.

2 ponomarevvb

>А насколько заливка будет быстрее волнового алгоритма?

Не знаю. Заливку использовал лет 15 назад, тогда же читал о ней. Вроде он самый быстрый для этой задачи. С тех пор не интересовался, дейкстра устраивает. Основной недостаток - заливка чувствительна к структуре графа, у нас структура бывает меняется. Дейкстра универсальный.

>И почему Дейкстра будет быстрее их обоих? Ведь волновой алгоритм есть в оптимизированном варианте, когда идёт при распространении волны не просматривается не вся матрица, а только волновой фронт.

Дейкстра не будет быстрее, будет медленнее, по крайней мере чем заливка. Насколько я понял волновой алгоритм и есть модифицированный дейкстра для случая ребер одинаковой длины (веса).

По-моему заливка сложнее в реализации чем дейкстра, поэтому на малых матрицах заливка может оказаться медленнее за счет инациализации и пр. На больших наверное будет быстрее.

>Но есть подозрения, что на матрицах порядка 50x50 и меньше это работает дольше, чем если бы проход шёл по всей матрице в поисках фронта.

Может быть. Но в таких случаях ИМХО не нужно заниматься вылавливанием блох. Тогда не нужно будет переписывать когда размеры увеличатся. Суммарный выигрыш времени работы для всех экземпляров программы врядли превзойдет твое время, потраченное на переписывание алогоритма.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32775165
ponomarevvb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо всем, господа!
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32775378
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
c1272 NotGonnaGetUs

>Т.е. n^2*ln(n^2) это лучше чем n^2?

Нет, это хуже. А n*ln(n) - лучше.


Либо Дейкстра у нас разный, либо лыжи.
Алгоритме дейкстры применим к произвольному графу,
сложность задаёт число вершин. У нас их n^2.
Поэтому дейкстра заведомо медленее любых решений, что были тут перечисленны.

Если конечно не называть их модифицированной дейкстрой :)


ponomarevvb
Хм, интересно...
А можно подробнее об условиях тестирования? У меня, например, на матрице 4000x4000 при заполнении единичками где-то на 33-34% (заполнял ramdom'ом, каждый 3-й 0 менял на 1) ищет путь из угла в угол ~ 500 мсек. В неоптимизированном варианте (тупой проход всей матрицы) ~ 30 сек.

Я просто запустил то, что ты запостил и посмотрел :)
Только тип массива был не byte[][], а int[][].
проц п4 2.4, 512мб остальное тоже, что у тебя.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32775538
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2 NotGonnaGetUs
Дейкстру модифицировать нельзя. Алгоритм канонизирован.
А вот внести оптимизации в алгоритм формирования графа - можно.
Можно обьединить смежные непрерывные области клеток в прямоугольники (любым алгоритмом) и считать эти прямоугольники вершинами графа.
Я рассуждаю так - поиск маршрута внутри прямоугольника - тривиальная задача. Гораздо важнее упростить сам граф.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32775616
ponomarevvb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Короче, вот результаты моих усилий - класс для поиска пути. Може, кому понадобится когда-нибудь, не придётся заново реализовывать :-)
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32776450
c127
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
2 mayton

>Дейкстру модифицировать нельзя. Алгоритм канонизирован.

Это я использовал название "модифицированный алгоритм Дейктры". Воспринимайте это словосочетание как название нового алгоритма и проблемы не будет.

2 NotGonnaGetUs

c127>Его еще можно улучшить до O(n*ln(n)), точно не помню.
NotGonnaGetUs>Т.е. n^2*ln(n^2) это лучше чем n^2?
c127>Нет, это хуже. А n*ln(n) - лучше.
NotGonnaGetUs>Либо Дейкстра у нас разный, либо лыжи.


Для Дейктры оценка n^2*ln(n^2) неверна, если n-число вершин, разумеется.

Только Дейкстра тут ни при чем. Речь идет о том, что Вы откуда-то выкопали оценку n^2*ln(n^2), о которой речи не было и теперь спорите сами с собой. А речь была о n*ln(n), которая сравнивалась с n^2. И очевидно для целых положительных n верно что n*ln(n) < n^2.

>сложность задаёт число вершин. У нас их n^2.

Это у Вас их n^2, а у остального мира обычно n. Поэтому о таких нововведениях нужно предупреждать сразу. Можно, конечно, положить число вершин равным n^2, но в этом случае:

1) Вам будет сложно объяснить читателю, что для графа из 5 вершин, n нужно зачем-то принять равным 2.2360679774997896964091736687313.... Да и запомнить число 5 как-то легче.

2) по-Вашему получается что перечисленные тут алогоритмы (кроме Дейкстры) имеют линейную сложность по числу вершин N, ну конечно принимая во внимание что число вершин N=n^2. А это неверно, их сложность хуже линейной.

3) не нужно останавливаться на степенных функциях, нужно идти дальше, например к тригонометрическим функциям. Прймите число вершин графа N=tg(n), это сделает Ваши рассуждения еще более наукообразными и менее понятными.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32778497
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2 с127
Я надеюсь ты не считаешь себя создателем нового алгоритма теории графов?
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32778549
c127
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
2 mayton

>2 с127
Я надеюсь ты не считаешь себя создателем нового алгоритма теории графов?


Я считаю себя создателем нового названия алгоритма теории графов. Шутка.
...
Рейтинг: 0 / 0
Задача на матрице - алгоритм Дейкстры или что-то ещё?
    #32778560
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Шутник!
...
Рейтинг: 0 / 0
22 сообщений из 22, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на матрице - алгоритм Дейкстры или что-то ещё?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]