Поиск в ширину в Java

Question

Мне нужно выполнить поиск в ширину в Java для назначения. У меня есть сетка плиток 5х5 (всего 24 - 1 плитка оставлена ​​«пустой»). Смысл поиска состоит в том, чтобы переставить плитки, переместив «пробел» вверх, вниз, влево или вправо, чтобы в конечном итоге переставить плитки в правильном порядке.

Для этого поиска я создал «очередь» Arraylist. У меня есть метод, который принимает состояние по индексу 0 этого массива, находит каждый из возможных законных шагов и затем добавляет их каждый в конец массива.

Теоретически это продолжается до тех пор, пока в конечном итоге не будет найдено «состояние цели». Проблема в том, что, когда я запускаю поиск, массив 'queue' просто продолжает становиться все больше и больше. Сегодня я оставил его на несколько часов, но решение так и не было найдено.

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

Любые советы или подсказки будут высоко оценены!

Answer 1

Прежде всего, я бы определенно использовал реальный объект Queue вместо ArrayList. Вот страница API Java на интерфейсе очереди: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html - на этой странице вы можете видеть, что есть много разработчиков очереди, если вы не знаете, что выбрать, подойдет простой LinkedList. ArrayList будет иметь огромный удар по производительности, потому что он быстро удаляется только с конца, если вы удаляете из любого места в массиве, он должен сдвинуть ВСЁ на единицу ( SLOW !). Вы будете ставить в очередь в конце и убирать в начале, поэтому МЕДЛЕННО !

Теперь вы прямо не упомянули, что снимаете с себя предметы (удаляете их) после того, как закончите с ними, так что я полагаю, что это так, потому что это было бы одной из причин.

Вам нужно специально использовать поиск в ширину? Если я рассчитал правильно, есть 25! (факториальные) комбинации, то есть 15511210043330985984000000 комбинаций, что теоретически означает, что если вы выполняете поиск в ширину, ваш алгоритм вряд ли когда-нибудь завершится. Разрешен поиск в глубину? Если вы должны использовать поиск в ширину, единственный способ ускорить его - это обрезать состояния, которые не могут привести к оптимальному решению. Не уверен, как бы вы поступили об этом.

Answer 2

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

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

public Queue<Position> queue = new LinkedList<Position>();
public Set<Position> done = new HashSet<Position>();

public Position[] findPath(Position start, Position goal) {
    if (done.contains(start)) return null;

    done.add(start);
    // add subsequent states to `queue`
    ...
}

Как упоминалось в других ответах, поиск в глубину является намного лучшим решением в этом случае. Предполагая, что позиция goal достижима, она должна привести к экспоненциально превосходящему времени поиска для всех позиций, кроме самых искусственных.

Answer 3

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

РЕДАКТИРОВАТЬ: если оставить в стороне алгоритмические ограничения, возможно, существует формула для перемещения блока X в положение Y в положение Z без нарушения каких-либо других тайлов. Учитывая это, вы можете просто вычислить все необходимые преобразования. Я сейчас размышляю над проблемой.

Answer 4

Хорошо, следующая вещь: если бы я делал ваш список посещений, я бы использовал Set (вероятно, TreeSet ), который бы автоматически сортировал состояния так, чтобы при поиске было ли новое состояние побывали раньше, будет намного быстрее.

Все, что вам нужно сделать, это заставить ваш класс состояний реализовать интерфейс Comparable . (надеюсь, вы уже ожидали что-то подобное и сделали это классом). Если вы еще не знаете, используя метод CompareTo этого интерфейса, вы определяете порядок сортировки объектов, который, конечно, будет использоваться посещаемым множеством. Оттуда вы можете настроить метод compareTo, чтобы он работал как сравнение строк, за исключением ваших плиток.

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

State 1: ABCDEFGHIJKLMNOP
State 2: BCADEFGHIJKLMNOP

Естественно, состояние 1 будет первым в порядке. Так что просто экстраполируйте этот механизм сравнения для работы с плитками на плитки (я уверен, что у ваших плиток есть идентификаторы или индексы или что-то не так?), И вы получите отсортированный список посещенных. Затем, когда вы вызвали visit.contains (состояние), программа сможет очень быстро рассчитать, было ли посещено состояние или нет.

Answer 5

То, как я сейчас это делаю, таково:

• 2 Arraylists; Очередь и Посещенные
• Начальное состояние автоматически добавляется в список посещенных
• Получены все возможные законные ходы с самого начала, и каждый из них сравнивается с теми, которые хранятся в гостевом массиве.
• Те законные ходы, которые не создают «посещенное» состояние, добавляются в очередь.
• Состояние, сохраненное в индексе 0 массива, занято, и процесс повторяется.

Я вижу из предыдущих ответов, что мне, вероятно, следует изменить arraylists в другую коллекцию. Но я проверяю, что состояния не дублируются.

Answer 6

Возможно целенаправленный поиск в глубину. Начните с решения 9 краевых плиток, уменьшив головоломку до сетки 4х4. Затем решите 7 краевых плиток этого, уменьшив сетку 3х3, которая должна быть легкой для вашего исходного алгоритма.

Answer 7

Вы не сказали, проверяете ли вы это или нет, но похоже, что вы не сокращаете циклы.

Во-первых, предположим, что вместо того, чтобы представлять движения как перемещение пустого квадрата в каком-то направлении, вы вместо этого указали номер плитки, который был перемещен. (Он гарантированно будет уникальным.) Теперь предположим, что допустимым шагом является «3» - перемещение плитки № 3 в пустое пространство. Результатом является новый макет платы. Правильный ход оттуда - снова переместить тайл 3, и теперь вы вернулись туда, откуда начали.

Головоломки слайдера могут легко иметь большие циклы. Если есть сетка 2x2 с 1-2-3-пустым в ней, то допустимая последовательность ходов 1-2-3-1-2-3-1-2-3-1-2-3 - которая отправляет вам вернуться к началу.

Если ваш поиск не проверяет и не удаляет дублирующиеся доски, поиск в ширину все равно будет прерван (при условии, что ошибок нет, и нет ошибки четности (?), Делающей вашу доску неразрешимой) - существует правильное решение, которое заключается в том, что Если длина N равна ходу, и вам потребуется определенное время для обработки каждой последовательности K ходов, так что в конечном итоге вы получите N и ваше решение. Однако время для каждой длины хода увеличивается в геометрической прогрессии (до 4 ходов с каждой доски). Вы, вероятно, бьетесь в памяти.

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

Answer 8

Я должен написать код для обоих. Итак, я собираюсь перейти к поиску в глубину. До того, как я это сделал, я просто хотел убедиться, что я не буду смеяться над своим курсом по созданию кода, который занял целую вечность и один день, чтобы найти решение !!!!!!!

Answer 9

Я думаю, что идея этого упражнения заключается в том, чтобы вы поняли, что поиск в глубину - лучший подход к этой конкретной головоломке.

Answer 10

Я выполнил «грубый поиск» - проблема в том, что с сеткой 5x5 существует так много комбинаций, что она просто вечна. Я оставил его работающим, пока я шел на работу ... 8 часов спустя он все еще шел, размер массива очереди достигал 100 000 различных состояний, и мой компьютер звучал так, как будто он перегревался и взрывался LOL

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