Что не так с моим поиском A* для 8-Puzzle?
Я пытаюсь использовать поиск A* с этими эвристиками для решения 8-головоломок: - h1: количество неуместных плиток - h2: общее расстояние до Манхэттена - h3: сумма вышеупомянутых
Движущаяся плитка известна как 0.
Моя цель состоит в том, чтобы решить эти наборы:
4 1 2
5 8 3
7 0 6
а также
8 6 7
2 5 4
3 0 1
Проблема, с которой я столкнулся, заключается в том, что с моей текущей реализацией A* она способна решить первую проблему, но не для второй проблемы.
Поэтому, пожалуйста, помогите мне понять, что не так с моим кодом A*:
int [,] current = вводится из консоли в виде строки (412583706) и превращается в 2D int, представляющий головоломку. То же самое для правильного, где 0 находится в правом нижнем углу.
var openList = new List<int[,]> { current };
var closedList = new List<int[,]>();
while (openList.Count > 0)
{
steps++;
current = GetBestNodeFromList(correct, dimensions, openList, useHeuristic);
// "GetBestNodeFromList()" finds the cheapest node in the openList.
// cheapest node: lowest value of h3.
openList.Remove(current);
h1 = getHeuristic1b(current, correct, dimensions);
h2 = getHeuristic2b(current, correct, dimensions);
h3 = h1 + h2;
if (h1 == 0 && h2 == 0) { break; }
openList = Puzzle_PossibleNext(current, closedList);
// the method "PossibleNext()" finds possible next moves from the current
// position. if the next move exists in the closedList, it is discarded.
// Drawing the puzzle and showing heuristics.
DrawCurrentState(h1, h2, h3, current, steps);
// adding last visited position to the closedlist.
closedList.Add(current);
}
Первая проблема решается с 7 шагов. Согласно другой программе, которую я тестировал, следующую проблему можно решить с помощью 32 шагов.
Моя программа отличается от другой тем, что первые 4 шага одинаковы, тогда другая программа выбирает другой маршрут, а моя просто продолжает работать вечно и не может найти решение. Похоже, что моя программа выбрала самый дешевый узел, поэтому я не могу понять, что не так.
Это мой первый раз с алгоритмами поиска пути, поэтому я хотел бы решить его. У меня была эта проблема в течение 3 дней, и я чувствую, что перепробовал много решений, но ни одно не работает T_T
С наилучшими пожеланиями.
---- Изменить ----- Дополнительный код:
// Put heuristic value from all in list, then return list item with lowest h-value.
static int[,] GetBestNodeFromList(int[,] correct, int d, List<int[,]> list, string useHeuristic)
{
int[,] n = new int[d,d];
if (list.Count > 0)
{
List<Int32> heuristicsValueList = new List<Int32>();
for (int i = 0; i < list.Count; i++)
{
if (useHeuristic == "h1") { heuristicsValueList.Add(getHeuristic1b(list[i], correct, d)); }
else if (useHeuristic == "h2") { heuristicsValueList.Add(getHeuristic2b(list[i], correct, d)); }
else { heuristicsValueList.Add(getHeuristic3(list[i], correct, d)); }
}
n = list[heuristicsValueList.IndexOf(heuristicsValueList.Min())];
}
return n;
}
--------- edit 2 -------- немного изменил мой код, но все равно не повезло, что установка / узел головоломки и его эвристика все находятся в объекте PuzzleNode.
// возвращает список следующих возможных ходов с текущего узла. // не включает ходы, которые находятся внутри closedNodeList.
static List<PuzzleNode> Puzzle_GenerateNextNodes(PuzzleNode node, List<PuzzleNode> closedNodeList)
{
List<PuzzleNode> nextList = new List<PuzzleNode>();
Point isNow = new Point(0, 0);
// 1) Find where [0] is.
int dimensions = (int)Math.Sqrt((double)node.n.Length);
for (int x = 0; x < dimensions; x++) {
for (int y = 0; y < dimensions; y++) { if (node.n[x, y] == 0) { isNow.X = y; isNow.Y = x; break; } }
}
// 2) Check possible moves.
bool moveUp = false, moveDown = false, moveLeft = false, moveRight = false;
if (isNow.X == 0)
{
moveRight = true;
if (isNow.Y == 0) { moveDown = true; }
else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
else if (isNow.Y == 2) { moveUp = true; }
}
else if (isNow.X == 1)
{
moveRight = true;
moveLeft = true;
if (isNow.Y == 0) { moveDown = true; }
else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
else if (isNow.Y == 2) { moveUp = true; }
}
else if (isNow.X == 2)
{
moveLeft = true;
if (isNow.Y == 0) { moveDown = true; }
else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
else if (isNow.Y == 2) { moveUp = true; }
}
// 3) Create list of possible moves.
// Add moved puzzle node to list over next moves
if (moveRight)
{
int[,] right = new int[dimensions, dimensions];
Array.Copy(node.n, right, node.n.Length);
PuzzleNode tmp = new PuzzleNode( PuzzleMoveRight(right, isNow.X, isNow.Y) );
if (!ListHasThisValue(tmp.n, closedNodeList, dimensions)) { nextList.Add(tmp); }
}
// moveleft, up, down, same structure as moveRight
if (moveLeft)
{
..
}
if (moveUp)
{
..
}
if (moveDown)
{
..
}
return nextList;
}
----------- редактировать 3----------------
Кстати, я хочу спросить, правильно ли понимается моя реализация различных шагов A*. На данный момент поиск моей программы A* делает это:
- Создать начальный список ОТКРЫТО и ЗАКРЫТО, добавить начальный узел в ОТКРЫТО
- Запуск цикла, удаление самого дешевого узла из OPEN, добавление его в CLOSED * Самый дешевый узел определяется значением его манхэттенского расстояния.
- Использование узла для поиска соседей / детей / следующих ходов, добавление их в список SUCCESSOR.
- Изучите список SUCCESSOR, проверьте, содержит ли какой-либо из них состояние цели, иначе добавьте в список OPEN.
- повторите 2-4, исследуя узлы в списке.
Когда я пытаюсь выполнить эти шаги с Q1, я получаю решение в 7 шагов, и это правильно. Это также найдено вручную. Но с Q2 он продолжается до тех пор, пока список OPEN не станет пустым, и больше нечего исследовать. Так чего мне не хватает?
2 ответа
Я смог быстро найти решение с помощью грубой силы. A* должен вернуться к грубой силе, если вы используете абсолютно тупую эвристику. Как вы сравниваете свое состояние со списком закрытых состояний?
var set = new int[,] {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 0 }
};
var clone = (int[,])set.Clone();
var foo = clone == set; // foo is false
var bar = clone.Equals(set); // bar is false
var closedStates = new List<int[,]>();
closedStates.Contains(state); // wrong - contains is using Equals
closedStates.Any(cs => AreEqual(cs, state)); // correct
static bool AreEqual(int[,] stateA, int[,] stateB) {
for (var x = 0; x < DIMENSIONS; x++) {
for (var y = 0; y < DIMENSIONS; y++) {
if (stateA[x, y] != stateB[x, y]) {
return false;
}
}
}
return true;
}
Я хочу поблагодарить всех за помощь в решении этой проблемы.
Я смог найти проблему сегодня. Я не знаю, как это сказать, это действительно глупо. Проблема была не в коде или реализации A* (мой текущий код может отличаться от того, что был опубликован ранее).
Проблема была в чрезмерной зависимости от используемой эвристики. Кажется, что для Q1, эвристики h1, h2 и h3(h1 и h2 имели одинаковую стоимость) могли бы найти решение. Однако для Q2 и h2, и h3 не смогли найти путь к решению, но h1 был. В моей программе я продолжал использовать h3 в качестве эвристики по умолчанию для отладки и тестирования, что также было моим недостатком.
Итак, урок, который следует усвоить, - это знать, с чем вы работаете. Я не смог понять разницу, которую смогли сделать даже самые простые эвристики.
Теперь я могу решить Q1 и Q2. Еще раз всем спасибо. Как программист, я, конечно, учился на этом.
Хотелось бы, чтобы вы все больше отдавали себе должное за то, что нашли время помочь.