Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898486 Wed, 27 Dec 2023 19:10:52 +0000 Цветной орграф. 2 фишки. 1 финиш https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898486
Нумеруем вершины в исходном графе. Строим "конфигурационный" граф из N*N вершин, каждой его вершине сопоставлена пара номеров вершин исходного графа, задающая позиции фишек. Вершины этого нового графа соединены ребром, если в исходном графе возможен переход между этими состояниями. Тогда решение исходной задачи сводится к поиску кратчайших путей в "конфигурационном" графе (путей - потому что в "конфигурационном графе будет 2*N-1 финишных вершин).]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898375 Tue, 26 Dec 2023 05:38:00 +0000 Цветной орграф. 2 фишки. 1 финиш https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898375 Цитата Akina @
То есть итоговый результат - сумма количества шагов, сделанных каждой фишкой.

понятно, полностью согласен

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

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

а вообще все это интересно)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898369 Tue, 26 Dec 2023 05:02:12 +0000 Цветной орграф. 2 фишки. 1 финиш https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898369 Цитата FasterHarder @
а что по этому поводу думаешь?

ИМХО. Поскольку движения другой фишки - полноправные и необходимые шаги для достижения конечного результата, следует считать количество отдельных шагов безотносительно к тому, какой фишкой они сделаны. То есть итоговый результат - сумма количества шагов, сделанных каждой фишкой.

Цитата FasterHarder @
было предложено создать граф из N^2 вершин

Ну по сути мы имеем не двумерный граф, а трёхмерный куб графов - каждый слой соответствует своему цвету исходящих дуг. И на каждом шаге проверяем, что одна из фишек находится на слое, соответствующем цвету узла местоположения другой фишки, причём каждая из фишек может находится на нескольких слоях одновременно.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898368 Tue, 26 Dec 2023 04:39:37 +0000 Цветной орграф. 2 фишки. 1 финиш https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898368 Цитата Akina @
Да, очень похоже на то... как говорится, "Нутром чую, а доказать не могу!".

ок, спс, понял)

а что по этому поводу думаешь?
Цитата FasterHarder @
Так, только фишек две штуки, считать нужно их сумму шагов или только той, которая сможет дойти до финиша?



зы: в инете раза 3-4 уже спрашивали про это задание ( или оч. похожее ), нигде ответа нет полного, но в одном месте было предложено создать граф из N^2 вершин и что-то там делать, пока не разобрался с предложенной идеей, возможно, там тоже полный перебор предлагается...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898367 Tue, 26 Dec 2023 04:34:07 +0000 Цветной орграф. 2 фишки. 1 финиш https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898367 Цитата FasterHarder @
Главный вопрос: это NP-полная задача и решение нужно искать ПОЛНЫМ перебором всех возможных ходов обоих фишек?

Да, очень похоже на то... как говорится, "Нутром чую, а доказать не могу!".]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898366 Tue, 26 Dec 2023 03:20:19 +0000 Цветной орграф. 2 фишки. 1 финиш https://forum.sources.ru/index.php?showtopic=440889&view=findpost&p=3898366
Есть такая задача.
Дан орграф, состоящий из N вершин ( N = [ 5 .. 99 ] ). Каждая вершина и дуга графа окрашена в определенный цвет. Количество различных цветов от 1 до 5. Задается 2 вершины, в которых находятся по фишке игрока, и конечная вершина ( финиш ). Игрок имеет право передвигать фишку по дуге, если ее цвет совпадает с цветом вершины, в которой находится другая фишка. Ходить поочередно фишками необязательно. Игра заканчивается, если одна из двух фишек встанет на конечную вершину ( достигнет финиша ). Найти кратчайший путь до финиша.

==========================================================

Если я все правильно понял из условия, то вот поясняющая картинка, где задействовано 3 различных цвета:
___________________________.png (, : 269)

Некоторые моменты:
1. просят найти кратчайший путь. В данном случае можно считать, что орграф взвешенный и вес ВСЕХ дуг = 1. Т е кратчайший путь - это кол-во дуг, по которым нужно пройти до финиша. Так, только фишек две штуки, считать нужно их сумму шагов или только той, которая сможет дойти до финиша?
2. элементарный случай, когда финиш совпадает с одной из стартовых вершин, в этом случае ответ = 0. Окэй.
3. если обе фишки стартуют из одной стартовой вершины, ну, они могут где-то разойтись и пойти по разным траекториям, вроде такой вариант вполне может быть
4. если вершины и дуги окрашены 1 цветом ( например, все черное ), ну, тогда DFS ( BFS ) и побеждает та фишка, которая "ближе" к финишу - это какой-то частный элементарный случай

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

Главный вопрос: это NP-полная задача и решение нужно искать ПОЛНЫМ перебором всех возможных ходов обоих фишек? А то были мысли сначала построить матрицу расстояний от каждой вершины до финиша, не обращая на цвет, но вроде все это пустое...

спс

Добавлено
примерно такие структуры данных могут потребоваться
Скрытый текст
    // коллекция допустимых цветов для окрашивания вершин и дуг орграфа
    enum COLOR
    {
        COLOR_INVALID_VALUE = 0,
        COLOR_FIRST = 1,
        COLOR_RED = 1,
        COLOR_GREEN = 2,
        COLOR_BLUE = 3,
        COLOR_LAST = 3
    };
     
    // для окраски вершин можно задать отдельный массив ( можно через vector )
    #define VERTEX_COUNT 5
    COLOR vertex_color[ VERTEX_COUNT ] =
        {
            COLOR_RED,
            COLOR_GREEN,
            COLOR_GREEN,
            COLOR_BLUE,
            COLOR_RED
        };
     
    // описание дуги
    struct Edge
    {
        int from;       // метка вершины, из которой выходит дуга
        int to;         // метка вершины, в которую входит дуга
        COLOR color;    // цвет дуги
     
        // параметрический конструктор
        Edge( const int from, const int to, const COLOR color )
        {
            this -> from = from;
            this -> to = to;
            this -> color = color;
        }
    };
     
    // для представления связей между вершинами использовать список смежности, как вариант
]]> FasterHarder Алгоритмы