Вопрос вытекает из условий текущего google AI Challenge Ank.

Собстно у нас имеется, большая матрица, координация осуществляет по номеру строки и колонки (далее точка пересечения, или просто точка). Не все точки доступны. Таким образом алгоритмы на плоскости не сработают (по крайней мере я не знаю те которые смогли бы построить оптимальный путь, да и вообще смогли бы путь проложить)

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

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

Теперь о проблемах. Граф у нас получается неориентированные и ...
* циклическим
* связанным (не уверен, не силен я в графах)

и с чрезвычайно большим числом вершин n*n/c (где с это число недоступных точек, которое спокойно может быть 99% всех точек)

делать полный обход графа при n=1000 думаю уже будет весьма проблемно. Возможно есть какие то алгоритмы ориентированные именно на построение пути на плоскости. Или же это не типизированная задача не имеющая оптимального решения ?

Это сообщение отредактировал(а) cupper - 31.10.2011, 18:51

Тебе нужно оптимальное или удовлетворительное решение?
Когда количество вариантов и условий велико и в оптимальном алгоритме решения задействованы все эти условия и варианты, бывает выгоднее использовать не очень точный алгоритм, не учитывающий все случаи, но дающий удовлетворительное решение.

Это сообщение отредактировал(а) tishaishii - 31.10.2011, 19:50

Я моделировал такую схему: станция тех-обслуживания и склад расположен на сети дорог, которая построена из ориентированных и неориентированных рёбер с разными весами-скоростными ограничениями. На той же сети расположены магазины, в которых происходят продажи товара с разной интенсивностью с экспоненциальным распределением вероятностной величины. Если в магазине заканчивается товар, то он закрывается. Грузовик на базе может заправиться и загрузиться товаром за такое-то время. При движении грузовика расходуется горючее, учитывая его загруженность. Грузовик движется по сети, выбирая оптимальный маршрут - такой, чтобы вывезти со склада побольше товара, побольше магазинов остались работать, и не оставить грузовик на трассе без топлива. Цель сего - для данной карты узнать максимальную зону покрытия организации, продающей товар.

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

Это сообщение отредактировал(а) tishaishii - 31.10.2011, 20:13

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

если много мест недоступно, то и волна не будет много занимать
ну и, конечно же, нужно прекращать поиск после достижения целевой вершины, что также уменьшит количество время и используемую память

Я таки не поняла в чем проблема? Как соорудить такой граф или как искать пути? Думаю, эти задачи нужно решать отдельно. Поиск оптимального пути вроде как стандартная задача (Дийкстра или просто поиск в ширину, если веса ребер одинаковые), работает оно быстро даже на больших графах. А организация самого графа - хороший вариант дает BGL (для C++), там есть разные варианты контейнеров, в том числе и разреженная матрица. Если не C++, то можно хотя бы позаимствовать концепцию в упрощенной форме (в BGL это очень хорошо проработано).

волновой алгоритм может пройти S-образный путь ? Т.е. случай когда карта выглядит не так что она вся открыта и на нем отдельные препятствия которые можно обогнуть. А когда препятствия представляю большую часть карты при это оставляя пути для прохода в виде длинных изгибистых туннелей (аля лабиринт, это конечно сильное усложнения, но вполне обычно можно встретить изгибистые пути между двумя большими доступными плоскостями. Я до конца не постиг этот алгоритм,, поэтому ну знаю ответа на свой вопрос. Но везде пишется что алгоритм нее является эффективным.

Добавлено через 1 минуту и 7 секунд

хорошее замечание, но что понимать под оптимальным решением и как его узнать ?

Добавлено через 2 минуты и 50 секунд

моя задачи сильно отличается. У тебя как раз хороший пример реальной задачи на графе.

Как искать пути. В ширину... мб и в ширину, походу надо просто реализовывать и смотреть на практике.

BGL велик, аж целая книжка. Может вы подскажите есть ли там структура которая позволяла бы получать доступ в вершине графа по координатам вершины ? Ведь изначальная задача что есть плоскость(аля матрица) которую можно интерпретировать как графф, но только для нахождения пути, при этом нужно уметь за единичное время получать вершину графа по координатам в матрице, и по вершине соответствующие координаты из матрицы. 

Это сообщение отредактировал(а) cupper - 1.11.2011, 12:38

любой, если есть связность. Собственно, поиск в ширину делает примерно то же, что и волновой алгоритм: проверяет точки, лежащие на равном "расстоянии" от центра волны (стартовой точки). Под расстоянием здесь понимается не эвклидова дистанция, а число шагов. Оптимальный путь - это всегда путь, минимизирующий некоторое значение. Что за значение - вопрос к постановщику задачи. Это может быть число шагов или сумма весов ребер, или еще что-нибудь. 

Ну, вобщем, тоже полностью поддерживаю. Интересные-такие задачки про графы и про дискретизацию.

Это сообщение отредактировал(а) tishaishii - 1.11.2011, 20:35

Книжка толщиной аж полсантиметра... И вовсе не обязательно читать все, достаточно первых концепций. Что касается адресации вершин, то они адресуются абстрактным типом vertex_descriptor, который зависит от выбора типа контейнера. И доступ константный. Чтобы адресоваться по координатам матрицы (строка-столбец) никто не мешает добавить отображение (строка-столбец)-> дескриптор. Кроме того, не обязательно использовать именно реализованные в бусте контейнеры. BGL - это прежде всего набор концепций и алгоритмов. Можно адаптировать свою собственную реализацию под BGL, и пользоваться всеми алгоритмами. Возможно, тебе подойдет контейнер - sparse_matrix, но утверждать не берусь, т.к. я использовала только adjacency_list.