21:36 

Волновой алгоритм 2

Уже писал про него, один из методов поиска, он же поиск в ширину. Неэффективную реализацию написал (на поиск каждого возможного шага прочесывает всю матрицу), но с некоторыми ошибками. Исправлять потом буду, пока времени не хватает на это. Программа выводит все кратчайшие пути. Все. Но тут сам собой вопрос напрашивается -- а все это сколько? И само собой появилось желание, чтобы программа количество кратчайших путей считала. И сколько я не пытался так ничего и не получилось. Решил пойти от простого, вывести формулу математически для какого-нибудь простого случая, а конкретно для матрицы без препятствий, начало в левом верхнем углу, конец -- в правом нижнем углу. Но и тут был нежданный провал. Вручную посчитал для 3x3 и 4x4 соответственно 5 и 20 путей. Формулу не вывел и, более того, даже не понял как подходить к ней. Кто-нибудь сталкивался с этой задачей? В интернете увы ничего найти не удалось. Любые ссылки, в том числе и на английскую литературу пойдут мне на пользу. Хотелось бы пока в оффлайне думать над решением.

@темы: Теория графов

Комментарии
2017-10-08 в 10:16 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
для 3x3 ... соответственно 5 ... путей. - вроде 6 должно быть...

Задача о числе решений из угла в угол когда-то попадалась...
если перемещение только через сторону, то в клетки пишем сумму соседних... и получаем кусок треугольника Паскаля...
думаю, что аналогичное заполнение доски возможно и при наличии препятствий...

Что касается литературы, то тут не силён... :nope:

2017-10-10 в 02:49 

All_ex, да, у меня оказывается 6 и записано на листе, забыл видать. С перемещением через сторону честно говоря не очень понял. Если Вы вспомните где видели или вспомните как это делать, то дайте знать, пожалуйста. Уж что-то очень эта штука заинтересовала) Честно говоря думал будет в интернете куча ссылок, а ничего не удалось найти. Это честно говоря странно очень. Сам вопрос-то естественен. Но с наводкой на треугольник Паскаля, не уверен, но интуитивно чувствую ответы для всех квадратных матриц.

Вот 2x2 - 2, 3x3 - 6, 4x4 - 20, 5x5 походу 70 будет и 6x6 - 252. По синим ячейкам вниз.
:duma2:

По поводу самого алгоритма, случайно попалось это видео, на мой взгляд лучшее объяснение, детальнейшее просто.

p.s. правда игра "жизнь" в разы проще реализации волнового алгоритма пишется)

2017-10-10 в 04:52 

All_ex, ну собственно я сделал походу (все-таки просто узрел его) :rotate:
Это и будет треугольник Паскаля! Сказать что удивлён, это ничего не сказать...

2017-10-10 в 06:59 

Причём по сути для заполнения достаточно только клетки, в которые один путь, занумеровать единицей, а остальной треугольник или его композиции (в случае препятствий) однозначно уже определяются просто через сумму двух соседних, если такие имеются.

Например, для случая когда a1 < b1 и a2 < b2 мы сразу видим куда курс держать влево и вверх, а потому условие только одно будет если сверху и слева рассматриваемой ячейки (например для (5, 5) на рисунке, индексация с нуля) клетки свободны (не равны препятствию), то пишем в них сумму элементов x(5-1, 5+1) + y(5, 5) и x(5, 5-1) + (5, 5) соответственно, и т.д. Осталось рассмотреть случай когда начало и финиш не в углах расположены.

p.s. а также понял, что Вы именно это и имели ввиду! :)

2017-10-10 в 14:27 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
p.s. а также понял, что Вы именно это и имели ввиду!
вот и ладненько... :red:

     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная