Seiten

  • Startseite
  • Impressum
  • Inhalt
  • MINT
  • Sprache
  • Soziales
  • Geist
  • Kunst
  • Gemischtes
  • Gedichte

Freitag, 7. Februar 2014

Backtracking

A normal backtracking algorithm always makes the following steps:
  1. proofing if work list is empty
  2. saving current node
  3. proofing if termination condition is true
  4. determining all reachable nodes from current node
  5. doing the following for every reachable node
  6. proofing if node is not tagged
  7. adding node to work list
  8. recursing
  9. removing node from work list

In Java code it looks like this:

private static void backtracking(List<Node> workList){
    Node current;
    if(workList.isEmpty()){
        current = null;
    }
    else {
        current = workList.get(workList.size()-1);
    }
    
if(terminationCondition){
        return;
    }
    List<Node> reachable = getReachableNodes(current);
    for(int i = 0; i < reachable.size(); i++){
        if(!isTagged(reachable.get(i))){
            workList.add(reachable.get(i));
            backtracking(workList);
            workList.remove(reachable.get(i));
        }
    }
}

There're many different uses for backtracking. For example finding a path between two nodes:

private static List<Node> findPath(List<Node> workList, Node start, Node target){
    Node current;
    if(workList.isEmpty()){
        workList.add(start);

        current = start;
    }
    else {
        current = workList.get(workList.size()-1);
    }
    if(current == target){
        return workList;
    }
    List<Node> reachable = getReachableNodes(current);
    for(int i = 0; i < reachable.size(); i++){
        if(!workList.contains(reachable.get(i))){
            workList.add(reachable.get(i));
            backtracking(workList,
start, target);
            workList.remove(reachable.get(i));
        }
    }
}

I certainly know that a lot of better ways to find a path exist.

Keine Kommentare:

Kommentar veröffentlichen