Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Доброго всем времени суток. Есть такая задача. Дана матрица из 0 и 1. Из данной клетки с нулём нужно найти путь (если таковой есть) по нулевым клеткам до другой нулевой клетки. Перемещение по клеткам - верх-низ, право-лево. Как решить такую задачу (как она хотя бы называется, чтобы в Инете посмотреть)? Единственное, что кроме перебора пришло на ум - составить соответствующий граф (клетка - вершина) и использовать алгоритм Дейкстры, но это, наверное, будет небыстро - при матрице, например, 20х20 (примерно такие будут в реальных условиях) получится граф из 400 вершин, да ещё и сложность алгоритма o(n^2)! Заранее спасибо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2004, 14:33 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
подойдёт вариация на тему "поиск в ширину" в неориентированных графах, если нужно найти минимальный путь. Суть подхода в том, что бы на каждом шаге итерации определять набор клеток достижимых из стартовой за k-шагов(k-номер шага). Следующий шаг использует реультаты предыдущего. Cложность алгоритма порядка n^2 (матрица nXn); ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2004, 14:48 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
NotGonnaGetUsподойдёт вариация на тему "поиск в ширину" в неориентированных графах, если нужно найти минимальный путь. Мне необязательно нужен минимальный. Моя задача - найти любой путь с обходом препятствий. Наверное, мне больше подойдёт поиск в глубину, а не в ширину. Но пока что-то не нашёл его толковых описаний - всё больше листинги, а хочется вникнуть в суть :-) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2004, 15:25 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Можно и поиск в глубину. Он существует в двух варинтах, поиск по всем путям в графе и поиск по всем вершинам в графе. В обоих случаях при поиске в глубину скачут от узла к узлу в определённом порядке, как только двигаться становится не возможно (некуда или упёрлись в уже пройденный узел) возращаются назад и согласно порядка пробуют выбрать другой узел и т.д. Уже пройденный узел это либо узел на текущем пути(1ый вариант), либо когда-то уже посещённый узел(2ой вариант). Во втором варианте сложность порядка n^2, в первом много больше. В среднем теже самые n2 с точностью до константы. Можно сделать оба и протестировать :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2004, 18:12 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Если в матрице достаточно много препятствий то подойдет алгоритм, предложеный NotGonnaGetUs. Я бы еще добавил "волновой алгоритм" описаный на www.codenet.ru. как вариации на тему. Лично для меня больший интерес представляет случай, когда препятствий мало и они сгруппированы в области (наподобие непроходимых гор или болот). В этом случае я бы предложил ввести функцию "опасности" или "близости препятсвия" выразив ее аналитически. А дальше - вспоминать алгоритмы поиска локальных экстремумов в условиях двух переменных. Может она и не всегда даст результат. Зато появится выбор. 1) Использовать в игре рекурсивный алгоритм который всегда даст результат но может скушать процессорное время. 2) Попробовать нацелить на лабиринт алгоритмы нечеткой логики, нейроные сети и т.п. А если распараллелить два алгоритма и ожидать первого результата то вообще здорово! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.11.2004, 22:07 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Всем большое спасибо. 2 mayton: codenet - рулит! Жаль, раньше про него не знал. 2 NotGonnaGetUs: заставили покопаться в конспектах. Вспомнил много инетерсного :-) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.11.2004, 23:15 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
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. Посмотри в кингах по компьютерной графике. Этот алгоритм вроде бы самый быстрый. Он быстрее Дейкстры, но Дейсктра универсальнее, например работает для всех графов, я использую его. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2004, 00:20 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Т.е. n^2*ln(n^2) это лучше чем n^2? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2004, 09:31 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
2 mayton: Волновой алгоритм и поиск в ширину - это одно и то же. Его использование, на мой взгляд, наиболее логичное решение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2004, 09:48 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Для этой задачи пожалуй лучше алгоритм кратчайшего пути Дейкстры. Есть опыт его использования на сильно разряженных матрицах примерно 900х900. Дает приемлимое быстродействие даже на медленных компьютерах, если не хранить нулевые элементы матрицы смежности. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2004, 10:02 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
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. Или, может, я выбрал порочный путь? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2004, 12:41 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Твой алгоритм: матрица 3000x3000, заполнение единичками 30%, поиск от одного угла, до противоложного занимает ~3.6сек. матрица 4000x4000, заполнение единичками 30%, поиск от одного угла, до противоложного занимает ~7сек. n^2 на лицо, а чего ещё ожидать от простого решения? Правда тупые эвристики будут на порядки быстрее, если процент невелик... (тот же поиск в глубину с выбором следующей клетки в направлении ближайшем к финишной точке) , а в худшем случае теже самые n^2 :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2004, 15:06 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2004, 22:44 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
2 NotGonnaGetUs >Т.е. n^2*ln(n^2) это лучше чем n^2? Нет, это хуже. А n*ln(n) - лучше. 2 ponomarevvb >А насколько заливка будет быстрее волнового алгоритма? Не знаю. Заливку использовал лет 15 назад, тогда же читал о ней. Вроде он самый быстрый для этой задачи. С тех пор не интересовался, дейкстра устраивает. Основной недостаток - заливка чувствительна к структуре графа, у нас структура бывает меняется. Дейкстра универсальный. >И почему Дейкстра будет быстрее их обоих? Ведь волновой алгоритм есть в оптимизированном варианте, когда идёт при распространении волны не просматривается не вся матрица, а только волновой фронт. Дейкстра не будет быстрее, будет медленнее, по крайней мере чем заливка. Насколько я понял волновой алгоритм и есть модифицированный дейкстра для случая ребер одинаковой длины (веса). По-моему заливка сложнее в реализации чем дейкстра, поэтому на малых матрицах заливка может оказаться медленнее за счет инациализации и пр. На больших наверное будет быстрее. >Но есть подозрения, что на матрицах порядка 50x50 и меньше это работает дольше, чем если бы проход шёл по всей матрице в поисках фронта. Может быть. Но в таких случаях ИМХО не нужно заниматься вылавливанием блох. Тогда не нужно будет переписывать когда размеры увеличатся. Суммарный выигрыш времени работы для всех экземпляров программы врядли превзойдет твое время, потраченное на переписывание алогоритма. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2004, 00:20 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Спасибо всем, господа! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2004, 12:11 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
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мб остальное тоже, что у тебя. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2004, 13:21 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
2 NotGonnaGetUs Дейкстру модифицировать нельзя. Алгоритм канонизирован. А вот внести оптимизации в алгоритм формирования графа - можно. Можно обьединить смежные непрерывные области клеток в прямоугольники (любым алгоритмом) и считать эти прямоугольники вершинами графа. Я рассуждаю так - поиск маршрута внутри прямоугольника - тривиальная задача. Гораздо важнее упростить сам граф. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2004, 14:27 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
Короче, вот результаты моих усилий - класс для поиска пути. Може, кому понадобится когда-нибудь, не придётся заново реализовывать :-) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2004, 14:58 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
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), это сделает Ваши рассуждения еще более наукообразными и менее понятными. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2004, 00:50 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
2 с127 Я надеюсь ты не считаешь себя создателем нового алгоритма теории графов? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2004, 21:15 |
|
||
|
Задача на матрице - алгоритм Дейкстры или что-то ещё?
|
|||
|---|---|---|---|
|
#18+
2 mayton >2 с127 Я надеюсь ты не считаешь себя создателем нового алгоритма теории графов? Я считаю себя создателем нового названия алгоритма теории графов. Шутка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2004, 22:58 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=32775378&tid=1348093]: |
0ms |
get settings: |
9ms |
get forum list: |
11ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
40ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
61ms |
get tp. blocked users: |
2ms |
| others: | 256ms |
| total: | 397ms |

| 0 / 0 |
