Почему делает*, путь, находящий иногда, входит в прямые линии и иногда диагонали? (Java)
Сортировка ключей требует, чтобы Компаратор искал каждое значение для каждого сравнения. Больше масштабируемого решения использовало бы entrySet непосредственно, с тех пор значение будет сразу доступно для каждого сравнения (хотя я не создал резервную копию этого числами).
Вот универсальная версия такой вещи:
public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue(Map<K, V> map) {
final int size = map.size();
final List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>(size);
list.addAll(map.entrySet());
final ValueComparator<V> cmp = new ValueComparator<V>();
Collections.sort(list, cmp);
final List<K> keys = new ArrayList<K>(size);
for (int i = 0; i < size; i++) {
keys.set(i, list.get(i).getKey());
}
return keys;
}
private static final class ValueComparator<V extends Comparable<? super V>>
implements Comparator<Map.Entry<?, V>> {
public int compare(Map.Entry<?, V> o1, Map.Entry<?, V> o2) {
return o1.getValue().compareTo(o2.getValue());
}
}
существуют способы уменьшить вращение памяти для вышеупомянутого решения. Первый ArrayList создал, мог, например, быть снова использован как возвращаемое значение; это потребовало бы подавления некоторых предупреждений дженериков, но это могло бы стоить того для допускающего повторное использование кода библиотеки. Кроме того, Компаратор не должен быть перераспределен при каждом вызове.
Вот более эффективное хотя менее привлекательная версия:
public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue2(Map<K, V> map) {
final int size = map.size();
final List reusedList = new ArrayList(size);
final List<Map.Entry<K, V>> meView = reusedList;
meView.addAll(map.entrySet());
Collections.sort(meView, SINGLE);
final List<K> keyView = reusedList;
for (int i = 0; i < size; i++) {
keyView.set(i, meView.get(i).getKey());
}
return keyView;
}
private static final Comparator SINGLE = new ValueComparator();
Наконец, если необходимо непрерывно получать доступ к отсортированной информации (вместо того, чтобы просто сортировать его время от времени), можно использовать дополнительную много карту. Сообщите мне, нужно ли Вам больше деталей...
9 ответов
Если вы ищете простое решение, могу ли я предложить немного рандомизации?
Я имею в виду следующее: в примере кода cokeandcode есть вложенные- циклы for, которые генерируют «состояния-преемники» (если использовать термин AI). Я имею в виду точку, в которой он проходит по квадрату 3x3 вокруг «текущего» состояния, добавляя новые места в куче для рассмотрения.
Относительно простое исправление (должно :)) состояло бы в том, чтобы немного изолировать этот код и иметь он, скажем, сгенерировал связанный список узлов перед остальной частью этапа обработки. Затем Containers.Shuffle (или Generics.Shuffle?) В этом связанном списке и продолжите обработку там. В общем, есть распорядок дня: "createNaiveNeighbors (узел)" который возвращает LinkedList = {(node.x-1, node.y), (node.x, node.y-1) ...} (простите, пожалуйста, pidgin Java, я пытаюсь (и всегда безуспешно) будьте краткими.
Однако, как только вы создадите связанный список, вы должны просто иметь возможность сделать "for (Node n: myNewLinkedList)" вместо
for (int x=-1;x<2;x++) {
for (int y=-1;y<2;y++) {
И при этом использовать тот же основной код!
В идеале это должно было бы как бы «встряхнуть» порядок рассматриваемых узлов и создать пути ближе к диагонали, но без изменения эвристики. Пути по-прежнему будут наиболее эффективными, но обычно ближе к диагонали.
Обратной стороной, конечно же, является то, что если вы переходите от A к B несколько раз, может быть выбран другой путь. Если это неприемлемо, вам может потребоваться более радикальная модификация.
Надеюсь, это поможет! -Агор
Оба пути имеют одинаковую длину, поэтому алгоритм отлично выполняет свою работу - находит кратчайший путь. Однако алгоритм A * не указывает, КАКОЙ кратчайший путь он выберет. Реализации обычно выбирают «первый» кратчайший путь. Не видя вашего, невозможно точно понять, почему, но если вы хотите получать одни и те же результаты каждый раз, вам придется добавлять какие-то правила приоритета (чтобы желаемый путь появлялся первым в поиске).
Причина, по которой на самом деле довольно проста: путь всегда будет пытаться иметь самая низкая эвристика, потому что поиск выполняется жадно. Приближение к цели - оптимальный путь.
Если бы вы разрешили диагональное движение, этого бы не произошло.
Причина в том, по какому пути должен идти алгоритм.
Я не знаю эвристики, которую использует ваш A *, но в первом случае он должен сначала пройти до конца туннеля, а затем спланировать путь от конца туннеля до цели.
Во втором случае простейшие движения к цели идут вниз, пока она не ударится о стену, а затем он планирует путь от стены к цели.
Большинство известных мне A * работают с эвристикой прямой видимости или Манхэттенским расстоянием в случае блочного мира. Эта эвристика дает вам кратчайший путь, но в случае препятствий, вынуждающих идти путем, отличным от прямой видимости, пути зависят от вашей отправной точки.
Алгоритм будет находиться в зоне прямой видимости как можно дольше.
В каждом случае он предпочитает путь, который быстрее приближает его к его целевому узлу, что и предназначено для A *.
Наиболее вероятный ответ состоит в том, что, идя прямо на юг, мы в первую очередь приближаемся к своей цели; Если пойти противоположным путем, это не выбор, поэтому он оптимизирует подпути по частям, в результате чего чередование движений вверх / поперек считается лучшим.
Если вы хотите, чтобы он шел по диагонали в обратном направлении, вам нужно будет определить некоторые интересные точки на пути (например, вход в туннель) и учесть их в вашей эвристике. В качестве альтернативы вы можете учесть их в своем алгоритме, повторно вычислив любой подпуть, который проходит через интересующую точку.
Раньше они делали предварительно скомпилированный статический анализ карт и размещали маркеры поиска пути в узких местах. В зависимости от того, какова ваша конечная цель, это тоже может быть хорошей идеей.
Если вы ' Если мне действительно интересно узнать, что происходит, я бы посоветовал отобразить шаги поиска A *. Учитывая ваш вопрос, он может открыть вам глаза.
If I saw right, the sphere is moving first to the right in a straigt line, because it cannot got directly toward the goal (path is blocked). Then, it goes in a straight line toward the goal. It only looks diagonal.
Does your search look in the 'down' direction first? This might explain the algorithm. Try changing it to look 'up' first and I bet you would see the opposite behavior.
В зависимости от реализации вашей астары вы увидите разные результаты с одной и той же эвристикой, как упоминали многие люди. Это из-за связей, когда две или более дорожек связаны, то, как вы упорядочиваете открытый набор, будет определять, как будет выглядеть окончательный путь.Вы всегда получите оптимальный путь, если у вас есть допустимая эвристика, но посещенные узлы будут увеличиваться с увеличением количества имеющихся у вас связей (по сравнению с эвристикой, производящей не так много связей).
Если вы не думаете, что посещение большего количества узлов является проблемой, я бы предложил использовать предложение рандомизации (которое является вашим текущим принятым ответом). Если вы думаете, что поиск большего количества узлов является проблемой, и хотите оптимизировать, я бы предложил использовать какой-то тай-брейк. Кажется, вы используете манхэттенское расстояние, если вы используете евклидово расстояние, когда два узла связаны в качестве разрешения конфликтов, вы получите больше прямых путей к цели и посетите меньше узлов. Это, конечно, без ловушек или препятствий для прямой видимости цели.
Чтобы избежать посещения узлов с блокирующими элементами на прямой видимости, я бы предложил найти эвристику, которая учитывает эти блокирующие элементы. Конечно, новая эвристика не должна работать больше, чем обычный поиск по звездочке.
Я бы посоветовал взглянуть на мой вопрос , поскольку он может дать некоторые идеи и решения этой проблемы.