На главную Наши проекты:
Журнал   ·   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+, сетка
    Цитата FasterHarder @
    способ №1: если сначала обработать №1 - тупиковая - удаляем. потом №8 - тупиковая - удаляем. потом №15 - аналогично и потом №22 - она по твоей классификации не является ни тупиковой ни проходной, а по сути - изолированная.

    Ты невнимателен. Мы удаляем узел (виртуально), и все связанные с ним рёбра (из списка рёбер графа видимости). Вот мы удалили последовательно узлы 1, 8, 15... ну и скажи мне, какие у тебя остались рёбра, где одна з вершин - 22-я? Напоминаю, у нас граф видимости, в котором есть только рёбра, и нет никаких вершин.
    Цитата FasterHarder @
    оворишь, что №14 - проходная, но ведь мы обсудили, что:
    Цитата FasterHarder @
    начальная и конечная ячейка/вершина НЕ учитываются в принципе в анализе

    И? мы не рассматривали СТАТУС ячейки 7, как и то, подлежит ли она удалению. И только... а соседом она как была,так и осталась.
    Сообщение отредактировано: Akina -
      Цитата Akina @
      Мы удаляем узел (виртуально)

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

      я считал, что граф видимости описан матрицей смежности :( неужели это не так...
      Цитата Akina @
      Вот мы удалили последовательно узлы 1, 8, 15... ну и скажи мне, какие у тебя остались рёбра, где одна з вершин - 22-я?

      ну, только со стенками, но мы их не учитываем, поэтому никто не ссылается на №22 и она ни на кого...последняя из вершин, которая на нее ссылалсь была №15, но ее уже грохнули
      Цитата Akina @
      И? мы не рассматривали СТАТУС ячейки 7, как и то, подлежит ли она удалению. И только... а соседом она как была,так и осталась.

      значит я не так понял, что значит не учитывать начальную и конечную ячейки :( ...

      еще этот чертов путь строить надо, там вообще непонятка лютая.
        Цитата FasterHarder @
        Цитата Akina @
        Мы удаляем узел (виртуально)
        как понять...

        Очень просто. В таблице видимости НЕТ узлов. Таблица видимости - это коллекция рёбер.

        Цитата FasterHarder @
        я считал, что граф видимости описан матрицей смежности

        Ну если так - то узел удаляется не виртуально, а вполне реально - т.е. удаляется и строка, и столбец этого узла. Вот только на суть происходящего это никак не влияет.

        Цитата FasterHarder @
        ну, только со стенками

        Даже в матрице смежности нет никаких "стенок", не говоря уж о коллекции рёбер графа видимости.

        Цитата FasterHarder @
        никто не ссылается на №22 и она ни на кого...последняя из вершин, которая на нее ссылалсь была №15, но ее уже грохнули

        Т.е. если работать с матрицей, то ВСЕ ячейки столбца и строки этого узла - нулевые. А если работать с коллекцией рёбер - то в ней не осталось ни одного ребра, в котором этот узел является одним из концевых, иными словами, его как бы вообще не существует.
          Еще раз хочется пройтись по очистке графа видимости, т е удалению лишних вершин и ребер
          Прикреплённая картинка
          Прикреплённая картинка

          Сначала удалим все тупиковые вершины, потом проходные. Вроде как, удаление тупиковой вершины НЕ приводит к образованию проходной, а вот удаление проходной может приводить к образованию тупиковых...
          №32 - идеальная тупиковая вершина, т к имеет только 1 ребро видимости к ближайшему соседу под №31. Удаляем ее и связь между 31 и 32.
          №31 имеет ЧЕТЫРЕ ребра видимости: 31-25, 31-19, 31-13 и 31-7. Было еще ребро 31-32, но оно удалено было ранее! Несмотря на то, что у №31 ЧЕТЫРЕ связи она является тупиковой, т к существует лишь 1 связь до ближайшего соседа под №25. Удаляем №31 и все четыре ребра инцидентные ей.
          №25 имеет ТРИ ребра видимости: 25-19, 25-13, 25-7. Ребро 25-31 было удалено ранее. Несмотря на то, что №25 ТРИ связи она является тупиковой, т к существует лишь 1 связь до ближайшего соседа под №19. Удаляем №19 и все четрые ребра инцидентные ей.
          Пока тупиковые вершины закончились! Но это лишь пока!

          Начинаем удалять проходные вершины. Такие вершины характ-ся тем, что они имеют лишь два ребра до БЛИЖАЙШИХ СОСЕДЕЙ, стоящих на одной линии (гор. или верт.) по разные стороны от проходной. ПРи этом такие проходные вершины могут иметь множество ребер видимости. Для нахождения проходных вершин придется рассматривать "тройки": A-B, B-C ---> A-C
          №13 - идеальная проходная вершина. удаляем ее и ребра.
          №8 по аналогию с номером 13.
          №4 - проходная, которая имеет ТРИ ребра видимости: 4-3, 4-5, 4-6, но несмотря на это ее нужно удалять, т к она имеет РОВНО 2 ребра до БЛИЖАЙШИХ соседей, лежаших по разные стороны от нее. Удаляем ее и инцидентные ей ребра в кол-ве ТРЕХ штук.

          И отдельно хотелось бы посмотреть на удаление №30 и 24. №30 - удаляется как обычно.
          Для вершины №24 при этом происходит ЗАМЕЩЕНИЕ БЛИЖАЙШЕГО нижнего соседа. Вместо №30, встает №36. Т е раньше №36 не был ближайшим соседом для №24, а после удаления вершины №30 №36 стал ближайшим соседом - единственный момент, который может вызвать сложности при кодинге...

          вот все правильно в этих рассуждениях или есть глубочайшие ошибки и полное непонимание происходящего?
            Цитата FasterHarder @
            И отдельно хотелось бы посмотреть на удаление №30 и 24. №30 - удаляется как обычно.
            Для вершины №24 при этом происходит ЗАМЕЩЕНИЕ БЛИЖАЙШЕГО нижнего соседа. Вместо №30, встает №36. Т е раньше №36 не был ближайшим соседом для №24, а после удаления вершины №30 №36 стал ближайшим соседом - единственный момент, который может вызвать сложности при кодинге...

            Не поверишь - можно делать, как ты описываешь, замещать соседа, а можно этого и не делать, и опознавать №30 как проходную, ориентируясь на старого соседа. Результат от этого ну никак не меняется. Всё зависит от того, как ты будешь реализовывать чистку. Если сразу удалять - да, сосед поменяется сам собой, куда деваться, а если будешь только накапливать список проходных узлов, а потом одним движением почистишься от их всех - то работай с исходными соседями.
            В отличие от поиска и удаления тупиков - их можно удалять только первым способом... то есть теоретически возможно модифицировать и до второго способа, если сформулировать тупик как узел, имеющий только одного соседа без учёта уже помеченных как тупиковые, но при этом может потребоваться обрабатывать один и тот же узел несколько раз, что не есть хорошо.

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

              А вот операция чистки графа видимости, который задан МС может быть и не такой простой как кажется. Нужно определять "параллельность", то, что вершины лежат по разные стороны от текущей, вот эти замещения соседей и пр. Но тут сделаю хитро, а может так и нужно: запомню координаты центров ячеек в исходном лабиринте. Значит, если у проверяемых вершин равны или Х или Y, то они лежат на верт. или гор. прямой. А иначе придется по номеру вершины определять возможных соседей и их номера и пр. пр. Вроде это не сложно и на комиксах все легко показать, но внутренние сложности при кодинге легко могут появиться...

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

                посмотри, плиз и скажи, какой вариант правильный и главное ПОЧЕМУ так нужно делать.
                если правильного нет <_< , то как его нужно прокладывать и почему

                ЗЫ: я не могу понять на 100% в чем тут соль/квинтэссенция, т к говорят, что нужно чтобы ломаная проходила через вершины препятствий, а мы используем центры ячеек и в голове мешанина какая-то сейчас по этой отрисовке...
                  Цитата FasterHarder @
                  Ты говорил что-то про коллекцию ребер. По факту, ребро - типа линия) и в любом случае нужно знать концевые ей вершины

                  Да, ребро задаётся двумя вершинами. То есть это структура. А граф - это массив или коллекция таких структур.
                  Цитата FasterHarder @
                  операция чистки графа видимости, который задан МС может быть и не такой простой как кажется. Нужно определять "параллельность", то, что вершины лежат по разные стороны от текущей, вот эти замещения соседей и пр.

                  Да как раз она элементарна... для теста узлов используются их координаты в прямоугольной матрице. Тест на "горизонтальных соседей" есть сравнение МС(i,i-1) и МС(i,i+1), а на вертикальных соответственно сравнение МС(i,i-N) и МС(i,i+N), где N - количество узлов на строку. Ну и тест на "проходность" - это проверка, что, скажем МС(i,i-1)+МС(i,i-N)=1.

                  Цитата FasterHarder @
                  на картинке привожу 6 различных вариантов прокладки кратчайшего расстояния

                  Некорректно. Если мы говорим о том, что узлы не имеют размеров (точечные), то единственный допустимый вариант - это вариант 1. Если мы рассматриваем их как имеющие размеры, то в случае, когда ищется путь от центра и к центру, верным является вариант 5, а если от любой точки узла - вариант 6.
                    Цитата Akina @
                    Некорректно. Если мы говорим о том, что узлы не имеют размеров (точечные), то единственный допустимый вариант - это вариант 1. Если мы рассматриваем их как имеющие размеры, то в случае, когда ищется путь от центра и к центру, верным является вариант 5, а если от любой точки узла - вариант 6.

                    вот сколько я пытался искать статей по описанию этого алгоритма, так и не понял, что нужно
                    предлагаю ввести такие упрощения/ограничения:

                    1) вроде как по этой траектории двигается ТОЧКА (в геом.смысле - не имеет размеров, то есть может пролезть куда угодно и двигаться ПО ЛЮБЫМ наклонам)
                    2) траектория должна проходить через вершины препятствий, но при этом не должна идти по общей касательной с препятствиями...а может и может - тут я не выкупил
                    3) площадь препятствия сохраняется по всем габаритам с заданными
                    4) начало и конец движения из ЦЕНТРОВ заданных ячеек, а не из любой точки ячейки
                    5) однонаправленное движение должно начинаться из центра ячейки и заканчиваться в центре др.ячейки (вроде выполнение этого условия гарантирует выполнение условия №2, что очень замечательно :yes: )
                    6) углы поворота могут быть не только под 90 или 45 градусов

                    т е в этом случае работает вариант под №5, да? (1 ряд снизу по центру)

                    дальше...

                    Поскольку нужно узнать ДЛИНУ этой траектории, то нужно подключать Дейкстру, а для этого потребуется построить взвешенный граф.
                    Как я понял из отрывочных описаний этого алгоритма, нужно построить всевозможные расстояние/соединительные отрезки, а затем запустить Дейкстру?
                    Akina, я правильно понимаю, что для этого нужно раздать координат ячейкам таким образом:
                    1) если это стена, то задаются 4-ре ее вершины
                    2) если это вершина очищенного графа видимости - ТОЛЬКО центр
                    после этого необходимо провести всевозможные отрезки и посчитать их длину (по формуле расстояний между 2-мя точками на плоскости), но при этом НЕ НУЖНО БРАТЬ в обработку отрезки, которые проходят через препятствия.
                    вот как отбросить эти неподходящие отрезки??
                    Сообщение отредактировано: FasterHarder -
                      Если движется точка, а путь имеет линейные размеры - то всё вышенаписанное в части понимания, что есть узел графа, херится. Меняется понятие узла графа - узлами становятся как раз точки поворота границ клеток пути плюс начальная-конечная точки. В таком графе отсутствует понятие проходного узла (да и сами проходные узлы - тоже отсутствуют). Впрочем, детект тупиков остаётся, причём именно в обсуждённом выше варианте.
                        Цитата Akina @
                        Если движется точка, а путь имеет линейные размеры - то всё вышенаписанное в части понимания, что есть узел графа, херится.

                        ничего себе...т е придется переделывать все структуры данных?

                        Цитата Akina @
                        Меняется понятие узла графа - узлами становятся как раз точки поворота границ клеток пути плюс начальная-конечная точки.

                        в одном из описаний алгоритма была такая фраза:
                        "Для построения кратчайшего пути используется граф видимости. Вершинами графа являются вершины препятствий-многоугольников. Рёбрами соединены только взаимновидимые вершины графа."
                        ты предлагаешь сделать также получается, да?

                        какой вариант прокладки пути нужно оставить, чтобы не менять обсуждаемый выше алгоритм? ТОЛЬКО под №1?
                          Цитата FasterHarder @
                          ты предлагаешь сделать также получается, да?

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

                            Вариант № 7.
                            Прикреплённая картинка
                            Прикреплённая картинка
                              Цитата Akina @
                              Вариант № 7.

                              нет-нет, этот вариант является оптимальным, но он требует ПЕРЕДЕЛКИ всех структур данных
                              я имел в виду, что если оставить все то, что было описано в первых постах, то подходящим будет 1-й вариант траектории?
                                Цитата FasterHarder @
                                он требует ПЕРЕДЕЛКИ всех структур данных

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


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0848 ]   [ 22 queries used ]   [ Generated: 29.03.24, 02:11 GMT ]