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

                                вот на этой стадии совсем не выкупаю к чему стремиться, хотя поверхностно понятно...
                                  Цитата 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 -
                                                                Akina, большое спс за помощь и разъяснение!
                                                                я тут на неделе) почитал еще про детали этого алгоритма и там такой "мертвый лес", что пока того, что я понял мне достаточно!
                                                                еще раз спс ;)
                                                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                                                0 пользователей:


                                                                Рейтинг@Mail.ru
                                                                [ Script execution time: 0,2262 ]   [ 34 queries used ]   [ Generated: 28.03.24, 09:13 GMT ]