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

    Блин, FasterHarder, да прочитай ты уже написанное!
    Цитата
    если из непокрашенной вершины можно попасть в зеленую (ход в которую гарантирует победу), то красим текущую вершину в красный цвет (ход сюда ведет к поражению)

    Тут очевидно, что если из некоторой вершины есть ребро, ведущее в зеленую, то сама эта вершина должна быть красной, и никакие подходы, никакие кривые пути этот факт не изменят. Вершина, покрашенная в красный, красной и останется.
    Цитата
    если из непокрашенной вершины все ребра ведут в красные, то красим текущую вершину в зеленый

    Тут очевидно, что прежде чем покрасить вершину в зеленый, нужно покрасить все смежные с ней, а тогда ее цвет определяется однозначно и не меняется. Вершина, покрашенная в зеленый, зеленой и останется.

    Здесь выбор порядка обхода вершин ни на что не влияет. Можно обходить вершины в случайном порядке - если применять только эти два правила, результат в любом случае будет один и тот же! Ты же перемудрил и взял откуда-то совершенно левый навороченный алгоритм, который не равнозначен этим двум простым правилам.

    Цитата
    Перебираем в цикле все тупики. Берем i-й тупик и запускаем от него BFS.

    Можно лучше: берем все покрашенные вершины (изначально - все тупики) и строим циклический список всех непокрашенных вершин, ведущих к ним. И уже по этому общему списку гуляем.
      Цитата AVA12 @
      Тут очевидно, что если из некоторой вершины есть ребро, ведущее в зеленую, то сама эта вершина должна быть красной, и никакие подходы, никакие кривые пути этот факт не изменят. Вершина, покрашенная в красный, красной и останется.

      это, очевидно, что ложь
      Прикреплённая картинка
      Прикреплённая картинка

      ----------------------------------------------------
      в итоге, еще подумав над раскраской начал осознавать, что здесь все гораздо и гораздо и гораздо сложнее, это я за себя говорю)) + сформулировать правила раскраски - проблемно...

      ласт попытка сделать некие правила, хотя ни в одном из них я уже не уверен:
      1. все тупики красные по дефалту и они являются эпицентрами начала движения по вершинам орграфа (дуги инвентированы)
      2. зеленую порождает красная
      3. красную порождает зеленая
      4. красная вершина должна иметь только зеленых соседей. ИСКЛЮЧЕНИЕ: если есть хотя бы один красный сосед, то у этого красного соседа в свою очередь все соседи должны быть красными. Но это невозможно, чтобы у красного все соседи были красными), поэтому, красная вершина должна иметь ТОЛЬКО зеленых соседей - я не уверен в этом на 100%, не знаю...
      5. зеленая вершина должна иметь хотя бы одного красного соседа (ИСКЛЮЧЕНИЕ: если все соседи зеленые, то у любого из этих зеленых соседей тоже все соседи должны быть зелеными, но это вроде тоже невозможно - не уверен на 100%, не знаю...)
      не уверен, но вроде в п4 и п5 исключения можно отбросить. не знаю
      и т.д.

      ну и главная проблема - порядок обхода вершин, хотя это не должно влиять, а по факту влияет. Картинка чуть выше. Если сделать обход чуть по-другому, то вершина №1 станет красной и это уже будет правильно.

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

        С чего бы? ход первого игрока на красный узел - это проигрыш.

        И раскраска на рисунке неверная. Я ещё давно говорил, что начинать надо с поиска всех путей. Потому что раскраска должна вестись строго с учётом чётности пути. Тупик на пути чётной длины - красный, на пути нечётной длины - зелёный, если в узел ведёт несколько путей, то узел зелёный лишь в случае, когда он зелёный для всех путей, не имеющих ветвлений на нечётных узлах.
          Цитата Akina @
          С чего бы? ход первого игрока на красный узел - это проигрыш.

          нет, конечно)

          цель каждого игрока - сходить в КРАСНУЮ вершину, чтобы у противника не было хода, т е загнать противника в тупик

          Цитата Akina @
          И раскраска на рисунке неверная.

          она верная, если следовать озвученным правилам. проблема в правилах

          Цитата Akina @
          Я ещё давно говорил, что начинать надо с поиска всех путей. Потому что раскраска должна вестись строго с учётом чётности пути. Тупик на пути чётной длины - красный, на пути нечётной длины - зелёный, если в узел ведёт несколько путей, то узел зелёный лишь в случае, когда он зелёный для всех путей, не имеющих ветвлений на нечётных узлах.


          скорее всего в этих словах есть смысл и надо копать в этом направлении) но это сложно!)
          ведь с ракраской так все просто казалось, а получать все пути - это же жесть как геморрно..Может попроще что-то есть)

          Добавлено
          в общем ладно, пока уберу анализ в не самый далекий ящик. Тут надо исследовать все с самого начала и думать с нуля.
          пока решение не идет, значит, надо подождать, как говорит Макконел))

          РЕЗЮМЕ: не смог я решить!! ну ладно) авось решу еще, но это неточно...Хотя код я уже давно накропал и мне казалось все там прекрасно, но прожка из 200 тестов 7 тестов НЕ проходит. и так сойдет ))
          Сообщение отредактировано: FasterHarder -
            Цитата FasterHarder @
            в итоге, еще подумав над раскраской начал осознавать, что здесь все гораздо и гораздо и гораздо сложнее, это я за себя говорю

            Если решать обходом в ширину, а не в глубину, то действительно немного сложнее получается. Но, если поменять порядок раскраски и помещения в очередь, то обходом в ширину тоже несложно выходит
            1. Кладём все тупики в очередь (только кладём, не раскрашиваем)
            2. Если очередь пуста - выходим. Иначе - п.3.
            3. Достаём из очереди очередную вершину. Если она покрашена, то её просто пропускаем и идём в п.2. Иначе - п.4
            4. Смотрим на список вершин, в которые мы можем из текущей вершины попасть. Есть три возможных варианта
              • Есть вершины, в которые мы можем попасть из текущей и которые мы ещё не покрасили. В этом случае просто эту вершину пропускаем, вернёмся к ней позже.
              • Есть вершины, которые мы покрасили в красный. Тогда текущую красим в зелёный
              • В списке красных вершин нет. Тогда в красный цвет красим текущую (в частности, у тупиков красных вершин не будет, поэтому они покрасятся в красный).
              Если выполнился вариант 2 или 3 (т.е. если мы покрасили вершину), то идём в п.5, иначе в п.2
            5. Все вершины, из которых мы можем попасть в текущую, закидываем в очередь, и идём в п. 2

            Насчёт подпунктов пункта 4. Может быть такое, что у тебя одновременно выполняются первые два пункта (покрашены не все вершины, и среди покрашенных есть красные), в этом случае можешь любое действие выполнять, на результат это не повлияет.
            Сообщение отредактировано: OpenGL -
              Я категорически отказываюсь понимать, что происходит.

              amk и я предлагаем простой, надежный, независящий от порядка обхода алгоритм из двух простейших правил. FasterHarder каким-то образом усматривает в нем изъяны и в качестве "иллюстрации" выдает совершенно другой, непонятно откуда взявшийся и явно кривой алгоритм. Время от времени Akina и OpenGL предлагают свои варианты алгоритмов.

              В связи с чем вопрос: а о чем конкретно мы беседуем?
                Замечу только, что всех путей в ациклическом орграфе может быть экспоненциальное количество от числа вершин.
                Будет ли работать раскраска, ещё не поняла. Щас подумаю :)

                Добавлено
                С раскраской всё правильно.
                Всегда ли мы можем раскрасить вершины? Когда мы не можем покрасить. Если из непокрашенной вершины v есть путь в непокрашенную вершину u. А из непокрашенной u есть путь в непокрашенную v. Чтобы покрасить вершину v, надо знать цвета всех следующих, то есть надо знать и цвет u. А чтобы узнать цвет u, нужно знать цвета всех следующих, в том числе и v.
                Но в этом случае между u и v замыкается орцикл, которого быть не должно.
                  В общем это задача, взята из раздела "Обход графа в глубину", т е она исключительно на DFS и никаких BFS даже юзать, вроде нельзя)
                  + не нужно здесь заниматься полным перебором чего-либо, вроде как

                  А ведь все сходится относительно DFS:
                  1. на 1ом этапе определяем все тупики через DFS
                  2. на 2ом этапе также, юзая ДФС, можно пораскрашивать и получить ответ

                  т е кроме DFS ничего и не нужно)

                  кстати, ДФС ведь бывает разного вида: рекурсивная и через стек. ИМХО, через стек попроще, т к рекурсия сама по себе (по своей природе) обладает повышенной встроенной сложностью. Вроде как порядок обхода вершин орграфа через рекурсию или стек в ДФС одинаков. Вроде бы. В графах я ни в чем не уверен, все надо проверять по "тысячу" раз...
                  --------------------------
                  в общем всем спс, кто пытался помочь
                  пока буду думать, как произвести раскраску, юзая ДФС. Оч. сильно сомневаюсь, что приду к решению, но попробовать ведь надо))
                    Цитата AVA12 @
                    Время от времени Akina и OpenGL предлагают свои варианты алгоритмов.

                    Они точно такие же, просто детали реализации расписаны. По крайней мере мои варианты :)

                    Добавлено
                    Цитата FasterHarder @
                    пока буду думать, как произвести раскраску, юзая ДФС.

                    Вот так
                      Цитата
                      В общем это задача, взята из раздела "Обход графа в глубину", т е она исключительно на DFS и никаких BFS даже юзать, вроде нельзя

                      О, а вот и постановка задачи, первая серия.
                        поломав голову, все-таки кое в чем прозрел!)
                        во-первых, я НЕ отказался от своих правил из сообщения №13, а переработал их
                        во-вторых, и самое главное, меня осенила великая мысль)) и я наконец-то таки понял, где был этот тонкий момент не понимания
                        На самом деле все оказалось еще тоньше и я не уверен, что это предел "тонкости" здесь...

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

                        Итак, свод правил раскраски. Предполагается, что дуги инвертированы + тупики найдены + покрашены в красный цвет. Задача любого игрока встать на красную вершину. Непосещенные вершины имеют белый цвет.
                        1. если вершина белая и в нее попадают из зеленой, то она становится красной.
                        2. если вершина белая и в нее попадают из красной, то она становится зеленой.
                        3. если вершина красная и в нее попадают из красной, то она становится зеленой! И этого НЕДОСТАТОЧНО! Теперь надо запускать ДФС из этой перекрашенной вершины (хотя раньше ДФС из этой вершины УЖЕ был запущен!!). По факту получается "вложенный" ДФС. Это тотально важно! И именно этот момент я раньше НЕ учитывал и получал лютейшие проблемы)
                        4. если вершина зеленая и в нее попадают из зеленой, то...оч.тоже интересный момент...
                        надо проверять всех ее соседей на исходном орграфе (без инвертирования дуг, который) и:
                        4.1. если все соседи имеют зеленый цвет (не уверен, но это вроде возможно, только при наличии единственного соседа, но не суть...), то красим в красный + запускаем от нее ДФС
                        4.2. если хотя бы один сосед имеет красный цвет, то оставляем зеленым (вот здесь есть частично отсылка к сообщению №16)
                        тут еще есть подвариант, когда несколько соседей ЕЩЕ НЕ раскрашены, а все раскрашенные соседи зеленые...хм...вроде (вроде!!) оставлять также надо зеленым. Позже, др.пути либо дадут красного соседа либо получим вариант №4.1 и она автоматически перекраситься в красный.

                        все! повторю: что самое важное, что я достиг в этом анализе по сравнению со своим старым - запуск ДФС от только что перекрашенной вершины.
                        -------------------------------------------------------------------------------------------------------------------------------------------
                        С уверенностью в 99% напишу, что ставлю под сомнение правильность алгоритмов раскраски, который претендуют раскрасить все вершины, посетив их по одному разу!! Если выше, кто-то приводил такой вариант, то с вероятностью 99% он не прав)) Это будет работать не на всех графах, а только на тривиальных.
                        -------------------------------------
                        А теперь покрасим граф, предложенный Akina в сообщении №10. кстати, спс ему за такую конфигурацию графа, т к в нем собраны очень проблемные моменты, которые не "видны" сходу.
                        Прикреплённая картинка
                        Прикреплённая картинка

                        стартовая вершина №1. В процессе раскраски эта вершина ЧЕТЫРЕ РАЗА МЕНЯЛА СВОЙ ЦВЕТ!!!: красный (первый путь: 86421), зеленый (231), красный (87531) и наконец приняла свой окончательный вариант ЗЕЛЕНЫЙ (21).
                        ---------------------------------------------------------------
                        Выводы:
                        1. невозможно раскрасить вершины, посетив их по одному разу
                        2. каждый новый путь (новых заход ДфС) уточняет выигрышную стратегию, перекрашивая вершины, полученные на предыдущих итерациях
                        -------------------------------------------------------------
                        Если кому не лень + он НЕ согласен с приведенным сводом правил (по сути, алгоритмом изложенными выше в этом посте), то просьба просто скинуть граф, который я НЕ смогу раскрасить правильно, посмотрим))

                        Является ли данный алгоритм оптимальным, с точки зрения производительности?? Далеко не уверен, но др.способа я не вижу. Вариант с четностью-нечетностью, предложенный Akina, возможно и оптимальнее, но он гораздо сложнее))) мне его не поднять 100%, поэтому даже не буду пытаться понять его)
                        -------------------------------------------
                        И последнее: если реализовать визуальную раскраску графа, то граф будет "мигать". Речь о сложных конфигурациях, с тысячами вершин и большим числом дуг. Каждый новый путь будет "уточнять" выигрышную стратегию и лишь на последнем пути она будет получена окончательно, т е когда будет рассмотрен ПОСЛЕДНИЙ тупик и его последний путь, ведущий к стартовой вершине. До этого момент победитель НЕ определен!!!

                        спс за внимание, я кончил)

                        Добавлено
                        единственный, самый-самый единственный момент еще есть, который вроде понятен на 99%, но 100% уверенности нет: победная стратегия НА КАЖДОМ ХОДЕ содержит ход в красную вершину или нет...вроде, да! но чую, что подстава может быть, хотя на 99%, что да...
                          :crazy:
                          F: Как решить задачу?
                          A: Вот так
                          O: А ещё вот так
                          F: О, я придумал, решу-ка её неправильно!
                          У меня один вопрос только - зачем спрашивал-то, если решение не нужно? :D
                            Да молодец ТС :D Я лично кое-что новое для себя узнала.
                              swf
                              Скрытый текст
                              если не стебешься, то спс)) а может намекаешь, что у меня полный бред и здесь все совсем по-другому!)
                                Цитата FasterHarder @
                                swf
                                Скрытый текст
                                если не стебешься, то спс)) а может намекаешь, что у меня полный бред и здесь все совсем по-другому!)

                                В тематике шутки не шучу.
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0443 ]   [ 18 queries used ]   [ Generated: 13.06.21, 17:41 GMT ]