Кратчайший путь в плане шестиугольника?
В последнем конкурсе IEEE Xtreme проблема, которую я пытался решить, заключается в следующем:
Введите две точки p1 (x1, y1), p2 (x2, y2), вы должны найти длину кратчайшего пути от p1 до p2,
например, если p1 (1,1), p2 (4,4), то кратчайший путь имеет длину 9 ребер,
Я сделал что-то вроде поиска в глубину, он отлично работает, если расстояние между двумя точками мало, и, например, для точек уходит много времени (1,1) & (10,10),
И есть ограничение на баллы, максимальный балл составляет (12,12).
Мой подход заключается в том, чтобы преобразовать приведенную выше картинку в неориентированный граф со всеми весами в 1, а затем найти кратчайший путь.
вот моя функция, которая находит кратчайший путь:
int minCost;
vector<int> path;
multimap<int,int> Connections;
typedef multimap<int,int>::iterator mmit;
void shortestPath(int cs){
if(cs > minCost)
return;
if(path.back() == Target){
if(cs < minCost)
minCost = cs;
return;
}
pair<mmit,mmit> it = Connections.equal_range(path.back());
mmit mit = it.first;
for( ; mit != it.second ; ++mit){
if(isVisited(mit->second))
continue;
markVisited(mit->second);
path.push_back(mit->second);
shortestPath(cs+1);
markUnvisited(mit->second);
path.pop_back();
}
}
Есть ли способ быстрее, чем это? Могу ли я использовать dijkstra для этого неориентированного графа ??
Решение
Использование Dijkstra или любого вида поиска на основе графа кажется здесь полным излишним. В каждой вершине вам просто нужно выбрать следующую вершину, которая приближает вас к вашей цели.
Итак, вы начинаете в центре (1,1). Вам нужно выбрать начальную вершину. Очевидно, это один на юго-востоке.
Оттуда у вас есть три варианта: двигаться на запад, двигаться на северо-восток или двигаться на юго-восток. Это на самом деле выбор у вас на каждой второй вершине. Вы выбираете направление, которое приближает вас (т. Е. Составляет наименьший угол с вашей целью).
Фактически, вы можете представить все свои координаты вершин в некотором обманчивом виде. Обратите внимание, что все они примерно на полпути между шестигранными координатами. Таким образом, вы можете сказать, что первая вершина находится в (1.5,1.33),
Ваши возможные шаги при первой координате — это направления:
west = (0, -0.67)
north-east = (-0.5, 0.33)
south-east = (0.5, 0.33)
Давайте назовем это странным движением. Теперь у четного движения есть следующие варианты:
east = (0, 0.67)
north-west = (-0.5, -0.33)
south-west = (0.5, -0.33)
Таким образом, все, что вам нужно сделать, это для каждого возможного направления, проверить новое расстояние (по т.е. Пифагор) к вашей цели. Выберите новую вершину, которая имеет наименьшее расстояние из трех вариантов. Очевидно, вам не нужно вычислять фактическое расстояние — квадрат расстояния в порядке.
Вы можете выяснить начальные и последние ходы, я уверен.
Наконец, я использую двойную арифметику, которая неточна. Вы можете масштабировать все направления (и, конечно, координаты шестиугольника) на 6 и использовать целые числа.
Другие решения
Других решений пока нет …