Как решать задачу с графом?

Question

[Xiran]

Задача

Ваня очень любит играть в компьютерную игру «Подземелья и гоблины». В игре персонаж спускается в одну из комнат подземелья. Подземелье состоит из множества комнат, которые соединены друг с другом тоннелями, но необязательно каждая с каждой. Проход по каждому тоннелю требует определённое количество времени. В каждой комнате есть монеты, которые охраняет гоблин. Как только игрок входит в комнату (в том числе, если входит в подземелье через комнату), то гоблин нападает на него. Чтобы одолеть гоблина в комнате, нужно затратить определённое количество времени. Как только гоблин повержен, игрок забирает монеты в комнате. Если игрок уже был в комнате, то сражаться с гоблином не нужно. По пути в подземелье Ваня нашёл карту, на которой была изображена схема подземелья: черными кружками отмечены комнаты, линиями, соединяющими кружки, отмечены тоннели между комнатами, фиолетовыми кружками отмечены комнаты с выходом из подземелья, черными числами внутри кружков отмечено время битвы с гоблином, жёлтыми числами внутри кружков отмечено количество золота в комнате, чёрными цифрами рядом с чёрными линиями отмечено время пути по тоннелю, синим числом рядом с кружком отмечен номер комнаты. Также в углу карты было отмечено, сколько времени у Вани есть, чтобы зайти в подземелье и выйти из него до момента его обрушения. Как только Ваня подошёл к подземелью, он заметил, что может войти в него через любую комнату, а выйти только через комнаты с выходом. Ваня очень ценит своё время и перед спуском решил разработать стратегию обхода комнат, чтобы собрать максимальное количество монет и успеть выйти из подземелья до его обрушения. Напишите в ответ последовательность комнат, которую должен обойти Ваня, чтобы получить максимальное количество монет, и, через пробел, количество монет после выхода из подземелья.

Как ее решать? В каком направлении копать?

Comments

[Wataru]

Какие даны ограничения? Их полезно знать, это часто большая подсказка.

Answer 1

[Rsa97]

Рекурсивный перебор в глубину из узлов-выходов, ограниченный временем жизни лабиринта, с обнулением посещённых узлов (можно через список посещённых).
Запоминаем маршрут с максимальной выгодой, потом разворачиваем его, получая прямой путь.
Отдельно надо обрабатывать вариант, когда два узла соединены путём с нулевым временем. Тут обход может зациклиться.

Вариант на PHP

<?php

/*
 * Комната 0 введена для унификации алгоритма.
 * Из неё можно попаст в любой выход, в неё попасть из других комнат нельзя.
 */
const NODES = [
    0 => ['battleTime' => 0, 'loot' => 0],
    1 => ['battleTime' => 5, 'loot' => 15],
    2 => ['battleTime' => 2, 'loot' => 1],
    3 => ['battleTime' => 3, 'loot' => 5],
    4 => ['battleTime' => 3, 'loot' => 6],
    5 => ['battleTime' => 4, 'loot' => 7],
    6 => ['battleTime' => 5, 'loot' => 9],
    7 => ['battleTime' => 7, 'loot' => 16],
    8 => ['battleTime' => 2, 'loot' => 3],
    9 => ['battleTime' => 0, 'loot' => 0],
    10 => ['battleTime' => 0, 'loot' => 0],
];

const ROUTE_TIMES = [
    0 => [9 => 0, 10 => 0],
    1 => [2 => 1],
    2 => [1 => 1, 8 => 2, 9 => 3, 4 => 1],
    3 => [9 => 2, 4 => 4],
    4 => [3 => 4, 2 => 1, 5 => 3],
    5 => [4 => 3, 10 => 1],
    6 => [10 => 4, 7 => 4],
    7 => [8 => 4, 6 => 4],
    8 => [2 => 2, 7 => 4, 10 => 6],
    9 => [3 => 2, 2 => 3],
    10 => [5 => 1, 8 => 6, 6 => 4],
];

const MAX_LIFETIME = 25;

function findRoute(array $state): array
{
    $bestState = $state;
    foreach (ROUTE_TIMES[$state['currentNode']] as $nextNode => $travelTime) {
        $nodeTime = $state['lifetime'] + $travelTime +
            (in_array($nextNode, $state['route']) ? 0 : NODES[$nextNode]['battleTime']);
        if ($nodeTime > MAX_LIFETIME) {
            continue;
        }
        $nodeState = findRoute([
            'lifetime' => $nodeTime,
            'currentNode' => $nextNode,
            'wealth' => $state['wealth'] + (in_array($nextNode, $state['route']) ? 0 : NODES[$nextNode]['loot']),
            'route' => [...$state['route'], $nextNode],
        ]);
        if ($nodeState['wealth'] > $bestState['wealth']) {
            $bestState = $nodeState;
        }
    }
    return $bestState;
}

$state = findRoute([
    'lifetime' => 0,
    'currentNode' => 0,
    'wealth' => 0,
    'route' => [],
]);

echo "Route: ", implode(' => ', array_reverse($state['route'])), "\n";
echo "Wealth: ", $state['wealth'], "\n";
echo "Time: ", $state['lifetime'], "\n";

Route: 8 => 2 => 1 => 2 => 4 => 5 => 10
Wealth: 32
Time: 25

Answer 2

[Wataru]

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

Можно применять тот же прием, что и в задаче коммивояжора - расслоите граф на 2^n слоев. Пуст у вас n вершин в изначальном графе. В новом графе каждая вершина соответсвует подмножеству комнат и одной комнате. Фактически, вершина обозначает, какие комнаты вы обошли и где сейчас находитесь.

Ребра есть:
Из вершины ({}, 0) во все вершины ({v},v) ценой goblinTime[v]: это мы можем зайти в лабиринт в любую комнату и должны там гоблина победить.
Из вершины (S, v) в вершину (S,u) ценой path[v,u], если u в S - это мы идем в ранее посещенную комнату.
Из вершины (S, v) в вершину (S+{u},u) ценой path[v,u]+goblitTime[u], если u не в S - это мы идем в ранее не посещенную комнату и бъем там гоблина.

В этом графе на n2^n вершин вам надо найти все кратчайшие пути из начальной ({},0) во все вершины (например, дейкстрой). Потом переберите все вершины в графе (S, v) и, если вершина соответствует комнате с выходом и вы до нее дошли за время не превосходящее время обрушения, то берите сумму количества золота в комнатах в множестве S в качесвте варианта ответа. Из всех них берите максимум.

Answer 3

[alexalexes]

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

Comments

[Alexandroppolus]

Здесь итоговый маршрут может проходить по комнате более одного раза, например если в примере оставить только комнаты 1, 2, 8, 4, 9, это не про Дейкстру