Вопросы об использовании A * с 15-квадратной головоломкой
Я пытаюсь построить решатель A * для головоломки с 15 квадратами.
![alt text]()
Цель состоит в том, чтобы переставить плитки так, чтобы они появлялись в их естественном положении. Вы можете перемещать только одну плитку за раз. Каждое возможное состояние головоломки - это узел в графе поиска.
Для функции h (x) я использую суммарную сумму по всем плиткам дислокации плиток из целевого состояния. На изображении выше, 5 находится в местоположении 0,0, и оно принадлежит в местоположении 1,0, поэтому оно вносит 1 в функцию h (x). Следующая ячейка - это 11, расположенная в 0,1, и принадлежащая в 2,2, поэтому она вносит 3 в h (x). И так далее. РЕДАКТИРОВАТЬ: Теперь я понимаю, что это то, что они называют "расстояние Манхэттен", или " расстояние такси ".
Я использовал счетчик шагов для g (x). В моей реализации для любого узла в графе состояний g просто +1 от предыдущего узла g.
Чтобы найти последовательные узлы, я просто исследую, где я могу переместить "дыру" в головоломке. Для состояния головоломки (он же узел) отображается 3 соседа: дыра может двигаться на север, запад или восток.
Мой поиск A * иногда сходится к решению в 20 секунд, иногда 180, а иногда вообще не сходится (ждал 10 минут или больше). Я думаю, что это разумно. Мне интересно, правильно ли я смоделировал г. Другими словами, возможно ли, что моя функция A * достигает узла в графе по пути, который не является кратчайшим?
Может быть, я не ждал достаточно долго? Может быть, 10 минут не достаточно долго?
Для полностью случайного расположения (при условии отсутствия проблем с четностью), каково среднее число перестановок, которое будет проверено решением A *? (пожалуйста, покажите математику)
Я собираюсь искать логические ошибки в моем коде, но в то же время, какие-нибудь советы?
(PS: это сделано в Javascript).
Кроме того, нет, это не домашняя работа CompSci. Это просто личное исследование. Я просто пытаюсь выучить Javascript.
РЕДАКТИРОВАТЬ: я обнаружил, что время выполнения сильно зависит от эвристики. Я видел 10-кратный коэффициент, примененный к эвристике из статьи, которую кто-то упоминал, и это заставило меня задуматься - почему 10-кратное? Почему линейный? Поскольку это сделано в javascript, я мог бы изменить код для динамического обновления html-таблицы с учетом рассматриваемого узла. Это позволило мне взглянуть на алгоритм по мере его развития. При регулярной эвристике на такси я наблюдал, как она не сходится.
В верхнем ряду было 5 и 12 человек, и они продолжали торчать. Я бы увидел 1,2,3,4 ползущих в верхнем ряду, но потом они выпадут, и другие числа будут двигаться там. То, что я надеялся увидеть, было 1,2,3,4 вроде ползания до вершины, а затем оставаться там.
Я подумал про себя - это не так, как я решаю это лично. Делая это вручную, я решаю верхний ряд, затем 2-й ряд, затем 3-й и 4-й ряды одновременно.
Таким образом, я настроил функцию h (x) для более тяжелого взвешивания старших строк и столбцов "lefter". Результатом было то, что A * сходились намного быстрее. Теперь он запускается за 3 минуты вместо "бесконечно". С "взглядами", о которых я говорил, я вижу, как меньшие числа ползут до верхних рядов и остаются там. Это не только кажется правильным, но и работает намного быстрее.
Я пробую кучу вариантов. Кажется довольно ясным, что среда выполнения A * очень чувствительна к эвристике. В настоящее время лучшая эвристика, которую я нашел, использует суммирование dislocation * ((4-i) + (4-j)) где я и j - строка и столбец, а дислокация - расстояние такси.
Одна интересная часть результата, который я получил: с определенной эвристикой я нахожу путь очень быстро, но это, очевидно, не самый короткий путь. Я думаю, что это потому, что я взвешиваю эвристику. В одном случае я получил путь 178 шагов за 10 секунд. Мои собственные ручные усилия дают решение за 87 ходов. (намного больше 10 с). Требуется дополнительное расследование.
В результате я вижу, что он должен сходиться быстрее, и путь определенно не самый короткий. Я должен думать об этом больше.
Код:
var stop = false;
function Astar(start, goal, callback) {
// start and goal are nodes in the graph, represented by
// an array of 16 ints. The goal is: [1,2,3,...14,15,0]
// Zero represents the hole.
// callback is a method to call when finished. This runs a long time,
// therefore we need to use setTimeout() to break it up, to avoid
// the browser warning like "Stop running this script?"
// g is the actual distance traveled from initial node to current node.
// h is the heuristic estimate of distance from current to goal.
stop = false;
start.g = start.dontgo = 0;
// calcHeuristic inserts an .h member into the array
calcHeuristicDistance(start);
// start the stack with one element
var closed = []; // set of nodes already evaluated.
var open = [ start ]; // set of nodes to evaluate (start with initial node)
var iteration = function() {
if (open.length==0) {
// no more nodes. Fail.
callback(null);
return;
}
var current = open.shift(); // get highest priority node
// update the browser with a table representation of the
// node being evaluated
$("#solution").html(stateToString(current));
// check solution returns true if current == goal
if (checkSolution(current,goal)) {
// reconstructPath just records the position of the hole
// through each node
var path= reconstructPath(start,current);
callback(path);
return;
}
closed.push(current);
// get the set of neighbors. This is 3 or fewer nodes.
// (nextStates is optimized to NOT turn directly back on itself)
var neighbors = nextStates(current, goal);
for (var i=0; i<neighbors.length; i++) {
var n = neighbors[i];
// skip this one if we've already visited it
if (closed.containsNode(n)) continue;
// .g, .h, and .previous get assigned implicitly when
// calculating neighbors. n.g is nothing more than
// current.g+1 ;
// add to the open list
if (!open.containsNode(n)) {
// slot into the list, in priority order (minimum f first)
open.priorityPush(n);
n.previous = current;
}
}
if (stop) {
callback(null);
return;
}
setTimeout(iteration, 1);
};
// kick off the first iteration
iteration();
return null;
}
Ответы
Ответ 1
Поиск A-звезды найдет оптимальное решение, доказав, что все пути, которые еще не решены, не могут быть решены с меньшим количеством ходов, чем текущее решение. Вы не ищите лучшего решения, а самого быстрого решения. Поэтому вы можете оптимизировать свой алгоритм, возвращая первое решение, взвешивая количество шагов ниже, чем ваша эвристическая функция, и эвристика может вернуть чрезмерную оценку.
Сама эвристическая функция лучше всего моделируется Манхэттенским расстоянием и линейным конфликтом. Манхэттенское расстояние хорошо объяснено в других ответах и в статье в Википедии, и вы, похоже, справляетесь с этим. Линейный конфликт добавляет два к манхэттенскому расстоянию для каждой пары блоков, которые должны быть заменены для достижения решения. Например, если строка содержит "3 2 1 4", то один и три должны быть заменены, и для этого нужно переместить в другую строку.
Использование базы данных шаблонов является опцией и может помочь вашему поиску избежать определенных тупиков, а использование памяти для этого 15-головоломки должно быть управляемым.
Ответ 2
Используйте IDA * вместо A *. Вам нужно гораздо меньше памяти. Как эвристика, "Walking distance" , разработанный Ken'ichiro Takahashi, намного эффективнее, хотя использует только 25 кбайт памяти.
Здесь и здесь - английский перевод.
Ответ 3
Да, это то, как я слышал об этой проблеме. g (x) - количество слайдов плитки, которые имели место, а h (x) - общее расстояние, в котором все плитки находятся от требуемых квадратов. Я не видел ничего, кроме этого подхода ( диагональный ярлык - вы можете проверить его.
Ответ 4
Что вы используете для тестовых данных? Если он случайный, вы не сможете решить загадку примерно в половине случаев. Невозможно переключить две плитки, оставив остальных в одном и том же положении, и, если вы достигнете того, что находится почти в конечной позиции, но имеет две черепицы, вы не можете попасть в нужную позицию и не искать алгоритм поиска может успешно завершиться успешно.
В 19-ом столетии американский головоломщик Сэм Лойд продал эти игрушки с 15 и 14 оборотами и предложил большой выигрыш для любого, кто мог бы продемонстрировать решение, переключающее плитки (предположительно, кроме того, что у меня есть, маленькое отвертка). Сегодняшний правовой климат, я не знаю, мог ли бы он посмеяться.
Одна из возможностей состоит в том, чтобы попытаться установить ее в правильную конфигурацию или в конфигурацию 15-14.
Ответ 5
Что я узнал
- очевидно, это известный, но это было не со мной: конвергенция A * очень чувствительна к эвристической функции.
- Если я напишу эвристику, которая весит верхние 2 строки сильнее, чем другие строки, она сходится гораздо быстрее, но путь обычно намного длиннее.
- Я обнаружил, что диагональная функция H (x) показала здесь, чтобы сходиться намного быстрее, чем расстояние Манхэттена, для головоломки 15 квадратов,
- даже с эвристической функцией, которая способствует более быстрой конвергенции, во время выполнения существует большая дисперсия. Иногда он находит путь через 10 секунд. Иногда 10 минут. Иногда дольше.
- Количество ходов, необходимых в найденных путях с использованием диагональной эвристики, колеблется от 30-и до 110.
Ответ 6
Я запрограммировал такой алгоритм один раз (windowsApp), и у меня есть следующий опыт
1), самое интересное увидеть робота в действии, если он использует (почти) оптимальное решение. (Для человека-наблюдателя невозможно понять, как робот "думает" и транзакция от хаоса к порядку неожиданна)
2), если вы хотите найти оптимальное решение, ваша функция h() должна недооценивать истинное расстояние. Если вы переоцените это, вы не найдете оптимального.
3) Потенциальное пространство состояний огромно, 15!/2 (10 ^ 12). Если вы используете плохую эвристическую функцию, ваши наборы данных будут намного превосходить размер вашей основной памяти, и для каждого доступа к данным потребуется несколько обращений к диску. Если это произойдет, время выполнения будет "бесконечным".
Ответ 7
Возможно, он будет сходиться быстрее, если вы сначала запустите промежуточные цели. Например, забирайте только верхнюю и правую строки. Это не займет много времени, чтобы получить эти строки на месте, тогда вы можете решить оставшиеся 3x3.
Ответ 8
check this
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.lang.Object;
class Puzzle extends JPanel implements ActionListener
{
JButton[] b = new JButton[16];
Puzzle()
{
b[0] = new JButton("4");
b[1] = new JButton("11");
b[2] = new JButton("5");
b[3] = new JButton("9");
b[4] = new JButton("1");
b[5] = new JButton("10");
b[6] = new JButton("12");
b[7] = new JButton("13");
b[8] = new JButton("15");
b[9] = new JButton("14");
b[10] = new JButton("3");
b[11] = new JButton("2");
b[12] = new JButton("7");
b[13] = new JButton("8");
b[14] = new JButton("6");
b[15] = new JButton("");
GridLayout grid = new GridLayout(4,4);
setLayout(grid);
for(int i=0;i<16;i++)
add(b[i]);
for(int i=0;i<16;i++)
b[i].addActionListener(this);
}
public void actionPerformed(ActionEvent e)
{
/*if(e.getSource()==b[11])
{
if(b[15].getText()=="")
{
b[15].setText("");
}
}
else if(e.getSource()==b[3])
{
if(b[2].getText()=="")
{
b[2].setText("");
}
}*/
for(int i=0;i<16;i++)
{
System.out.println(e.getSource());
if(e.getSource()==b[i])
{
if(i==5 || i==6 || i==9 || i==10)
{
if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
else if(i==4 || i==8)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
else if(i==7 || i==11)
{
if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==0)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==3)
{
if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==15)
{
if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==12)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==1 || i==2)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i+4].getText()=="")
{
b[i+4].setText(b[i].getText());
b[i].setText("");
}
}
if(i==13 || i==14)
{
if(b[i+1].getText()=="")
{
b[i+1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-1].getText()=="")
{
b[i-1].setText(b[i].getText());
b[i].setText("");
}
else if(b[i-4].getText()=="")
{
b[i-4].setText(b[i].getText());
b[i].setText("");
}
}
}
}
//System.out.println(e.getActionCommand());
}
public static void main(String[] args)
{
JFrame frame = new JFrame("15-Puzzle");
//frame.setContentPane(panel);
JComponent newContentPane = new Puzzle();
//newContentPane.setOpaque(true); //content panes must be opaque
frame.setContentPane(newContentPane);
//panel.add(button);
frame.setSize(400,400);
frame.setVisible(true);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
}
