Время головоломки A * 8 занимает слишком много времени

Question

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

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

Примечания: в худшем случае, 8 головоломки разрешима не более чем на 31 шагов ...

... Здесь это моя главная функция для моего кода:

List<Node> nodeList = new ArrayList<Node>(); 
    nodeList.add(startNode); //"Node startNode" contains the root node of the tree that will be produced 
    Node currentNode = null; 
    while (1 == 1) {    
     //THIS SECTION FINDS THE LEAF NODE WITH THE LEAST f(n) 
     currentNode = null; 
     for (Node pickNode : nodeList) { 
      if (pickNode.isLeaf == true) { 
       if (currentNode == null) 
        currentNode = pickNode; 

       else if (pickNode.fn < currentNode.fn){ 
        currentNode = pickNode; 
       } 
      } 
     } 
    /*-----------------------------------------------------------*/ 
     //BREAK THE LOOP WHEN THE SOLUTION IS FOUND 
     if (Arrays.deepEquals(currentNode.state, goalState)) 
      break; 
    /*-----------------------------------------------------------*/  
     else { 
      int xcheck = currentNode.zeroX; 
      int ycheck = currentNode.zeroY; 
      int switcher; 
      int approve = 1; 
     /*-----------------------------------------------------------*/ 
      //THE FOLLOWING LINES DETERMINES WHICH CHILDREN CAN BE PRODUCED BY A NODE 
      if ((ycheck - 1) >= 0) { 
       int subState[][] = new int [3][]; 
       subState[0] = currentNode.state[0].clone(); 
       subState[1] = currentNode.state[1].clone(); 
       subState[2] = currentNode.state[2].clone(); 
       switcher = subState[ycheck-1][xcheck]; 
       subState[ycheck-1][xcheck] = 0; 
       subState[ycheck][xcheck] = switcher; 

       Node checkerNode = new Node(); 
       checkerNode = currentNode; 
       while (checkerNode != null) { 
        if (Arrays.deepEquals(subState, checkerNode.state)) { 
         approve = 0; 
         break; 
        } 
        checkerNode = checkerNode.parentNode; 
       } 

       if (approve != 0) { 
        Node childNode = new Node(); 
        childNode.state = subState; 
        childNode.totalPath = currentNode.totalPath + "*" + "up"; 
        childNode.gn = currentNode.gn + 1; 
        childNode.hn = computeHn(childNode.state, goalState); 
        childNode.fn = childNode.gn + childNode.hn; 
        childNode.isLeaf = true; 
        childNode.parentNode = currentNode; 
        childNode.zeroX = xcheck; 
        childNode.zeroY = ycheck-1; 
        nodeList.add(childNode); 
       } 
      } 
      approve = 1; 
     /*-----------------------------------------------------------*/ 
      if ((ycheck + 1) <= 2) { 
       //same logic with: if (ycheck-1 >= 0) 
      } 
      approve = 1; 
     /*-----------------------------------------------------------*/ 
      if ((xcheck + 1) <= 2) { 
       //same logic with: if (ycheck-1 >= 0) 
      } 
      approve = 1; 
     /*-----------------------------------------------------------*/ 
      if ((xcheck - 1) >= 0) { 
       //same logic with: if (ycheck-1 >= 0) 
      } 
      approve = 1; 
     } 
     currentNode.isLeaf = false; 
    } 

Вот функция, которая вычисляет для моей эвристики (количество неуместных плиток вместо Манхэттенского расстояния):

public static int computeHn (int checkStateH[][], int goalStateH[][]) { 
    int total = 0; 
    int rowC = 0; 
    int columnC = 0; 

     rowC = 0; 
     while (rowC < 3) { 
      columnC = 0; 
      while (columnC < 3) { 
       if (goalStateH[rowC][columnC] != checkStateH[rowC][columnC]) { 
        total++; 
       } 
       columnC++; 
      } 

      rowC++; 
     } 

    return total; 
} 

и вот мой Класс Узел:

public class Node { 
    int state[][]; //contains the matrix configuration of the node 
    String totalPath; //contains the path on how to get to this node from the root node 
    int gn; //contains the number of moves made to get to this node from the root node 
    int hn; //contains the heuristic (number of misplaced tiles per node) 
    int fn; // fn = gn + hn 
    boolean isLeaf; //states whether a node is a leaf or not. used so that I can know whether a node could still be expanded or not 
    Node parentNode; //points to the node's parent node 
    int zeroX; //the x position of the zero tile 
    int zeroY; //the y position of the zero tile 
} 

Это данная матрица, или матрица "начальное состояние" (на худшем случае, это может дать ответ на 31 ходов на минимум):

... и он должен достичь этого конечного состояния:

... опять же, когда я использую "Манхеттен расстояние", как моя функция эвристического, мой код работает, но это занимает 30 secs, чтобы дать ответ для такого ввода ... но когда я использую «количество неуместных плит» в качестве функции эвристики, оно не дает решения даже через 15 минут, но дает ответ, когда я использую эту матрицу:

• 3 0 4 // эта матрица достижима из ранее упомянутого состояния матрицы запуска

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

Answer 1

Имеет смысл, что расстояние Манхэттена будет быстрее, поскольку это лучше эвристический. 30 секунд - это немного долго ждать решения, особенно для C++, но это не совсем смешно. > 15 минут, хотя, даже для не большой эвристики.

Если я правильно интерпретирую ваш код, цикл checkerNode проверяет, присутствует ли это состояние в пути, который вы просматриваете, пройдя весь путь. Это довольно неэффективно (O (log (n) ish), я думаю). Если вы вместо этого поддерживаете словарь состояний, которые вы уже расширили, вы можете получить это до постоянного времени.

Могут быть и другие тонкие неэффективности, но я подозреваю, что это значительно ускорит ваш код.

EDIT объяснить словари:

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

Для большинства структур данных, если вы хотите найти элемент с заданным значением, вам необходимо сравнить это значение с каждым элементом, уже сохраненным в структуре (например, как вы сравниваете checkerNode со всеми предшественниками) , Проблема в том, что, поскольку вы сохраняете все больше и больше вещей в своей структуре данных, этот процесс занимает больше времени и дольше. Это не относится к словарю, потому что словарь использует что-то, называемое хеш-таблицей, чтобы сразу перейти в место, где данный элемент будет сохранен, если он существует. Тогда, если элемент есть, вы знаете, что он находится в структуре данных, и если вы не знаете, что это не так.

Словари обычно используются для сопоставления заданного ключа со связанным значением, но здесь мы действительно не заботимся об этой функциональности. Мы просто хотим знать, находится ли данный ключ в словаре, поэтому мы можем установить значение в любое нужное (обычно я просто сохраняю логическое значение «True» или указатель на узел, если вам нужно будет найти его снова). В C++ встроенный класс словаря - std::map.

Чтобы его использовать в своем коде вы можете сделать что-то примерно так:

Первого, инициализировать объект

std::map<char,int> already_explored; 

карты не Execute начала программы до того момента, когда только было присвоено значение to currentNode. Теперь, когда мы исследуем currentNode, мы добавляем его в словарь. Состояние - это ключ, значение «Истина» - это значение.

already_explored[currentNode.state] = True; 

Продолжить выполнение программы до тех пор, пока вы обнаружили следующее состояние являются хотите знать, если это уже было видно. Теперь мы можем сделать просмотровые в словаре:

if (already_explored.count(subState) > 0){ 
    approve = 0; 
} 

Если вы делаете вещи в таком порядке, вы даже не придется беспокоиться о проверке п (п) значения других узлов с одинаковыми состояниями. Первый, который достигает A *, гарантированно будет самым быстрым способом достичь этого состояния. И никогда не будет никакой пользы для перехода на более длинный путь в одно и то же состояние.

Answer 2

После взглянуть на ваш код, я могу указать две вещи, которые могли бы улучшить много эффективность кода:

1. A * хранит упорядоченный список с узлами будет расширен (ОТКРЫТЬ список), который сортируется по возрастанию f(n). В вашем коде я понимаю, что вы выбираете узел с самым низким f(n) в первом цикле, обходя дерево всех сгенерированных состояний.Это очень неэффективно, потому что дерево поиска растет с каждой итерацией алгоритма, в то время как вам нужно только перебирать листья этого дерева (которые являются сгенерированными как преемники других состояний, но не расширены). Вам лучше хранить узлы, которые будут расширены A * в PriorityQueue. Первым элементом очереди является тот, у которого самый низкий f(n), поэтому вам не нужно проходить все дерево поиска на каждой итерации.

2. Как @seaotternerd указывает на его ответ, вам нужно как-то «словарь» с состояниями, уже расширенными алгоритмом. A * хранит в списке OPEN узлы, которые сгенерированы как преемники других (но еще не расширены), а в списке ЗАКРЫТО узлы уже расширены. Это необходимо, чтобы проверить, в случае достижения состояния, которое было создано в предыдущих итерациях, если вы улучшили его значение f(n) или нет. В качестве примера, если вы будете следовать этому implementation of A* сделано в Hipster библиотеки, следующие поля будет использоваться для хранения «словаря» состояний:

   private Map<int[][], Node> open; 
   private Map<int[][], Node> closed; 
   private Queue<Node> queue; 
   

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

   private Node takePromising() { 
       // Poll until a valid state is found 
       Node node = queue.poll(); 
       while (!open.containsKey(node.state())) { 
        node = queue.poll(); 
       } 
       return node; 
   } 
   

Редакции: Это позволит избежать вам итерации по дереву поиска, как вы делаете сейчас, в начале вашего цикла, улучшение т он выбирает наиболее перспективный узел до O(n). С помощью словаря код, который вы выполняете в checkerNode, чтобы избежать цикла «предок-преемник-предок», больше не понадобится. И учтите, что без правильной реализации списков OPEN и CLOSED ваш поиск может входить в бесконечные циклы. Чтобы закончить, вам может показаться интересным проверить full example of the 8-puzzle problem solved with A*, который входит в комплект поставки Hipster library.

Я надеюсь, что мой ответ помогает,