вопросы относительно использования* с загадкой с 15 квадратами

Может быть, он сойдется быстрее, если вы сначала будете стрелять по промежуточным целям. Например, засчитывайте только верхнюю и правую строки. Уложить эти ряды не займет много времени, тогда вы сможете собрать оставшиеся 3x3.

Да, именно так я слышал об этой проблеме. g(x) - это количество слайдов плитки, которые имели место, а h(x) - это общее расстояние, на котором все плитки находятся от требуемых квадратов. До сегодняшнего дня я не видел ничего, кроме этого подхода (манхэттенский эвристический ), но только что нашел этот так называемый диагональный ярлык - возможно, вы захотите проверить его.

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

В 19 веке американский пасьянсный мастер Сэм Лойд продал эти игрушки с 15 и 14 перевернутыми, и предложил большой приз любому, кто мог бы продемонстрировать решение, поменяв плитку (предположительно, кроме той, что у меня есть, маленькая отвертка). В сегодняшнем правовом климате, я не знаю, посмел бы он.

Одной из возможностей было бы попытаться вставить его в правильную конфигурацию или в конфигурацию 15-14.

То, что я узнал

• , по-видимому, хорошо известно, но не мне: схождение A* очень чувствительно к эвристической функции.
• если я напишу эвристическое произведение, которое весит 2 верхних строки больше, чем другие строки, то оно сходится намного быстрее, но путь, как правило, намного длиннее.
• Я обнаружил, что диагональная функция H(x), показанная здесь, сходится намного быстрее, чем расстояние на Манхэттене, для 15-ти...квадратная головоломка.
• даже при эвристической функции, способствующей более быстрому сближению, существует большая дисперсия во времени выполнения. Иногда она находит путь за 10 секунд. Иногда 10 минут. Иногда дольше.
• Количество ходов, требуемых на найденных путях, с использованием диагональной эвристики, варьируется от 30 до 110.

Я однажды запрограммировал такой алгоритм (windowsApp) и у меня есть следующий опыт

1]) самое большое удовольствие видеть робота в действии, если он использует (близкое) оптимальное решение. (Для человеческого наблюдателя невозможно понять, как робот "думает" и сделка из хаоса в порядок внезапно)

2) Если вы хотите найти оптимальное решение, то ваша функция h() должна недооценивать истинное расстояние. Если вы ее переоцениваете, то не найдете оптимального.

3) Потенциальное пространство состояний огромно, 15!/2 (10^12). Если Вы используете плохую эвристическую функцию, то Ваши наборы данных будут расти намного больше, чем размер Вашей основной памяти, и каждый доступ к данным будет требовать множества дисковых обращений. Если это произойдет, то время выполнения будет "бесконечным".

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);
    }
}