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

    Вот условие задачи:
    Есть шахматная доска размера N x M (N, M из отрезка [1 .. 350]). На некоторых клетках стоят черные фигуры (может быть ни одной черной фигуры). Нужно на свободные клетки доски расставить максимальное количество красных коней (их кол-во предполагается бесконечным), чтобы они не били друг друга.
    Обязательное требование: решить при помощи графов (графовых алгоритмов)
    -----------------------------------------------
    На что обратил внимание после анализа:
    1. речь про черные ФИГУРЫ, а не про коней.
    2. красные кони должны не бить ДРУГ ДРУГА, а не черные фигуры.
    3. привязка к шахматам - для отвода глаз, от шахмат здесь лишь возможный код коней (буквой "Г"). ИМХО, удобнее вместо "шахматной доски" рассматривать прямоугольную сетку.

    Какие проблемы получил:
    1. У меня абсолютно не получается сформулировать эту задачу в терминах графов...Подскажите эту формулировку, плз.

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

    2 подход. Нумеруем ячейки заданной сетки слева направо и снизу вверх натуральными числами. Например, если сетка размера 7 х 7, то будет так:

    1 2 3 4 5 6 7
    8 9 10 11 12 13 14
    ....
    43 44 45 46 47 48 49
    Можно нумеровать по-другому, на итоговый алгоритм НЕ повлияет. Наверное)

    Рассмотрим более простой пример на заданной сетке размера 3 х 3 (БЕЗ черных фигур) и сразу построим граф (визуально, а не с тз памяти):
    Прикреплённая картинка
    Прикреплённая картинка

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

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

    Единственная проблема: понять, в какую ячейку (др.словами, какую вершину удалять и все смежные с ней) ставить красного коня на очередном "ходе" алгоритма...
    Только 1 мысль: отбирать ту вершину графа, которая имеет наименьшую степень. Но я ни на грамм не уверен, что это то, что нужно. Если несколько вершин в графе с одинаковой мин.степенью - берем любую (тоже не факт).
    То есть получается смысл задачи в том, чтобы итеративно удалять вершины из графа со всеми смежными и максимизировать кол-во таких удалений.

    Подскажите как быть-то?
    спс за внимание

    Скрытый текст
    Кому не лень, можете попробовать расставить красных коней на этой сетке. Ответ у меня есть, но у меня не получается расставить коней в макс.количестве, всегда получается меньше.
    Прикреплённая картинка
    Прикреплённая картинка
    Сообщение отредактировано: FasterHarder -
      Иогу расставить 18 коней

      Добавлено
      Больше ничем помочь не могу
        Цитата MIF @
        Иогу расставить 18 коней

        ну, неплохо) У меня тоже вроде 18 получалось в одном из вариантов, но ответ другой

        Цитата MIF @
        Больше ничем помочь не могу

        :D , ну, и на этом спс

        кстати, нашел на забугорном сайте задачу очень похожую (не копия, но близкую вроде, а может и не близкую) и там есть какие-то выкладки и речь ушла В БИГРАФЫ...и там все сложно оказывается и нет здесь простого подхода...мда уж...какие же графы коварные по своей сути. Т е в этой задаче, возможно, надо подключить двудольные графы - ничего себе, в век бы на них здесь не подумал!
          Решение задачи: на одной доске расставляем коней на черные клетки, на второй - на белые. Выбираем лучшее решение из двух.
          Теперь сюда надо бы графы прикрутить :( .
            Вообще-то это решение не всегда лучшее.

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

            Маленькие области, например 2х2, могут быть полностью заставлены красными конями.
              Цитата FasterHarder @
              Кому не лень, можете попробовать расставить красных коней на этой сетке. Ответ у меня есть, но у меня не получается расставить коней в макс.количестве, всегда получается меньше.

              23 штуки.
              Прикреплённая картинка
              Прикреплённая картинка
              Сообщение отредактировано: Akina -
                Цитата Akina @
                23 штуки.

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


                Рейтинг@Mail.ru
                [ Script execution time: 0,0565 ]   [ 19 queries used ]   [ Generated: 29.03.24, 15:57 GMT ]