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

    Условие задачи.
    Есть шахматная доска (не классическая) размером N x N, где N = [2 ... 1000], то есть максимальный размер доски может быть 1 000 на 1 000 итого 1 000 000 (миллион) клеток. N задается в процессе работы программы. В ячейки шахматного поля раскладывают мины (на одну ячейку можно положить не больше 1ой мины). Гарантируется, что M = [0 ... (N - 2)]. Клетки, содержащие мину, будем называть запрещенными. В любую свободную клетку поля ставится КОНЬ(К). Также задается клетка, докуда ему нужно допрыгать.
    Гарантируется, что:
    • Координаты исходной (где стоит КОНЬ) и конечной клеток НЕ совпадают
    • Исходная (где стоит КОНЬ) и конечная клетки свободны, то есть на них нет мин

    Цель КОНЯ добраться от стартовой клетки до конечной, прыгая ТОЛЬКО на свободные клетки (без мин). То есть в ответе достаточно написать слово "Да" (если это возможно) или "Нет". Если КОНЬ после хода/прыжка окажется в клетке с миной, то ему каюк, разумеется)
    ===================================================================
    Для наглядности приведу пример стартового поля (это лишь условный пример):
    Прикреплённая картинка
    Прикреплённая картинка

    Зеленая клетка - клетка, куда стремится конь! К - стартовое положение коня. Клетки с минами (запрещенные клетки) закрашены черным фоном.
    И вот эта задача на графы + BFS/DFS.

    А что такое граф, в самом грубом смысле?? Граф - совокупность вершин и ребер/дуг.
    Но еще есть способы задания/представления графа с точки зрения программирования/хранения в памяти! Например: матрица смежности, списки смежности, матрица инцидентности и т.д.
    Шахматная доска с минами и конем НЕ является способом задания графа, как я понимаю)) Поэтому, самый важный момент на этом этапе - увязать доску с конем и графом... Именно поэтому я спрашиваю, т к, если здесь ошибиться, то все остальное будет насмарку

    Кстати, напомню возможные ходы шахматного коня:
    Прикреплённая картинка
    Прикреплённая картинка


    Как хочется соорудить граф.
    1. Каждая клетка без мины (свободная клетка) шахматного поля (хотя по факту, это просто сетка на самом деле) будет выражать ВЕРШИНУ графа.
    2. Кол-во вершин будущего графа считаем по формуле: N - M (кол-во всех клеток поля - кол-во запрещенных клеток). Также учитывать надо стартовую и конечную клетку.
    3. Граф неориентированный, то есть конь может прыгнуть с клетки "А" в "Б" и наоборот.
    4. Предельная степень любой вершины графа НЕ превосходит 8! Рисунок выше это доказывает...По факту будет гораздо меньше, ну, в среднем 2-3, наверное...
    5. Нумеруем вершины графа, проходя построчно (сверху вниз) заданное шахматное поле
    6. Строим списки смежности (!) - то есть формируем способ задания графа.
    7. Запускаем DFS от стартовой вершины до конечной. Можно еще до запуска проверить конечную вершину по спискам смежности: если нет ни одной вершины смежной с конечной - конь стопудова не доберется до нее)

    Вот пример построения списков смежности для условного примера:
    Прикреплённая картинка
    Прикреплённая картинка


    Всего в графе 28 вершин. Если получать матрицу смежности, то будет нерациональное использование дин.памяти. Т к всего ячеек в такой матрице 28 * 28, а задействовано будет НЕ больше, чем 28 * 8 (в реальности в 2 раза меньше). Поэтому здесь лучше взять списки смежности. На мое ИМХО матрица смежности гораздо удобнее при кодировании, чем списки смежности, но в данном случае эта матрица смежности будет слишком разряженной...
    =============================================================

    Вопрос
    Я правильно выбрал модель формирования графа по отношению к этой задаче? Если нет, то просьба пояснить, как можно правильнее или вообще по-другому.
    Просто все дальнейшие алгоритмы завязаны именно на этой модели. Ошибка на этом этапе - ставит крест на эффективном решении данной задачи)

    спс. за внимание

    Добавлено
    Скрытый текст
    Еще вопрос вдогонку: а разве форум не поддерживает оформления в стиле LATEX, ну типа там $x^2$ или $\frac{3}{\sin(y) - 4}$, хм... думал, что какой-нибудь модуль mathjax подключен...
      Цитата FasterHarder @
      матрица смежности гораздо удобнее при кодировании

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

      Или, если в языке имеется - то ассоциативный массив (коллекция), где ключ - номер вершины, а значение - вектор достижимых вершин.

      Вот если они лежат в БД - то да.
      Сообщение отредактировано: Akina -
        Имхо, в озвученной задаче вообще нафиг не надо хранить граф. Храни матрицу состояния ячеек, а смежные вершины вычисляй каждый раз.
          Можно скрестить матрицу и вектор. У каждой вершины может быть не более 8 смежных, координаты потенциальных смежных клеток легко вычисляются. Для клетки с координатами (x, y) возможные кандидаты - это (x+-2, y+-1) и (x+-1, y+-2). Либо использовать сплошную нумерацию, тогда у клетки [i] потенциальными смежниками будут [i +- 2*N +- 1] и [i +- N +- 2]. Для каждой клетки заводим битовый массив из 8 элементов, где 1 означает, что соответствующий кандидат присутствует на поле и не содержит мину.
            Перебор с возвратом ещё не освоили?

            Добавлено
            Граф не нужен. Бинарная матрица.
            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
            0 пользователей:


            Рейтинг@Mail.ru
            [ Script execution time: 0,0314 ]   [ 18 queries used ]   [ Generated: 28.03.24, 22:27 GMT ]