На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (3) [1] 2 3  все  ( Перейти к последнему сообщению )  
> Алгоритм построения графа видимости (планарный граф вроде) , Вычислительная геометрия, лабиринт, BFS, Дейкстра, волновой алгоритм, GDI+, сетка
    Всем хай! Сходу к делу!
    Постараюсь предельно лаконично описать задачу и проблемы (а их не мало тут накопилось).
    Все схемы, рисунки показаны на общем изображении.
    Дан лабиринт квадратной формы. Заданы препятствия, начальная и конечная ячейка.
    1. Найти кратчайший путь между стартом и концом (используя BFS + планарный граф). Движение робота по принципу фон Неймана (вверх, вправо, вниз, влево).
    2. Построить граф видимости :(

    =====================================================
    С 1-й подзадачей справился особенно легко. Сформировал матрицу смежности планарного графа (ведь у графа нет ни одной пары пересекающихся ребер) из сетки/лабиринта, запустил поиск в ширину из старт.вершины и в итоге получил наикратчайший путь. Здесь проблем НЕТ!
    Со 2-й подзадачей не сложилось: не сразу, ни через какое-то время...

    Поискал в сети информацию о получении графа видимости. Я бы не сказал, что описательной информации этого алгоритма предостаточно (в отличие, например, от BFS, DFS и др.классических алгоритмов) + я не смог выкупить все равно тонкости построения графа видимости.
    Как я понял, оптимальный путь будет представлять кусочно-линейная ломаная, проходящая через вершины препятствий. Но дело в том, что тут смешиваются информационные модели и геометрические. Т е оказывается важна геометрия физически исходного лабиринта. Ну, допустим! Но когда я получал планарный граф за вершину принимался ЦЕНТР ЯЧЕЙКИ, а не ее вершины, коих 4-ре штуки к слову...
    Т е придется полностью менять граф что ли для создания его видимости)? Я вот этот момент не очень выкупаю.
    Также непонятно, что брать за отправную точку движения? Центр исходной ячейки или можно сместиться в какую-то ее вершину?
    Также, как я понимаю, для построения графа видимости робот, перемещающийся по лабиринту вырождается в ТОЧКУ, т е не обладает ни шириной, ни высотой и вообще не обладает габаритами?
    Я правильно выкупаю, что нужно ввести систему координат и раздать координаты тем ячейкам сетки, которые выражают препятствия?
    Потом нужно получить новый взвешенный граф и запустить алг. Дейкстры, для нахождения кратчайшего пути? Или достаточно все делать на одном графе?
    Ну, и последнее) мне бы просто шоб работало. Мне не нужен оптимальный, высокопроизводительный алгоритм, т к он будет сложен для моего понимания. Хотелось бы топорный, максимально простой и тупой алгоритм, который пусть имеет сложность (n^5), но который бы был понятен) Главное чтоб работало да и все...
    Прикреплённая картинка
    Прикреплённая картинка
      По-моему граф видимости надо строить по тем же точками, что вы искали кратчайший путь, т.е. центр клеточки лабиринта.
      Тогда граф видимости будет такой граф, у которого две вершины будут связаны (видимы), если ребро их связывающее не пересекает препятствие.
      Соответственно нужно построить отрезки всех препятствий и для всех пар вершин исходного графа проверить видимость: пересекается или нет отрезок из двух вершин какой-то отрезок препятствий.
      Прикреплённая картинка
      Прикреплённая картинка
        Что-то я как-то не понимаю, какое движение в графе видимости? Формально граф видимости есть обычный ненаправленный граф, где ребро означает, что связанные им вершины достижимы без смены направления движения. Всего-то лишь... т.е. построение сводится к перебору вершин и для каждой - перебору находящихся в прямой видимости вершин, т.е. движение в одном из 4 возможных направлений до ближайшего препятствия (включая границы). Например, на исходном рисунке для ячейки (row-col) 12 такой перебор даст следующие рёбра графа видимости: 12-13, 12-14, 12-22, 12-32, 12-42, 12-52, причём первые 2 ребра получены движением вправо до препятствия, остальные движением вниз до границы, а движение вверх или влево невозможны, ибо граница - вот она... для ячейки 13 набор рёбер будет 13-12, 13-14. Для исключения дубликатов (граф-то ненаправленный) достаточно для каждой ячейки обрабатывать только два (перпендикулярные) из 4 направлений, т.е. после обработки ячейки 12 и получения 7 рёбер графа видимости обработка ячейки 13 добавит в граф только одно ребро 13-14. И чего тут сложного...
          Кстати, в общем случае граф видимости не планарный.
            вот с одной стороны вроде все понятно, а с другой стороны не выкупаю тонкости некоторые, которые не позволяют осознать все окончательно...
            мне ведь еще нужно показать эту видимость (ломаную линию) на самом лабиринте, используя технологию GDI+, которую я вроде норм. знаю и что-либо отрисовать нет проблем, если ПОНИМАТЬ, что и где чертить....

            я прав или нет в том, что
            : вот эта "видимость" будет пролегать через вершины/ячейки лабиринта, которые входят в состав кратчайшего пути (они желтого цвета на картинке)? Если да, то тогда ведь можно оптимизировать построение, проверяя только эти "желтые" ячейки или нет? они у меня все лежат в стеке и я всегда к ним могу получить доступ...


            Цитата grgdvo @
            По-моему граф видимости надо строить по тем же точками, что вы искали кратчайший путь, т.е. центр клеточки лабиринта.

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

            Цитата Akina @
            Например, на исходном рисунке для ячейки (row-col) 12 такой перебор даст следующие рёбра графа видимости: 12-13, 12-14, 12-22, 12-32, 12-42, 12-52, причём первые 2 ребра получены движением вправо до препятствия, остальные движением вниз до границы, а движение вверх или влево невозможны, ибо граница - вот она... для ячейки 13 набор рёбер будет 13-12, 13-14

            вроде я понимаю это, но твое движение предполагает строго по вертикали и по горизонтали, а ломаная линейная может проходить и под углом и не всегда вроде даже под 45 градусов...

            Цитата amk @
            Кстати, в общем случае граф видимости не планарный.

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

              Я был не прав (смутило определение в википедии). Граф видимости похоже действительно строится по вершинам препятствий.
              Соответственно, да, потребуется построение второго графа со своими вершинами и определением ребер видимости.
                Цитата FasterHarder @
                мне ведь еще нужно показать эту видимость (ломаную линию)

                Видимости. Ломаная. Ага... не, ну бред же, али сам не видишь? оно, конечно, пушка по параболе стреляет, и ежели её на бок положить, так можно из-за угла стрелять...

                Не смешивай граф видимости и построение пути по нему. Как строится сам граф - я выше говорил... Для построения пути из графа предварительно выбрасываются все рёбра, у которых хотя бы для одного концевого узла существует только два параллельных ребра (за исключением точек старта и финиша). И построение выполняется стандартными методами - хоть поиском в ширину, хоть ещё как...
                  Цитата Akina @
                  Формально граф видимости есть обычный ненаправленный граф, где ребро означает, что связанные им вершины достижимы без смены направления движения.

                  кажется я понял о чем речь!
                  Прикреплённая картинка
                  Прикреплённая картинка

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

                  Добавлено
                  Цитата Akina @
                  Для построения пути из графа предварительно выбрасываются все рёбра, у которых хотя бы для одного концевого узла существует только два параллельных ребра (за исключением точек старта и финиша).

                  что ты понимаешь здесь под ПАРАЛЛЕЛЬНЫМИ ребрами? я могу предположить, что || ребра - как || ходы в лабиринте, если смотреть на лабиринт, как на физ.объект, а не информационный. Возможно, я не прав, разумеется)

                  Добавлено
                  Цитата Akina @
                  параллельных ребра

                  как я понял, в т.графов, под параллельными ребрами понимают ребра, имеющие одинаковые концевые вершины.

                  хотелось бы глубоко понять смысл этой фразы:
                  Цитата Akina @
                  Для построения пути из графа предварительно выбрасываются все рёбра, у которых хотя бы для одного концевого узла существует только два параллельных ребра (за исключением точек старта и финиша).

                  вот тут ты говоришь про ДВА || ребра, но, если я правильно построил граф видимости, то у него вообще нет ни одной пары || ребер или я чего-то не выкупаю конкретно...?...
                    Цитата FasterHarder @
                    получив такой граф можно говорить, что сформирована структура графа видимости, да?

                    Угу.
                    Цитата FasterHarder @
                    что ты понимаешь здесь под ПАРАЛЛЕЛЬНЫМИ ребрами?

                    Параллельны рёбра, если у них при переходе меняется одна и та же координата. Ну или если они лежат на параллельных прямых (с учётом общей вершины-клетки - на одной прямой). Школьная геометрия, не надо искать какого-то особенного смысла.
                    Скажем, ребру (в нотации row,col) 2,3-2,4 параллельны рёбра 2,3-2,5 и 2,3-2,1, ибо у них всех изменяется только координата col.
                    Цитата FasterHarder @
                    как я понял, в т.графов

                    Я использовал этот термин чисто в геометрическом смысле, рассматривая ребро как отрезок, соединяющей точки центров клеток.
                    Цитата FasterHarder @
                    если я правильно построил граф видимости, то у него вообще нет ни одной пары || ребер

                    С учётом вышенаписанного - нет. Скажем, параллельны рёбра 2-3 и 3-4, они же в нотации (row,col) рёбра 1,2-1,3 и 1,3-1,4.

                    PS. Конечно, рёбра 2-3 и 18-20 (они же 1,2-1,3 и 4,3-4,5) тоже параллельны - но они лежат на разных прямых, не имеют общей вершины, а потому в свете вышеописанного выбрасывания нам неинтересны.
                    Сообщение отредактировано: Akina -
                      Akina, ох, сколько тут тонкостей, хм...
                      отбрасывать нужно, когда именно РОВНО ДВА || ребра, а, допустим, не 3 или 17, ну ладно...
                      Посмотри, плиз картинку, я правильно понЯл твою идею или совсем не то
                      Прикреплённая картинка
                      Прикреплённая картинка


                      Добавлено
                      и давай еще закрепим понятие параллельных ребер, а то у меня есть сомнения. что не на 100% я правильно понял!
                      Ребра считаем параллельными, если они лежат на одной прямой в геом.смысле конфигурации лабиринта (горизонтальной или вертикальной) и имеют строго одну общую вершину
                      Исключения для ребер, исходящих/входящих в старт. и конеч. вершины.
                        Цитата FasterHarder @
                        Посмотри, плиз картинку, я правильно понЯл твою идею или совсем не то

                        Неправильно. Впрочем, я неаккуратно сформулировал условие.
                        Цитата Akina @
                        Для построения пути из графа предварительно выбрасываются все рёбра, у которых хотя бы для одного концевого узла существует только два параллельных ребра (за исключением точек старта и финиша).

                        Должно быть:

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

                        На картинке ты нарисовал два ребра 2-3 и 2-4. И забыл нарисовать третье ребро 3-4. А также пометить, что у узлов 2 и 4 есть ещё рёбра. В соответствии с тем, что я сказал, ни узел 2, ни узел 4 не подходят под описание, ибо у них более чем 2 ребра к соседям. А вот узел 3 подходит, из него выходят 2 ребра 2-3 и 3-4, и они параллельны. Поэтому мы выбрасываем узел 3 и оба выходящих из него ребра, и оставляем только ребро 2-4.

                        Аналогично на второй картинке. Узел 16 не является кандидатом на выбрасывание, это начало. Узел 17 тоже не является кандидатом, потому что у него есть как рёбра горизонтальные (17-16 и 17-18), так и вертикальные (17-12 и 17-22). Узел 18 - кандидат, у него 2 ребра к соседним вершинам (18-17 и 18-19) и они параллельны, т.е. выбрасывается вершина 18 и оба ребра этой вершины. Узел 19 тоже не является кандидатом, потому что у него есть как рёбра горизонтальные (19-18 и 19-20), так и вертикальные (19-14 и 19-24). Узел 20 - не кандидат, хотя у него всего 2 ребра (20-19 и 20-15), но они непараллельны.

                        Суммарно при построении пути по матрице видимости в ходе предобработки из матрицы будут выброшены узлы 3, 18 (оба - проходные), 6 и 24 (тупиковые), а также все исходящие из них рёбра (6 штук).

                        PS. При выбрасывании одного узла количество выбрасываемых рёбер может быть и более 2, потому что рассматриваем мы только рёбра к "соседям", а выбрасываем вообще все.

                        Добавлено
                        Цитата FasterHarder @
                        давай еще закрепим понятие параллельных ребер

                        Давай будем проще. Рёбра видимости А-Б и Б-В считаются параллельными, если существует ребро видимости А-В.
                        Сообщение отредактировано: Akina -
                          Akina, во, теперь стало гораздо понятнее)
                          вот более "сложный" случай, посмотри, плиз
                          Прикреплённая картинка
                          Прикреплённая картинка

                          И очень важные уточняющие вопросы:
                          1. начальная и конечная ячейка/вершина НЕ учитываются в принципе в анализе, как будто их нет, а также не учитываются все ребра им инцидентные?
                          2. насколько важен порядок нахождения проходных и тупиковых вершин? или без разницы? такое чувство, что если сначала удалить тупиковые, то тогда некоторые "тройки" с проходной вершиной уже не будут найдены...
                          3. вот этот коэффициент равный 2 продиктован ТОЛЩИНОЙ препятствий. Если бы стенки были двойной толщины, тогда коэффициент бы стал равен 3 или там бы этот учет усложнился..?

                          Добавлено
                          4. все эти поиски и удаления узлов и ребер производится на построенном на 1-й стадии графом видимости?
                          5. что делать дальше?)
                            Цитата FasterHarder @
                            вот более "сложный" случай, посмотри, плиз

                            Тупиковые определены верно. Проходные - пропущены 8, 14, 15, 22, 30, 32, 36, 43, 47. Например, у 8-й есть только два соседа 1 и 15, и существует ребро 1-15.
                            Цитата FasterHarder @
                            1. начальная и конечная ячейка/вершина НЕ учитываются в принципе в анализе, как будто их нет, а также не учитываются все ребра им инцидентные?

                            На стадии "избавления" от лишних рёбер графа достижимости - да.
                            Цитата FasterHarder @
                            2. насколько важен порядок нахождения проходных и тупиковых вершин?

                            Абсолютно неважен.
                            Цитата FasterHarder @
                            3. вот этот коэффициент равный 2 продиктован ТОЛЩИНОЙ препятствий.

                            Какой коэффициент???

                            Добавлено
                            Цитата FasterHarder @
                            4. все эти поиски и удаления узлов и ребер производится на построенном на 1-й стадии графом видимости?

                            Угу.
                            Цитата FasterHarder @
                            5. что делать дальше?)

                            А всё, потом поиск (в ширину, в глубину, в длину или куда там надо).
                              Цитата Akina @
                              Абсолютно неважен.

                              а как насчет этого случая
                              Прикреплённая картинка
                              Прикреплённая картинка

                              способ №1: если сначала обработать №1 - тупиковая - удаляем. потом №8 - тупиковая - удаляем. потом №15 - аналогично и потом №22 - она по твоей классификации не является ни тупиковой ни проходной, а по сути - изолированная.
                              способ №2: если встать на №8 - проходная - удаляем. потом №15 - проходная - удаляем. №22 - тупиковая - удаляем. №1 - изолированная.

                              хотя вроде, да, неважно какой способ, остается по 1 изолированной вершине. ну и как бы плевать на нее) наверное...

                              Вот мы еще не обговорили кол-во компонент связности графа видимости. Их ведь очевидно, что может быть больше 1! Наверное, нужно взять только ту КС, в состав которой входят начальная и конечная вершины, а остальные вообще не учитывать при анализе?, т к через те вершины путь теоретически даже не может проходить...

                              Добавлено
                              Цитата Akina @
                              Какой коэффициент???

                              Цитата Akina @
                              существует только два параллельных ребра


                              Добавлено
                              Цитата Akina @
                              Проходные - пропущены 8, 14, 15, 22, 30, 32, 36, 43, 47.

                              важнейшее для меня уточнение!
                              говоришь, что №14 - проходная, но ведь мы обсудили, что:
                              Цитата FasterHarder @
                              начальная и конечная ячейка/вершина НЕ учитываются в принципе в анализе

                              поэтому она вроде должна быть ТУПИКОВОЙ, т к у нее нет верхнего соседа, точнее он есть - конечная вершина, но мы же ее НЕ учитываем! или как?
                                Цитата Akina @
                                А всё, потом поиск (в ширину, в глубину, в длину или куда там надо).

                                а дальше самое страшное для меня... :) :(
                                нужно ГРАФИЧЕСКИ, средствами GDI+ (ну я типа на C# делаю) НА ПОВЕРХНОСТИ ЛАБИРИНТА (который представлен элементом управления "сетка") показать кратчайшую траекторию.
                                т е граф видимости построен - 1 стадия
                                отсекли лишние вершины+ребра - 2 стадия

                                как я понимаю, вершина соот-ет как бы ЦЕНТРУ ячейки грида, но я вот в упор не понимаю, как наклонять линию при рисовании ломаной. еще описывал в 1-ом сообщении, что нужно вводить систему координат, раздавать координаты. Но теперь мне непонятно, стенка характеризуется только своим центром или нужно задавать координаты ее 4-рех вершин...

                                тут ведь такой нюанс есть, что это ломаная может проходить не только по горизонтальным/вертикальным осям симметрии ячейки, но и касаться вершин препятствий, а там вроде не только угол в 45 градусов может быть и пр... :(

                                +нужно еще рассчитать длину этой траектории, а это приводит к Дейкстра какому-нибудь. По умолчанию можно взять габариты ячейки 1 на 1 уе.

                                вот на этой стадии совсем не выкупаю к чему стремиться, хотя поверхностно понятно...
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (3) [1] 2 3  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0957 ]   [ 28 queries used ]   [ Generated: 29.03.24, 00:08 GMT ]