Игра на ориентированном графе , прям сильно много нюансов возникло

Цитата

что-то не всегда четко, т к к конкретной вершине можно подойти разными путями, при этом она может иметь разный цвет в зависимости от подхода

Блин, FasterHarder, да прочитай ты уже написанное!

Цитата

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

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

Цитата

если из непокрашенной вершины все ребра ведут в красные, то красим текущую вершину в зеленый

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

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

Цитата

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

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

Цитата AVA12 @ 17.03.21, 15:30

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

это, очевидно, что ложь

Прикреплённая картинка

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

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

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

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

Цитата FasterHarder @ 18.03.21, 05:46

это, очевидно, что ложь

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

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

Цитата Akina @ 18.03.21, 06:13

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

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

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

Цитата Akina @ 18.03.21, 06:13

И раскраска на рисунке неверная.

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

Цитата Akina @ 18.03.21, 06:13

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

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

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

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

Сообщение отредактировано: FasterHarder - 18.03.21, 06:25

Цитата FasterHarder @ 18.03.21, 05:46

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

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

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

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

Сообщение отредактировано: OpenGL - 18.03.21, 09:16

Я категорически отказываюсь понимать, что происходит.

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

В связи с чем вопрос: а о чем конкретно мы беседуем?

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

Добавлено 18.03.21, 20:32
С раскраской всё правильно.
Всегда ли мы можем раскрасить вершины? Когда мы не можем покрасить. Если из непокрашенной вершины v есть путь в непокрашенную вершину u. А из непокрашенной u есть путь в непокрашенную v. Чтобы покрасить вершину v, надо знать цвета всех следующих, то есть надо знать и цвет u. А чтобы узнать цвет u, нужно знать цвета всех следующих, в том числе и v.
Но в этом случае между u и v замыкается орцикл, которого быть не должно.

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

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

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

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

Цитата AVA12 @ 18.03.21, 15:29

Время от времени Akina и OpenGL предлагают свои варианты алгоритмов.

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

Добавлено 19.03.21, 06:01

Цитата FasterHarder @ 19.03.21, 05:35

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

Вот так

Цитата

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

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

Добавлено 20.03.21, 19:49
единственный, самый-самый единственный момент еще есть, который вроде понятен на 99%, но 100% уверенности нет: победная стратегия НА КАЖДОМ ХОДЕ содержит ход в красную вершину или нет...вроде, да! но чую, что подстава может быть, хотя на 99%, что да...

F: Как решить задачу?
A: Вот так
O: А ещё вот так
F: О, я придумал, решу-ка её неправильно!
У меня один вопрос только - зачем спрашивал-то, если решение не нужно?

Да молодец ТС Я лично кое-что новое для себя узнала.

swf

Скрытый текст

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

Цитата FasterHarder @ 08.04.21, 00:08

swf

Скрытый текст

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

В тематике шутки не шучу.