Самый короткий путь в сетке между двумя точками. С уловом

У меня есть эта проблема, когда мне нужно найти самый короткий путь в сетке NxM из точки A (всегда вверху слева) до точки B (всегда справа внизу), только двигаясь вправо или вниз. Звучит просто, а? Ну вот улов: я могу только переместить число, показанное на плитке, на которой я сейчас сижу. Позвольте мне проиллюстрировать:

2 5 1 2
9 2 5 3
3 3 1 1
4 8 2 7

В этой сетке 4x4 самый короткий путь займет 3 шага, идущий от верхнего левого 2 узла до 3, а оттуда 3 узла справа до 1, а затем 1 node до цели.

[2] 5 1 2
 9 2 5 3
[3] 3 1 [1]
 4 8 2 [7]

Если бы не самый короткий путь, я мог бы также воспользоваться этим маршрутом:

[2] 5 [1][2]
 9 2 5 3
 3 3 1 [1]
 4 8 2 [7]

Для этого, к сожалению, потребуется whopping 4 шага, и, следовательно, это не в моих интересах. Это должно немного прояснить ситуацию. Теперь о вводе.

Пользователь вводит сетку следующим образом:

5 4 // height and width
2 5 2 2 //
2 2 7 3 // the
3 1 2 2 // grid
4 8 2 7 //
1 1 1 1 //

Домашнее задание

Я подумал об этом, но не могу прийти к лучшему решению, чем упростить введенную сетку в не взвешенный (или отрицательный вес) график и запустить на нем что-то вроде dijkstra или * (или что-то вроде этих строк). Ну... это та часть, где я заблудился. Я реализовал что-то для начала (или что-то сразу бросать трэш). Это не имело никакого отношения к дикстре или А * или чему-либо; просто прямой поиск по ширине.

Код

#include <iostream>
#include <vector>
struct Point;
typedef std::vector<int> vector_1D;
typedef std::vector< std::vector<int> > vector_2D;
typedef std::vector<point> vector_point;
struct Point {
 int y, x;
 vector_point Parents;
 Point(int yPos = 0, int xPos = 0) : y(yPos), x(xPos) { }
 void operator << (const Point& point) { this->Parents.push_back(point); }
};
struct grid_t {
 int height, width;
 vector_2D tiles;
 grid_t() // construct the grid
 { 
 std::cin >> height >> width; // input grid height & width
 tiles.resize(height, vector_1D(width, 0)); // initialize grid tiles
 for(int i = 0; i < height; i++) //
 for(int j = 0; j < width; j++) // input each tile one at a time
 std::cin >> tiles[i][j]; // by looping through the grid
 }
};
void go_find_it(grid_t &grid)
{
 vector_point openList, closedList;
 Point previous_node; // the point is initialized as (y = 0, x = 0) if not told otherwise
 openList.push_back(previous_node); // (0, 0) is the first point we want to consult, of course
 do
 {
 closedList.push_back(openList.back()); // the tile we are at is good and checked. mark it so.
 openList.pop_back(); // we don't need this guy no more
 int y = closedList.back().y; // now we'll actually
 int x = closedList.back().x; // move to the new point
 int jump = grid.tiles[y][x]; // 'jump' is the number shown on the tile we're standing on.
 if(y + jump < grid.height) // if we're not going out of bounds
 { 
 openList.push_back(Point(y+jump, x)); // 
 openList.back() << Point(y, x); // push in the point we're at right now, since it the parent node
 }
 if(x + jump < grid.width) // if we're not going out of bounds
 { 
 openList.push_back(Point(y, x+jump)); // push in the new promising point
 openList.back() << Point(y, x); // push in the point we're at right now, since it the parent node
 }
 }
 while(openList.size() > 0); // when there are no new tiles to check, break out and return
}
int main()
{
 grid_t grid; // initialize grid
 go_find_it(grid); // basically a brute-force get-it-all-algorithm
 return 0;
}
</point></int></int></vector></iostream>

Я должен, вероятно, также указать, что время работы не может превышать 1 секунду, а максимальная высота и ширина сетки - 1000. Все плитки также являются числами от 1 до 1000.

Спасибо.

Отредактированный код

#include <iostream>
#include <vector>
struct Point;
typedef std::vector<int> vector_1D;
typedef std::vector< std::vector<int> > vector_2D;
typedef std::vector<point> vector_point;
struct Point {
 int y, x, depth;
 vector_point Parents;
 Point(int yPos = 0, int xPos = 0, int dDepth = 0) : y(yPos), x(xPos), depth(dDepth) { }
 void operator << (const Point& point) { this->Parents.push_back(point); }
};
struct grid_t {
 int height, width;
 vector_2D tiles;
 grid_t() // construct the grid
 { 
 std::cin >> height >> width; // input grid height & width
 tiles.resize(height, vector_1D(width, 0)); // initialize grid tiles
 for(int i = 0; i < height; i++) //
 for(int j = 0; j < width; j++) // input each tile one at a time
 std::cin >> tiles[i][j]; // by looping through the grid
 }
};
int go_find_it(grid_t &grid)
{
 vector_point openList, closedList;
 Point previous_node(0, 0, 0); // the point is initialized as (y = 0, x = 0, depth = 0) if not told otherwise
 openList.push_back(previous_node); // (0, 0) is the first point we want to consult, of course
 int min_path = 1000000;
 do
 {
 closedList.push_back(openList[0]); // the tile we are at is good and checked. mark it so.
 openList.erase(openList.begin()); // we don't need this guy no more
 int y = closedList.back().y; // now we'll actually move to the new point
 int x = closedList.back().x; //
 int depth = closedList.back().depth; // the new depth
 if(y == grid.height-1 && x == grid.width-1) return depth; // the first path is the shortest one. return it
 int jump = grid.tiles[y][x]; // 'jump' is the number shown on the tile we're standing on.
 if(y + jump < grid.height) // if we're not going out of bounds
 { 
 openList.push_back(Point(y+jump, x, depth+1)); // 
 openList.back() << Point(y, x); // push in the point we're at right now, since it the parent node
 }
 if(x + jump < grid.width) // if we're not going out of bounds
 { 
 openList.push_back(Point(y, x+jump, depth+1)); // push in the new promising point
 openList.back() << Point(y, x); // push in the point we're at right now, since it the parent node
 }
 }
 while(openList.size() > 0); // when there are no new tiles to check, break out and return false
 return 0;
}
int main()
{
 grid_t grid; // initialize grid
 int min_path = go_find_it(grid); // basically a brute-force get-it-all-algorithm
 std::cout << min_path << std::endl;
 //system("pause");
 return 0;
}
</point></int></int></vector></iostream>

Теперь программа печатает правильный ответ. Теперь мне нужно оптимизировать (время работы слишком велико). Любые намеки на это? Оптимизация - это единственное, что я сосать.

Ответ

В итоге решение оказалось состоящим из небольшого кода. Чем меньше, тем лучше. Спасибо Dejan Jovanović за прекрасное решение

#include <iostream>
#include <vector>
#include <algorithm>
struct grid_t {
 int height, width;
 std::vector< std::vector<int> > tiles;
 std::vector< std::vector<int> > distance;
 grid_t() // construct the grid
 { 
 std::cin >> height >> width; // input grid height & width
 tiles.resize(height, std::vector<int>(width, 0)); // initialize grid tiles
 distance.resize(height, std::vector<int>(width, 1000000)); // initialize grid tiles
 for(int i = 0; i < height; i++) //
 for(int j = 0; j < width; j++) // input each tile one at a time
 std::cin >> tiles[i][j]; // by looping through the grid
 }
};
int main()
{
 grid_t grid; // initialize grid
 grid.distance[0][0] = 0;
 for(int i = 0; i < grid.height; i++) {
 for(int j = 0; j < grid.width; j++) {
 if(grid.distance[i][j] < 1000000) {
 int d = grid.tiles[i][j];
 if (i + d < grid.height) {
 grid.distance[i+d][j] = std::min(grid.distance[i][j] + 1, grid.distance[i+d][j]);
 }
 if (j + d < grid.width) {
 grid.distance[i][j+d] = std::min(grid.distance[i][j] + 1, grid.distance[i][j+d]);
 }
 }
 }
 }
 if(grid.distance[grid.height-1][grid.width-1] == 1000000) grid.distance[grid.height-1][grid.width-1] = 0;
 std::cout << grid.distance[grid.height-1][grid.width-1] << std::endl;
 //system("pause");
 return 0;
}
</int></int></int></int></algorithm></vector></iostream>
4 ответа

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

Вы можете установить матрицу расстояний D [i, j] на + inf в начале, с D [0,0] = 0. При прохождении матрицы вы просто делаете

if (D[i,j] < +inf) {
 int d = a[i, j];
 if (i + d < M) {
 D[i + d, j] = min(D[i,j] + 1, D[i + d, j]);
 }
 if (j + d < N) {
 D[i, j + d] = min(D[i,j] + 1, D[i, j + d]);
 }
}

Конечное минимальное расстояние находится в D [M -1, N-1]. Если вы хотите восстановить путь, вы можете сохранить отдельную матрицу, которая отмечает, где был найден самый короткий путь.


Ты слишком задумываешься об этом.:) Запустите поиск по ширине. Пространство решений представляет собой двоичное дерево, где каждый node переходит в "правый" или "вниз". Из текущей точки, сгенерируйте нижнюю и правую точки, введите их координаты в очередь, повторите до конца.

Без проверки, что-то вроде этого:

queue = [{ x: 0, y: 0, path: [] }] # seed queue with starting point
p = nil
do
 raise NoSolutionException if p.empty? # solution space exhausted
 p = queue.pop # get next state from the back of the queue
 break if p.x == MAX_X - 1 && p.y == MAX_Y - 1 # we found final state
 l = grid[p.x][p.y] # leap length
 # add right state to the front of the queue
 queue.unshift({x: p.x + l, y: p.y, path: p.path + [p] }) if p.x + l <= MAX_X
 # add down state to the front of the queue
 queue.unshift({x: p.x, y: p.y + l, path: p.path + [p] }) if p.y + l <= MAX_Y
end
puts p.path

Углификация на С++ слева как упражнение для читателя: p


Постройте невзвешенный ориентированный граф:

  • Есть вершины N x M. В дальнейшем вершина v соответствует квадрату сетки v.
  • Существует дуга от вершины u до v, если вы можете перейти от квадрата квадрата u к квадрату v за один ход.

Теперь примените алгоритм кратчайшего пути из верхней правой вершины в левую нижнюю.

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


Начните с подхода грубой силы, чтобы заставить его работать, а затем оптимизируйте его. Грубая сила прямолинейна: запустите ее рекурсивно. Возьмите два хода, рекурсируйте их и так далее. Соберите все действительные ответы и сохраните минимум. Если время работы слишком велико, то вы можете оптимизировать различными способами. Например, некоторые из ходов могут быть недействительными (потому что они превышают размер сетки) и могут быть устранены и так далее. Продолжайте оптимизацию до тех пор, пока входной сигнал наихудшего случая не будет работать с требуемой скоростью.

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

licensed under cc by-sa 3.0 with attribution.