Предположим, у вас есть игровая плата n x n, и у вас есть персонаж, который может двигаться как рыцарь на шахматной доске, за исключением того, что он не может двигаться вверх или влево. И каждый блок, в который он перемещается, имеет значение, которое может быть накоплено в его точках. Игрок пытается максимизировать очки и достигает TОптимизация движения на борту
Я придумал решение, но им интересно, где он может потерпеть неудачу и его время работы.
Моя идея состояла в том, чтобы создать ориентированный взвешенный график (точки как веса) для каждого возможного пункта назначения и запустить алгоритм Дейкстры на графике, однако вместо кратчайшего пути мы найдем самый длинный путь: .
Я предполагаю, что во время выполнения будет O (некоторые вещи + | E | + | V | войти || V |)
Я не уверен, что что-то есть.
Мне кажется, что график ацикличен, в этом случае есть быстрые алгоритмы: [ref1] (http://cs.stackexchange.com/questions/11295/finding-shortest-and-longest-paths-between -two-vertices-in-a-dag) [ref2] (http://stackoverflow.com/questions/2525316/longest-acyclic-path-in-a-directed-unweighted-graph), [ref3] (https: //en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths) – Nabla
Алгоритм не работает, могут быть циклические случаи – RandomGuy
Хм Я думал, что ваше ограничение на движение вниз и вправо сделает это ацикличным. – Nabla