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

    Схематика лабиринта и возможные пути показаны на картинке, а также краткий комментарий к ним.
    Зеленая ячейка - место высадки чела в лабиринт. Может находиться в любой точке/ячейке/узле лабиринта.
    Красная ячейка - место выхода из лабиринта. Может находиться лишь в приграничной зоне, т е на границе периметра лабиринта.
    Серые ячейки - стены, через которые проход невозможен. Но их допустимо пробивать лбом с разбега!
    Координаты зеленой НЕ РАВНЫ координатам красной.

    ВАЖНО! движение по лабиринту соот-ет окрестности фон Неймана, а не Мура, т е двигаться можно строго влево, вверх, вправо или вниз.
    Прикреплённая картинка
    Прикреплённая картинка

    ====================================================================================================================
    Ну, короче, как я понял, да, это задача на классический волновой алгоритм. Структуры данных у меня - простые массивы, очереди, стеки и НИКАКИХ планарных графов. Все шикарно закодировалось с граф.интерфейсом, если нет необходимости прошибать стены, т е можно проложить ПРЯМОЙ путь от начала к выходу. Но не до конца понятно, шо делать, когда нужно прошибать стены лбом!

    Например, нет прямого пути. Я запускаю волновой алгоритм и он заканчивается тупиком, т е не достигает выхода. Получается, нужно начинать перебор ВСЕХ пронумерованных ячеек, и, если есть граничащая стенка, то пробивать ее и запускать повторно волновой алгоритм из только что выбитой стенки. Если получилось достичь выхода, то запомнить кол-во выбитых стен. Потом нужно ВОССТАНОВИЬ стенку, чтобы не образовалось необоснованного прохода для др.возможных кратчайших путей + нужно где-то запомнить сам путь. Мороки немерено! Если выхода достичь не получилось, то нужно опять перебирать все ячейки этого хвоста и искать граничащие стенки. Ппц какой-то!

    В итоге, такое чувство, что возникает NP-полная задача или почти NP-полная, т е приходится перебирать почти все возможные пути + рекурсия по любому подключается какая-нибудь.

    Как это реализуется оптимально?

    P.S. нужно считать, что координаты выходной ячейки неизвестны, но выход точно есть! Если есть алгоритм, который очень прост и понятен, но требует знания координат выходной ячейки, то тогда сниму это ограничение
      Да вроде всё намного проще! Просто обозначим цену прохода пустой ячейки за 1, К = кол-во пустых, К+1 = цена пробития одной стенки = цена сплошной стенки (это чтобы дешевле было пройти куда угодно, лишь бы не пробивать. Можно просто некое очень большое число). И теперь запускаем алгоритм нахождения пути минимальной стоимости.

      Во втором вашем случае цена будет 2005 (К=1000), т.к. 2 стены за 1000 и 5 обычных, что меньше, чем синий путь ценой за 3002.
        Цитата FasterHarder @
        + нужно где-то запомнить сам путь.

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

          На алгоритм Дейкстры только. Волновой выгодно использовать только если веса ребёр отличаются не сильно. Например, вот эта задача, в точности повторяющая твою, у меня в своё время волновым не решилась - не проходило по времени, а Дейкстра прекрасно зашёл. Да и пишется он проще, если в языке есть встроенная куча.
            Вроде понял, спс всем, особенно Славян-у! Нужно ввести веса "ребер" и все свести к алгоритму Дейкстры для планарного НЕОРИЕНТИРОВАННОГО взвешенного графа

            Цитата OpenGL @
            если веса ребёр отличаются не сильно

            а разве не должно быть СТРОГОГО равенства, ведь если "не сильно", то уже появляется разный вес...

            т е если:
            1. стенки можно пробивать, то сводим к алгоритму Дейкстры
            2. стенки НЕЛЬЗЯ прошибать, то стандартный волновой алгоритм, но в этом случае выход не всегда возможен.

            ясно, вроде...
              На самом даже запоминать пробитые стены не нужно. Мы ведь спускаемся в направлении уменьшения пометок (не обязательно на единицу), при этом построенный путь просто пройдёт сквозь стену.

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

              Аналогично можно обрабатывать участки с просто затруднённым прохождением. К примеру, клетки покрытые песком, стоимость прохождения 2, грязь - стоимость прохождения 5, деревянные стены, которые можно ломать даже при наличии пути без проломов - 25, каменные стены, которые стоит ломать только при отсутствии другого пути - 1000

              Сложность волнового алгоритма (с пробитием стен или без) O(N), где N - число клеток в лабиринте.
                Цитата amk @
                На самом даже запоминать пробитые стены не нужно.

                Это был ответ для FasterHarder, если бы он воспользовался своей первой идеей, а не тем, что предложил Славян.
                  Цитата FasterHarder @
                  а разве не должно быть СТРОГОГО равенства, ведь если "не сильно", то уже появляется разный вес...

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

                  Цитата amk @
                  Ещё, вместо обычной очереди придётся применять приоритетную очередь, так как пробиваемые стены должны обрабатываться сильно позже.

                  Это Дейкстра получится :)
                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                  0 пользователей:


                  Рейтинг@Mail.ru
                  [ Script execution time: 0,0519 ]   [ 18 queries used ]   [ Generated: 29.03.24, 09:46 GMT ]