Обход дерева BFS - PullRequest
       15

Обход дерева BFS

0 голосов
/ 18 ноября 2018

Я пытаюсь написать алгоритм поиска в ширину в Javascript, который также включает в себя количество повторений каждого узла.Например, в меню создания видеоигры я хочу создать нужный элемент A, для которого требуются элементы B x20, C x30 и D x100.Пункты B, C и D, в свою очередь, требуют, чтобы другие предметы превышали произвольную сумму.Я хочу знать, сколько предметов на самом нижнем уровне дерева мне понадобится для создания предмета А. Попробуйте, как я мог бы, я не могу найти решение для этого.По сути, я делаю BFS материалов и BFS материалов "параллельно".Предполагаемый вывод - это двумерный массив (2 строки, x столбцов) с (уникальными) именами материалов в первой строке и связанными количествами материалов во второй строке.Этот текущий код дает мне пустой результат.Я написал 10-20 вариантов этого к настоящему времени в течение 8 недель после поиска StackOverflow, https://www.w3schools.com/jsref/jsref_obj_array.asp, https://www.geeksforgeeks.org/java-util-hashmap-in-java/, и https://developer.mozilla.org/en-US/docs/Web/JavaScript. Не повезло, или я просто такплохо знакомый с JS, что я не вижу ответа, который прямо передо мной.Все функции, которые я вызвал из этой функции, работают отлично (я тестировал их отдельно).

function traversebreadth(key, keyamt, leaveschecked, repschecked, leavesqueue, repsqueue, roots, leaves, leafreps) { //initial parameters: string, number, [], [], string (same as key), number (same as keyamt), Array (column vector), 2D array (each row is a material list corresponding to the same row in "roots"), 2D array (each row is a material amount list corresponding to the same row in both "roots" and "leaves")

  var keyleaves = getleaves(key, roots, leaves);    //gets the leaves(/children) of the current node
  var keyreps = getleafreps(key, roots, leafreps);  //gets the children of the current node's repetitions (or "amounts")
  keyreps = scalarmultiply(keyamt, keyreps);        //multiplies the current repetitions by the number of repetitions of the parent node

  leaveschecked += key;   //push the key to the queue of checked nodes
  repschecked += keyamt;  //push the keyamt to the queue of checked node reps

  if(!Array.isArray(leavesqueue)){  //ensure leavesqueue is an Object (Array), not a Number
        var lq = [];
        lq.push(leavesqueue);
        leavesqueue = lq;
  }
  if(!Array.isArray(repsqueue)){    //ensure repsqueue is an Object (Array), not a Number
        var rq = [];
        rq.push(repsqueue);
        repsqueue = rq;
  }
  if(isemptyarray(leavesqueue,"row")){      //if leavesqueue is empty, then there are no more leaves to check and this recursive function can return the result
        return ArrayLib.transpose(leaveschecked).concat(ArrayLib.transpose(repschecked));  //return all of the unique nodes needed to craft item A, and the total amount of each node
  }else{                                    //else, repeat this function
        var newleavesqueue = queueleaves(keyleaves, leavesqueue); //queueleaves() appends keyleaves to leavesqueue and removes the first element of leavesqueue, then returns leavesqueue
        var newrepsqueue = queueleafreps(keyreps,repsqueue); //queueleafreps() does the same thing as queueleaves() using keyreps and repsqueue
        var newkey = ArrayLib.transpose(newleavesqueue).shift();   //gets the new node to use as current key
        var newkeyamt = ArrayLib.transpose(newrepsqueue).shift();  //gets the reps of this new current key
        traversebreadth(newkey, newkeyamt, leaveschecked, repschecked, newleavesqueue, newrepsqueue, roots, leaves, leafreps);  //repeat this function with the new parameters
}
...