Цветной орграф. 2 фишки. 1 финиш , алгоритм + структуры данных

[FasterHarder]

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

Есть такая задача.
Дан орграф, состоящий из N вершин ( N = [ 5 .. 99 ] ). Каждая вершина и дуга графа окрашена в определенный цвет. Количество различных цветов от 1 до 5. Задается 2 вершины, в которых находятся по фишке игрока, и конечная вершина ( финиш ). Игрок имеет право передвигать фишку по дуге, если ее цвет совпадает с цветом вершины, в которой находится другая фишка. Ходить поочередно фишками необязательно. Игра заканчивается, если одна из двух фишек встанет на конечную вершину ( достигнет финиша ). Найти кратчайший путь до финиша.

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

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

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

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

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

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

спс

Добавлено 26.12.23, 03:26
примерно такие структуры данных могут потребоваться

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

// коллекция допустимых цветов для окрашивания вершин и дуг орграфа
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;
    }
};
 
// для представления связей между вершинами использовать список смежности, как вариант

[Akina]

Цитата FasterHarder @ 26.12.23, 03:20

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

Да, очень похоже на то... как говорится, "Нутром чую, а доказать не могу!".

[FasterHarder]

Цитата Akina @ 26.12.23, 04:34

Да, очень похоже на то... как говорится, "Нутром чую, а доказать не могу!".

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

а что по этому поводу думаешь?

Цитата FasterHarder @ 26.12.23, 03:20

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

зы: в инете раза 3-4 уже спрашивали про это задание ( или оч. похожее ), нигде ответа нет полного, но в одном месте было предложено создать граф из N^2 вершин и что-то там делать, пока не разобрался с предложенной идеей, возможно, там тоже полный перебор предлагается...

[Akina]

Цитата FasterHarder @ 26.12.23, 04:39

а что по этому поводу думаешь?

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

Цитата FasterHarder @ 26.12.23, 04:39

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

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

Сообщение отредактировано: Akina - 26.12.23, 05:11

[FasterHarder]

Цитата Akina @ 26.12.23, 05:02

То есть итоговый результат - сумма количества шагов, сделанных каждой фишкой.

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

Цитата Akina @ 26.12.23, 05:02

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

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

а вообще все это интересно)

[AVA12]

Либо я чего-то не понимаю, либо задача эта не NP, а очень даже P.

Нумеруем вершины в исходном графе. Строим "конфигурационный" граф из N*N вершин, каждой его вершине сопоставлена пара номеров вершин исходного графа, задающая позиции фишек. Вершины этого нового графа соединены ребром, если в исходном графе возможен переход между этими состояниями. Тогда решение исходной задачи сводится к поиску кратчайших путей в "конфигурационном" графе (путей - потому что в "конфигурационном графе будет 2*N-1 финишных вершин).

Сообщение отредактировано: AVA12 - 27.12.23, 19:20