Что такое хороший ориентир для A * (AStar)?

Я написал себе A *, он работает достаточно хорошо, и настало время оценить его производительность (потенциально против других решений, чтобы увидеть, как он работает).Что такое хороший ориентир для A * (AStar)?

Для обеих визуальных обратных связей и развлечений я использую его как изображение maze solver. Во-первых, я знаю, что это не то, для чего A * был разработан в первую очередь, но я считаю, что это довольно хороший способ (но не единственный) проверить его. Согласен ? Я сохранил это очень просто: белые пиксели - это узлы, а другие цвета - стены.

Я подумывал this maze (большое изображение) на него, но я знаю, что это будет

явно занять некоторое время, потому что он имеет более 3 000 000 ребер (и немного меньше половина как стены, но все же)
не обязательно быть хорошим индикатором, негабаритные среда

Подводя итог: в какой среде является хорошим стресс-тест для а *? Каков порядок величины графов в аппликативном A * (например, в играх)?

источник

2013-06-07 teh internets is made of catz

Я не уверен, что этот вопрос имеет смысл - я не думаю, что «вообще хороший индикатор» * существует вообще *. Различные настройки работают лучше или хуже, в зависимости от проблемы; некоторые, например, используя логическую сетку для хранения закрытого «списка», даже не применяют * вообще * во многих ситуациях, но * могут быть * (но не обязательно) удивительными, когда они это делают. – harold

@harold Не может быть «одной скамейки, чтобы управлять ими всех», это точно, но я думаю, что есть интересные вещи, которые нужно попробовать. Я не говорю об оптимизации, мне было интересно, не такой ли лабиринт, как тот, который я связал, не очень конкретный случай, который не является репрезентативным для глобального использования алгоритма. –

Ну, это интересный тест, по крайней мере, если это то, что вы имеете в виду. – harold

тест хороший стресс является цифровая сеть дорог для
1) часть большой страны (например, Испания, Франция, Германия), а затем
2) Вся страна. (несколько миллионов узлов)

OpenStreetMap предоставляет такие данные, но очень важно импортировать это на график.

источник

2013-06-07 17:28:52 AlexWien

Это очень хорошая идея, но я боюсь, что это выходит за рамки моего опыта (я предполагаю, что это очень сложные данные). Я все равно посмотрю! –

@tehinternetsismadeofcatz GraphHopper уже импортирует большие данные из openstreetmap легко (например, во всем мире), так что это уже не так много. Он реализует A *, но вы можете легко реализовать свои собственные (в Java) и более важные: вы можете сравнивать и улучшать производительность :) – Karussell

@AlexWien для меня/graphhopper во всем мире сценарий имеет ок. 80mio и ~ 110mio для автомобиля. германия имеет 9mio ребра и 7mio узлы – Karussell

Я внедрил серийную версию Parallel New Bidirectional A* на карте местности размером около 420 x 760 (более 325 000 шестиугольников). Самый сложный длинный диагональный путь на этой карте, составляющий около 1080 шагов, завершается примерно через 0,45 секунды истекшего времени на одном ядре i7 с чуть менее 90 000 закрытых элементов после завершения.

Обратите внимание, что карты местности есть лабиринт как качества, насколько Дейкстры и А * обеспокоены, потому что широкий диапазон ступенчатых затрат (fr0m 2 до 10+ для этой карты) убедитесь, что все допустимые эвристические неэффективны.

источник

2013-07-03 01:59:31

Что такое хороший ориентир для A * (AStar)?

ответ

Смежные вопросы