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

Всем хай! Сходу к делу!

Дан граф (ациклический, ориентированный невзвешенный). Кол-во вершин и дуг может быть несколько сотен тысяч (поэтому частные случаи даже можно не рассматривать). На произвольной вершине (стартовая вершина) кладут фишку. Есть 2 игрока. За один ход каждый из них может передвинуть фишку на смежную вершину по дуге. Игроки ходят по очереди. Цель игрока - загнать противника в тупик, т е получить ситуацию, когда у соперника нет хода. Побеждает тот, кто загнал противника в тупик.
------------------------------------------------------------------
Сначала показалось, что это несложно, но, подумав, осознал, что здесь что-то совсем для меня непростое...
Самая главная проблема - наличие параллельных путей при достижении тупика. Если бы их не было, тогда поиском в глубину все бы решилось нормально.

Это ведь задача на поиск оптимальной стратегии, как я понимаю. Но я не уверен, что ее можно в принципе получить, т к каждый ход все меняется и КАЖДЫЙ из игроков в каждый момент своего хода выбирает как бы "новую" оптимальную стратегию или по крайней мере ухудшает оптимальную стратегию противника.

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

Какие были мысли:
1. получать расстояния для каждого игрока от вершины с фишкой до всех тупиковых вершин (только тупиковых) + смотреть на четность-нечетность сделанных шагов. Но вроде это бессмысленно, т к алгоритмы типа Дейкстры находят кратчайшие пути, а ведь далеко не факт, что противник будет также следовать по этим кратчайшим путям и свернет на параллельный путь, убив весь этот анализ.
2. построить матрицу расстояний между всеми вершинами (алгоритм Флойда или +Уоршелла). Возможно, что это пригодится в каком-то моменте основного алгоритма. Но сама по себе эта матрица не решает проблему исходной задачи.
3. задействовать поиск в глубину(DFS). Уверен, что здесь это точно надо юзать!). Но, вообще, ДФС ведь нужен для ОБХОДА вершин графа, а НЕ для прокладки путей. Но благодаря дфс можно достаточно легко получить тупиковые вершины. Проблема, что вариантов достижение тупика от заданной вершины может быть тысячи (параллельные пути) + противник своим ходом может свернуть куда ему выгодно.
4. как-то применить топологическую сортировку графа. Это я от балды говорю)
---------------------------------------------------------------------
Как я понимаю, ведь по сути игроки равносильные исполнители, у них одинаковая возможность хода и анализа, т е достаточно понять, как действовать одному игроку, значит, 2ой будет действовать аналогично со своей колокольни только)
Я правильно понимаю, что анализ нужно проводить динамически, т е от вершины, где лежит фишка и НИКАКОГО предварительного анализа (до начала игры) делать НЕ нужно, да??

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

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

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

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

Akina, я лишь частично (очень частично) понял твое сообщение.
Как мне показалось, ты намекаешь на выигрышную стратегию, например для игрока №1. Выигрышная стратегия - стратегия, приводящая к победе, независимо от ходов противника (при безошибочной игре противника не всегда существует). Смысл ее в том, что игрок №1 "направляет" игрока №2 по нужному пути независимо от того, как сходит игрок №2.
Игроку №1 надо, чтобы расстояние до тупика было НЕЧЕТНЫМ (1, 3, 17, 9999 шагов и т.д.) или четным, если рассматривать случай, когда игрок №1 уже походил в какую-то вершину. Например, стоит игрок №1 в стартовой вершине, перед ним развилка на 173 смежных вершины. Ему нужно сходить в вершину, расстояние от которой до тупика четное число. Затем ходит игрок №2 - куда захочет. Игрок №1 снова выбирает из набора возможных путей ту вершину, расстояние до тупика которое четно и т.д. Т е игрок №1 постоянно "навязывает" свой путь независимо от того, куда сходил игрок №2. Все это хорошо, но ведь возможны случаи, когда ходит игрок №1 и перед ним стая вершин и у КАЖДОЙ вершины расстояние до тупика - нечетное число. Выбора как бы нет, но это не означает, что игрок №1 не может выиграть. Он может временно согласиться пройти по "неправильному" для него пути, а через несколько итераций снова задать свое направление.
Да, я понимаю, что в своем сообщении ты не это описывал), просто решил написать про выигрышную стратегию, которая здесь вот таким образом не применима.

Akina, я бы хотел провести декомпозицию алгоритма на подалгоритмы, т к мне не хватает ума все это охватить и понять сразу. И пусть будет неоптимально, просто бы хоть как-то понять. (хотя в задаче еще есть ограничение по времени , т е как бы намек на то, что метод грубой силы тут не нужен, хотя я не уверен, что без него вообще можно реализовать)
---------------------------------------------------------
Вот хотелось бы понять, насколько все это пригодится в решении (забыл сделать ремарку, что тупиков может быть больше одного, разумеется + из конкретной вершины можно проложить путь разной протяженности до разных тупиков):
1. Получение всех тупиков достижимых из заданной вершины. В этом может помочь DFS+стек (вроде стек, а не очередь, т к она для BFS вроде). В результате будет сформирован одномерный массив вершин в том или ином виде. Хотя структуры данных оч.важны тоже, разумеется - без них дело гиблым оказывается при кодировании)
2. Получить множество всех вершин, через которые может проходить какой-либо путь до какого-либо тупика
3. ДЛЯ КАЖДОЙ вершины из п.2 найти расстояние ДО КАЖДОГО тупика! Это двумерный массив, где по оси Ох, допустим откладываются тупики, по оси Oy - №вершины, а на пересечении - расстояние между ними (или можно просто true/false аля чет/нечет длина)

И вот владея этой информацией (из п.3) разве невозможно проанализировать победу игрока №1 или №2??
Например, есть стартовая вершина и ходит игрок №1. Он может "просмотреть" все возможные пути (конкретно расстояния) до каждого достижимого тупика из этой вершины. Проблема выбора остается, т к путей нечетной длины может быть несколько...непонятно какой взять... ... а может ЛЮБОЙ)) навряд ли...

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

На самом деле никакие пути искать не надо. Такие задачи решаются раскраской графа.
Вершины помечаются как выигрышные и проигрышные. И по этой раскраске строится оптимальная стратегия.

Изначально все вершины непомеченные (помечены как неопределённые).
1a. Тупиковые вершины помечаются как выигрышные - поставив в них фишку мы выигрываем.
2. Вершины, из которых можно передвинуть фишку в выигрышную позицию помечаем как проигрышные - если мы поставим в них фишку, противник передвинет её в выигрышную позицию и выиграет.
1b. Вершины, из которых все пути ведут в проигрышные позиции, помечаем как выигрышные - если мы поставим в них фишку, противник будет вынужден передвинуть её в проигрышную позицию.

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

Поправка: Позиция называется выигрышной, если игрок, делающий в ней ход выигрывает.
Поэтому в описанном алгоритме надо поменять местами проигрышные и выигрышные позиции.

Сообщение отредактировано: amk - 16.03.21, 10:52

amk, прикольный метод с раскраской, у меня даже мысли не возникло про это)

но есть ряд моментов!
1. некая взятая вершина может принадлежать разным путям. Для одного пути - победная, для другого - проигрышная. Как понимаю приоритет имеет "проигрышный" статус вершины, т к никто из игроков не хочет оказаться в этой вершине независимо от того по какому пути дошел до нее, т к немедленно будет наказан соперником??
2. чтобы понять, побеждает игрок №1 или №2 надо раскрасить граф и просто посмотреть на ПЕРВЫЙ ход 1ого игрока: есть ли смежная хотя бы ОДНА победная вершина?? Их может быть НЕСКОЛЬКО - игрок №1 может вставать в любую.

Цитата FasterHarder @ 16.03.21, 07:38

1. некая взятая вершина может принадлежать разным путям.

А тут зависит от того, чей ход. Если твой, и есть выигрышный путь - вершина выигрышная. Если не твой, и есть проигрышный путь - вершина проигрышная. Варианты, когда все пути одного типа - тривиальны.

Цитата Akina @ 16.03.21, 07:46

А тут зависит от того, чей ход.

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

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

Цитата FasterHarder @ 16.03.21, 07:38

чтобы понять, побеждает игрок №1 или №2 надо раскрасить граф и просто посмотреть на ПЕРВЫЙ ход 1ого игрока: есть ли смежная хотя бы ОДНА победная вершина

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

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

p.s. может быть я здесь сильно ошибаюсь и поторопился с таким выводом

Сообщение отредактировано: FasterHarder - 16.03.21, 08:36

Цитата Akina @ 16.03.21, 09:33

3

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

Добавлено 16.03.21, 10:08
Подытожим алгоритм! Кому не лень и несложно, плиз проверьте + поправьте, если что.

1. находим все возможные тупики от заданной вершины. Всего в графе N вершин. Будет одномерный массив, состоящий из N элементов. У тупиков будут стоять 1цы, у остальных 0. Поиск тупиков через ДФС(стек)
2. помечаем все тупики статусом "победа"
3. инвертируем дуги исходного графа!
4. в цикле перебираем все тупики и от каждого тупика запускаем BFS (очередь). Помечаем чередованием вершины статусом "победа-поражение". ВАЖНО! Если встретилась вершина со статусом "победа", а ей для данного пути надо поставить статус "поражение", то ставим "поражение", т к у "поражения" высочайший приоритет. Также не меняем статус "поражение" на "победа" при возникновении обратной ситуации. Есть такой момент здесь: при обходе BFS будет задействовано много "лишних" вершин, которые не принадлежат ни одному из возможных путей. Это некритично - не обращаем на это внимания) На самом деле не оч.понятно, в какой момент заканчивать BFS, запущенный от текущего тупика. Ладно, пусть работает до упора - это НЕ оптимально и здесь можно как-то усовершенстовать.
5. после назначения статуса "победа-поражения" смотрим смежные вершины от стартовой. Если есть хотя бы одна вершина со статусом "победа" - победил игрок №1, иначе игрок №2.

Для статуса "победа-поражение", наверное, завести отдельный одномерный массив из N элементов (0 - поражение, 1 - победа). По дефалту поставить всем статус = 1.
язык Си, никаких STL-ских (делающих всю работу) приблуд

примерно так

Цитата FasterHarder @ 16.03.21, 07:38

1. некая взятая вершина может принадлежать разным путям. Для одного пути - победная, для другого - проигрышная.

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

Цитата FasterHarder @ 16.03.21, 07:38

2. чтобы понять, побеждает игрок №1 или №2 надо раскрасить граф и просто посмотреть на ПЕРВЫЙ ход 1ого игрока: есть ли смежная хотя бы ОДНА победная вершина?

Не надо смотреть смежные вершины, пометка вершины уже сообщает тебе, выигрываешь ты или нет (см поправку в описании алгоритма). Смежные

Я допустил ошибку при именовании пометок. Вершину графа игры (позицию) принято считать выигрышной, если игрок, начиная в ней игру, при правильной стратегии выигрывает. Поэтому в описании надо поменять местами выигрышные / проигрышные позиции.

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

При маркировке позиций можно дополнительно определить число полуходов до окончания игры.
Вершины помеченные по первому пункту алгоритма получают оценку 0.
По второму - минимальная из оценок соседних проигрышных вершин + 1.
По третьему - максимальную из оценок соседних вершин (все они выигрышные) + 1.

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

Сообщение отредактировано: amk - 16.03.21, 11:09

Цитата FasterHarder @ 16.03.21, 09:37

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

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

Akina, интересный граф и проблемы в программе возникли)

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

FasterHarder, нету тут никаких тонкостей. Просто не надо слишком мудрить, надо тупо следовать правилам: если из непокрашенной вершины можно попасть в зеленую (ход в которую гарантирует победу), то красим текущую вершину в красный цвет (ход сюда ведет к поражению), если из непокрашенной вершины все ребра ведут в красные, то красим текущую вершину в зеленый. В цикле гуляем по всем непокрашенным вершинам графа и применяем эти два правила (если возможно) до тех пор, пока все вершины не будут покрашены.

P. S. У тебя на картинке цвета инвертированы. По-моему нагляднее так: красный цвет - "ты туда не ходи", зеленый цвет - "ты сюда ходи".

Сообщение отредактировано: AVA12 - 16.03.21, 21:16

Цитата AVA12 @ 16.03.21, 21:12

У тебя на картинке цвета инвертированы. По-моему нагляднее так: красный цвет - "ты туда не ходи", зеленый цвет - "ты сюда ходи".

изначально так и было (в первых сообщениях), а потом уже по совету amk инвертировал, но это ведь НЕ принципиально с т.з. алгоритма

Цитата AVA12 @ 16.03.21, 21:12

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

AVA12, выше ведь писал, что планирую запускать BFS от каждого тупика, а сам тупик закрашен "красным". Насчет правил, да, согласен, конечно, и они выработаны, но здесь все равно, что-то не всегда четко, т к к конкретной вершине можно подойти разными путями, при этом она может иметь разный цвет в зависимости от подхода.

Вообще, надо бы разобраться подетальнее с этой раскраской, конечно, чтобы снять любые сомнения.
Все тупики получены. Сразу их все безраздумья красим в красный цвет. Тут однозначно!
Перебираем в цикле все тупики. Берем i-й тупик и запускаем от него BFS. Не уверен, что бфс тут идеально подходит, но вроде должен подходить) (прим. дуги к этому моменту в орграфе инвертированы + также все вершины кроме тупиковых имеют "серый" цвет, якобы непосещенные). Т е все возможны 3 цвета: красный (ход туда ведет к победе), зеленый (ход туда приводит к победе противника), серый.

возможные случаи раскраски:
1. стоим на красной вершине и дуга к серой ---> красим серую в зеленый - тут вроде однозначно.
2. стоим на зеленой вершине и дуга к серой ---> красим серую в красный - тут вроде однозначно.
3. стоим на зеленой и дуга к зеленой. хм... Тут момент: а надо ли зеленую перекрашивать в красный? получается, что, НЕТ! сделав вершину-достижения красной будем обман игрока, он подумает, что надо в нее заходить, а соперник потом переведет его дальше в красную). Т е вариант "зеленая-зеленая" оставляем без изменений
4. стоим на красной и дуга к красной. хм... Тут момент: а надо ли красную перекрашивать в зеленую? получается, что, ДА! если оставить красной, то это будет обманкой для игрока, т к соперник его следующим ходом переведет в красную.
все, др.комбинаций здесь нет.

что-то мне подсказывает, что это НЕТОЧНЫЙ алгоритм раскраски, который не учитывают все возможные случаи. Как обычно с графами, все намного тоньше и умнее)
что не так с подалгоритмом раскраски??

Да просто запусти обход вглубь из текущей вершины

// True - побеждает тот, кто из этой вершины начинает, false - побеждает второй игрок
bool can_win(int vertex_number)
{
    if(уже_считали_эту_вершину) return старый_результат;
    // В тупике мы проигрываем, т.е. побеждает другой игрок
    if(это_тупик) return false;
    for(auto v : соседи_текущей_вершины)
        // Если в той вершине побеждает второй игрок, то мы пойдём туда, т.к. в этом случае мы будем этим "вторым"
        if(!can_win(v)) return true;
    // Не судьба, тут побеждает наш противник
    return false;
}

Метод минимакса, который используют для игр двух лиц с полной информацией, описан в книге Нильса Нильсона "Принципы искусственного интеллекта".
Есть два игрока, назовём их Мин и Макс. Мин минимизирует свой проигрыш, Макс максимизирует свой выигрыш. Каждая позиция - вершина игрового дерева. Дерево "слоистое", чередуются слои с ходом Мина и слои с ходом Макса. Мы играем за Макса, неважно, какой ход он делает, первый или второй. Начинаем строить дерево от текущей позиции с ходом Макса.
Теперь, внимание, игровое дерево строится с порождением всех возможных ходов для каждой позиции. Это полный перебор. И его (дерево) для данной размерности мы не построим вплоть до позиций, где игра заканчивается. Строим, докуда можем. Построили. Теперь придумываем эвристическую оценочную функцию, чтобы оценивать позицию одним числом. Её придумывают так, чтобы позиции с большей оценкой были выгодны Максу. Для листов (позиций без продолжения) рассчитываем оценку согласно эвристике, затем оценка распространяется вверх к корню дерева и Макс выбирает из всех возможных ходов ход с большей оценкой.

Цитата

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

Блин, 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

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

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

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