8Пазл с A*: Какая структура для открытого набора?

Question

В последнее время я разрабатываю решатель 8-головоломок на Python, и мне нужна небольшая помощь. Пока что я закончил кодирование алгоритма A*, используя расстояние Манхэттена в качестве эвристической функции.

Решатель запускается и находит ~60% решений менее чем за 2 секунды. Однако для других ~40% мой решатель может занять до 20-30 минут, как будто он работал без эвристики.

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

• Мой открытый набор - это массив
• На каждой итерации я просматриваю открытый набор, чтобы найти наименьшее f(n) (сложность: O(n))

У меня такое ощущение, что O (n) - это слишком много для запуска приличного алгоритма A* с такой используемой памятью, поэтому я хотел знать, как мне сделать openset менее "пожирателем времени"

Спасибо за помощь! Хорошего дня

РЕДАКТИРОВАТЬ: ИСПРАВЛЕНО

Я решил свою проблему, которая на самом деле была двойной проблемой.

Я попытался использовать словарь вместо массива, в котором я сохранил узлы по их значению f(n), что позволило мне запустить решатель и ~181000 возможностей игры за несколько секунд.

Вторая проблема (я не знал об этом из-за первой) заключается в том, что я не знал о разрешимости игры-головоломки, и поскольку я рандомизировал начальный узел, 50% головоломок не могли быть решены. Вот почему с openset в виде массива потребовалось так много времени.

Answer 1

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

Ни список массивов, ни словарь не будут эффективными.

---

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

Словарь (он же "карта") технически будет работать, но концептуально это неправильная структура данных, потому что вы ни на что не сопоставляете. Список массивов неэффективен.