Site hosted by Angelfire.com: Build your free website today!

                    // The implementation for backtracking and branch-and bound algorithm

 

//The language used: Java, jdk 1.2.2

// The machine used: the machine in the arts 144 lab

// memory problem: there does not exist memory problems when running this program.

 

//The code:

 

import java.util.*;

import java.io.*;

import java.util.Date;

 

/* This class reads assignments for the driver from a text file, divides each an assignment into ‘North part’ and ‘South part’ by the direction of each stop, and stores them separately by each stop’s distance increasing order. And then it determines the best route of each assignment by using two different ways, backtracking and branch-and bound, and writes their results and their time spend for finding the best route into different text files. */

 

class Assign3 implements Cloneable

{

    long startTime, endTime;

    Date dateS, dateE;

    PriorityTree priorityTree = new PriorityTree();

    int upBound = 99999;

    Vector resultB;

 

    public static void main(String arg[])

    {

        Assign3 ass = new Assign3();

        ass.find_route();

    }  // the end of main

 

/* The method find_route opens data.txt file and creates result files,  managers the program to find the best route of each assignment after having read the data,  and then writes each result to corresponding result file. Finally all files have been closed. */

 

    private void find_route()

    {

        int counter = 0;

        long timing;

        String label1 = "\nData Set ";

        String label2 = "\nbacktracking\tbranch-and-bound\n";

 

        try {

        FileReader fr = new FileReader("data.txt");

        BufferedReader br = new BufferedReader(fr);

        FileWriter f1 = new FileWriter("q1Result.txt");

        FileWriter f2 = new FileWriter("q2Result.txt");

        FileWriter f3 = new FileWriter("timeTable.txt");

 

        String s;

        StringTokenizer st;

        Node node;

        String dirc;

        String routes; // contain the result of routes

        int dist;

        int kids, totalKids = 0;

        Vector vec = new Vector();

        Vector vec1 = new Vector(), vec1B;

        Vector vec2 = new Vector(), vec2B;

 

        while((s = br.readLine()) != null)

        {

            if ((s.substring(0,8)).equals("Data Set"))

            {

                f3.write(label1 + counter++ + label2);

                continue;

            }

            st = new StringTokenizer(s, " ");

 

            while(st.hasMoreTokens())

            {

                dirc = st.nextToken();

                if ( dirc.equals("S") )

                {

                    dist = Integer.parseInt(st.nextToken());

                    kids = Integer.parseInt(st.nextToken());

                    node = new Node(dirc, dist, kids);

                    vec1.addElement(node);

                    totalKids += kids;

                }

                else if ( dirc.equals("N") )

                {

                    dist = Integer.parseInt(st.nextToken());

                    kids = Integer.parseInt(st.nextToken());

                    node = new Node(dirc, dist, kids);

                    vec2.addElement(node);

                    totalKids += kids;

                } else {

                    System.out.println("oops...");

                    return;

                }

 

            } // inner while, token each set of data

 

            // after reading a set of date, sort 2 queues

            vec1 = sortQueue(vec1);

            vec2 = sortQueue(vec2);

            vec1B = (Vector)vec1.clone();

            vec2B = (Vector)vec2.clone();

 

            // find the best route by using backtrack

            vec = new Vector();

            vec.addElement(new Integer(0));

            dateS = new Date();

            startTime = dateS.getTime();

            vec = backtrack(vec1, vec2, totalKids, new Node(), vec);

            dateE = new Date();

            endTime = dateE.getTime();

 

            // print result

            routes = getResult(vec) + "\n";

            System.out.println("\n" + routes);

            f1.write(routes);

 

            timing = endTime-startTime;

            f3.write(timing+"\t\t\t");

            System.out.println("\n**** Timing: " + timing + " ****\n");

            resultB = setUpBound(vec1B,vec2B,totalKids);

 

            // find the best route by using branchBound

            vec = new Vector();

            vec.addElement(new Integer(0));

            int pred = 0;

            dateS = new Date();

            startTime = dateS.getTime();

            branchBound(new State(pred,vec1B, vec2B, totalKids, new Node(), vec));

            dateE = new Date();

            endTime = dateE.getTime();

 

            // print result

            routes = getResult(resultB) + "\n";

            System.out.println("\n" + routes);

            f2.write(routes);

 

            timing = endTime-startTime;

            f3.write(timing + "\n");

            System.out.println("\n**** Timing: " + timing + " ****\n");

 

            System.out.println("\n******************************************\n");

 

            // reset for next set of data

            vec1 = new Vector();

            vec2 = new Vector();

            totalKids = 0;

        } // outer while, read line

 

        fr.close();

        f1.close();

        f2.close();

        f3.close();

        } catch(Exception e) {System.out.println(e);}

 

    } // end of find_route

 

/* The method getResult gets the result from the vector and appends each item in the vector into a string. */

 

    private String getResult(Vector result)

    {

        Node st;

        String s = "";

        int total = 0;

        int size = result.size();

        if (size > 0)

            total = ((Integer)result.remove(0)).intValue();

        for (int i = 0; i < size - 1; i++)

        {

            st = (Node)result.remove(0);

            s = s + st.direction + " " + st.dist + ", ";

        } // end of for

 

        s = s + "total kid-kilo = " + total;

        return s;

 

    } // end of getResult

 

/* The method setUpBound initializes upbound, the route is that the driver goes south first, and goes north after all south stops having been endured. */

 

    private Vector setUpBound(Vector v1, Vector v2, int kids)

    {

                Vector iniResult = new Vector();

        int total = 0, lastDist = 0, realDist;

        int left = kids;

        Node temp;

                                iniResult.addElement(new Integer(0));

        for(int i = 0; i < v1.size(); i++)

        {

            temp = (Node)v1.elementAt(i);

            realDist = temp.dist - lastDist;

            total += realDist*left;

            left -= temp.kids;

            lastDist = temp.dist;

            iniResult.addElement(temp);

        }

        lastDist = -lastDist;

        for(int i = 0; i < v2.size(); i++)

        {

            temp = (Node)v2.elementAt(i);

            realDist = temp.dist - lastDist;

            total += realDist*left;

            left -= temp.kids;

            lastDist = temp.dist;

            iniResult.addElement(temp);

        }

 

        upBound = total;

        iniResult.setElementAt(new Integer(upBound),0);

        return  iniResult;

    } // end of set upper bound

 

/* The method sortQueue sorts by using selection sort. */

 

    private Vector sortQueue(Vector org) {

        int small, big;

        Node smallest, temp;

        int size = org.size();

 

        for (int i = 0; i < size; i++)

        {

            smallest = (Node)org.elementAt(i);

            small = smallest.dist;

 

            for ( int j = i+1; j < size; j++)

            {

                big = ((Node)org.elementAt(j)).dist;

                if (small > big) // switch

                {

                    smallest = (Node)org.elementAt(j);

                    small = smallest.dist;

 

                    temp = (Node)org.elementAt(i);

                    org.setElementAt(smallest, i);

                    org.setElementAt(temp, j);

                }

            } // inner for

        } // outer for

 

        return org;

    } // end of sort

 

/* The method weight calculates the number of kid-kilometers from cur node to next cur. */

 

    public int weight(Node cur, Node next, int nkids)

    {

        if (cur.direction.equals(next.direction))

            return Math.abs((cur.dist-next.dist)*nkids);

        else

            return (cur.dist+next.dist)*nkids;

    }

 

/* The method backtrack finds the best route for an assignment by using backtrack. */

 

    public Vector backtrack(Vector southQ, Vector northQ, int nkids, Node last,Vector route)

    {

        int curTotal;

        Node cur;

        Vector temp;

 

        nkids = nkids - last.kids;

        if (southQ.isEmpty() && northQ.isEmpty())

            return route;

        else if (southQ.isEmpty() && !northQ.isEmpty())

        {

            cur = (Node)northQ.remove(0);

            route.addElement(cur);

 

            // re-set total kid-kilometers

            curTotal = weight(last,cur,nkids) + ((Integer)route.elementAt(0)).intValue();

            route.setElementAt(new Integer(curTotal),0);

            temp = backtrack(southQ,northQ,nkids,cur,route);

            return temp;

}

        else if (!southQ.isEmpty() && northQ.isEmpty())

        {

            cur = (Node)southQ.remove(0);

            route.addElement(cur);

 

            // re-set total kid-kilometers

            curTotal = weight(last,cur,nkids) + ((Integer)route.elementAt(0)).intValue();

            route.setElementAt(new Integer(curTotal),0);

            temp = backtrack(southQ,northQ,nkids,cur,route);

            return temp;

}

        else

        {       //southQ and northQ are both not empty

            Vector sTemp = (Vector)southQ.clone();

            Vector nTemp = (Vector)northQ.clone();

            Vector southResult, northResult;

            int southTot, northTot;

 

            Node cur1 = (Node) sTemp.elementAt(0);

            Node cur2 = (Node) nTemp.elementAt(0);

 

            // south branch

            temp = (Vector)route.clone();

            sTemp.remove(0);

            temp.addElement(cur1);

            southTot = weight(last,cur1,nkids) + ((Integer)route.elementAt(0)).intValue();

            temp.setElementAt(new Integer(southTot),0);

            southResult = backtrack(sTemp,northQ,nkids,cur1,temp);

 

            // north branch

            temp = (Vector)route.clone(); // reset temp

            nTemp.remove(0);

            temp.addElement(cur2);

            northTot = weight(last,cur2,nkids) + ((Integer)route.elementAt(0)).intValue();

            temp.setElementAt(new Integer(northTot),0);

            northResult = backtrack(southQ, nTemp,nkids, cur2, temp);

 

            int so = ((Integer)southResult.elementAt(0)).intValue();

            int no = ((Integer)northResult.elementAt(0)).intValue();

            // compare north branch and south branch

            if (so <= no)

                return southResult;

            else

                return northResult;

        } // end of both not empty

    } // end of backtrack

 

/* The method predict calculates the lower bound when the driver goes curT from last.*/

 

    private int predict(Vector vs, Vector vn, int kn, Node last, int curT)

    {

        int pred = 0, diff = 0;

        Node temp;

 

        if(last.direction.equals("S"))

            diff = last.dist;

        else

            diff = -last.dist;

 

        for(int i=0; i<vs.size(); i++)

        {

            temp = (Node)vs.elementAt(i);

            pred += temp.kids*(temp.dist-diff);

        }

        for(int i=0; i<vn.size(); i++)

        {

            temp = (Node)vn.elementAt(i);

            pred += temp.kids*(temp.dist+diff);

        }

 

        return curT + pred;

    } // end of predict

 

/* The method backtrack finds the best route for an assignment by using branchBound.  */

 

    public void branchBound(State state)

    {

        int curTotal, tempHigh;

        Node cur;

        Vector temp;

        int sPred, nPred;

 

        priorityTree.enqueue(state);

 

        while (! priorityTree.isEmpty() )

        { 

                State curState = (State)priorityTree.dequeue();   

                int nkids = curState.nkids - curState.last.kids;

 

                if (curState.southQ.isEmpty() && curState.northQ.isEmpty())

                {

                     temp = (Vector)((curState.route).clone());

                   tempHigh = ((Integer)temp.elementAt(0)).intValue();

                   if (tempHigh < upBound)

                   {

                                upBound = tempHigh;

                                resultB = (Vector)((curState.route).clone());

                                priorityTree.delete(upBound);

                    }

                }

                else if (curState.southQ.isEmpty() && ! curState.northQ.isEmpty())

                {

                     Vector curNorthQ = (Vector)curState.northQ.clone();

                    cur = (Node)curNorthQ.remove(0);

                    temp = (Vector)curState.route.clone();

                                   

                    // update total kid-kilometers

                    curTotal = weight(curState.last,cur,nkids) + ((Integer)temp.elementAt(0)).intValue();

                                   

                    nPred = predict(curState.southQ,curNorthQ,curState.nkids,cur,curTotal);

                    if (nPred < upBound)

                     {

                                temp.addElement(cur);

                                temp.setElementAt(new Integer(curTotal),0);

                                priorityTree.enqueue(new State(nPred,curState.southQ,curNorthQ,nkids,cur,temp));   

                     }

                 }

                else if (! curState.southQ.isEmpty() && curState.northQ.isEmpty())

               {

                      Vector curSouthQ = (Vector)curState.southQ.clone();

                     cur = (Node)curSouthQ.remove(0);

                     temp = (Vector)curState.route.clone();

                                               

                      // update total kid-kilometers

                    curTotal = weight(curState.last,cur,nkids) + ((Integer)temp.elementAt(0)).intValue();

 

                   sPred = predict(curSouthQ,curState.northQ,curState.nkids,cur,curTotal);

                  if (sPred < upBound)    

                  {

                temp.addElement(cur);

                temp.setElementAt(new Integer(curTotal),0);

                                priorityTree.enqueue(new State(nPred,curSouthQ,curState.northQ,nkids,cur,temp));   

                    }

       

                    }      

        else

        {       //southQ and northQ are both not empty

                Vector sTemp = (Vector)curState.southQ.clone();

                Vector nTemp = (Vector)curState.northQ.clone();

                Vector temp1,temp2;

                int southTot, northTot, so = 0, no = 0;

 

                Node cur1 = (Node) sTemp.remove(0);

                Node cur2 = (Node) nTemp.remove(0);

 

                // south branch prediction  

    

               temp1 = (Vector)curState.route.clone();

               southTot = weight(curState.last,cur1,nkids) + ((Integer)temp1.elementAt(0)).intValue();

               temp1.addElement(cur1);

               temp1.setElementAt(new Integer(southTot),0);

               sPred = predict(sTemp,curState.northQ,nkids,cur1,southTot);

                 if (sPred <= upBound)

               {      priorityTree.enqueue(new State(sPred,sTemp,curState.northQ,nkids,cur1,temp1));  }

 

               // north branch prediction

 

               temp2 = (Vector)curState.route.clone(); // reset temp

              northTot = weight(curState.last,cur2,nkids) + ((Integer)temp2.elementAt(0)).intValue();

              temp2.addElement(cur2);

              temp2.setElementAt(new Integer(northTot),0);  

              nPred = predict(curState.southQ,nTemp,nkids,cur2,northTot);

              if (nPred <= upBound)

             {      priorityTree.enqueue(new State(nPred,curState.southQ,nTemp,nkids,cur2,temp2));   }

          } // end of both not empty     

       } // end of the while loop

} // end of branch-and-bound

 

/* The method clone creates a copy of this object.  */

 

    public Object clone()

    {

        try{

        return super.clone();

        } catch(CloneNotSupportedException e) {

        System.out.println("Cloning not allowed.");

        return this;

        }

    }

 

} // end of Assign3 class

/* The class Node stores the information of the each stop. */

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

class Node

  {

        String direction;

        int dist;

        int kids;

 

    public Node()

        {

           direction = "S";

           dist = 0;

           kids =0;

        }

 

    public Node(String direct,int distance, int nkids)

        {

           direction = direct;

           dist = distance;

           kids =nkids;

        }

  }

 

/* The class State stores the information of each state that the driver drives to the last node from school. */

class State implements Comparable

{

    int       lowBound,  nkids;

    Vector southQ,northQ,route;

    Node last;

 

    public State(int l, Vector s, Vector n, int k, Node la, Vector c)

    {

                lowBound = l;

                southQ = s;

                northQ = n;

                route = c;

                nkids = k;

                last = la;

    }

 

    public int compareTo (Object o)

    {

                State compareState = (State) o;

                if (lowBound < compareState.lowBound)

                    return -1;

                else if (lowBound > compareState.lowBound)

                    return 1;

                else

                    return 0;

    }

 

    public String toString()

    {

                return lowBound + " ";

    }

 

}//end of State class

/*This PriorityTree is a binary tree, and each node stores a state.  The states can be insert(enqueue), delete(dequeue) and update(delete).  Therefore states in the tree are ordered by their lower bound.  */

 

class PriorityTree

{

  private PriorityTree left, right;

  private State root;

 

  public PriorityTree() {

  }

 

  public boolean isEmpty() {

    return (root == null);

  }

 

  public void enqueue (Comparable i) {

    int comparisonValue;

 

    if (isEmpty()) {

      root = (State)i;

      left = new PriorityTree();

      right = new PriorityTree();

    } else {

      comparisonValue = i.compareTo(root);

      if (comparisonValue <= 0) {

                left.enqueue(i);

      } else {

                right.enqueue(i);

      }

    }

  }

 

  public State dequeue()

  {

    State temp = root;

    if (left.isEmpty())

    {

                deleteRoot();

                return temp;

    }

    else

                return left.dequeue();

  }

 

  public State more (int upper)

  {

    if (isEmpty())

      return null;

   

    if (root.lowBound >= upper)

      return root;

    else

      return right.more(upper);

  }

 

  public void delete (int upBound)

  {

    State temp;

    while ((temp = more(upBound)) != null)

      getItemSubtree(temp).deleteRoot();

  }

 

  private PriorityTree getItemSubtree (Comparable item) {

    // this method assumes that the item is in the tree

    int comparisonValue;

 

    comparisonValue = item.compareTo(root);

 

    if (comparisonValue == 0) {

      return this;

    } else if (comparisonValue < 0) {

      return left.getItemSubtree(item);

    } else {

      return right.getItemSubtree(item);

    }

  }

 

  private void deleteRoot() {

    PriorityTree predecessor;

 

    if (left.isEmpty() && right.isEmpty()) {

      // case 1: no subtrees, so delete by making this node empty

      left = null;

      right = null;

      root = null;

    }

    else if (!left.isEmpty() && right.isEmpty()) {

      // case 2.1: only one subtree, so replace root with subtree

      replaceRoot(left);

    }

    else if (left.isEmpty() && !right.isEmpty()) {

      // case 2.2: only one subtree, so replace root with subtree

      replaceRoot(right);

    }

    else if (!left.isEmpty() && !right.isEmpty()) {

      // case 3: both subtrees exist, so replace root with inorder

      // predecessor, then delete inorder predecessor

 

      predecessor = getPredecessorSubtree();

      root = predecessor.root;

      predecessor.deleteRoot();

    }

  }

 

  private void replaceRoot(PriorityTree subtree) {

    root = subtree.root;

    left = subtree.left;

    right = subtree.right;

  }

 

  private PriorityTree getPredecessorSubtree() {

    PriorityTree predecessor;

 

    predecessor = left;

    while (!(predecessor.right.isEmpty())) {

      predecessor = predecessor.right;

    }

    return predecessor;

  }

 

  public String toString() {

    if (isEmpty()) {

      return "";

    } else {

      return left.toString() + " " + root.toString()

                + " " + right.toString();

    }

  }

 

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                               

 

 

 

 

 

 

 

 

 

// The input data

Data Set 0

N 2 2 N 4 2 N 6 2

S 2 2 S 4 2 S 6 2

N 2 10 S 2 5 N 10 1

N 10 1 N 2 20 S 5 10 S 3 10

S 14 5 N 20 12 S 10 8 S 5 2 N 25 4 N 40 29

Data Set 1

N 14 5 S 20 12 N 10 8 N 5 2 S 25 4 S 40 29

S 7 3 N 15 5 N 16 12 S 12 2 N 20 6 N 27 9 N 30 1 S 4 11 N 34 4 S 25 2

S 43 2 S 20 4 S 14 1 S 6 3 N 10 1 N 25 2 N 38 3 N 44 5 N 50 1 N 60 6 N 70 1 N 78 4 N 84 1 N 96 2

S 43 2 S 26 2 S 20 4 S 14 1 S 6 3 N 6 2 N 10 1 N 14 5 N 25 2 N 33 2 N 38 3 N 44 5 N 50 1 N 60 6 N 70 1 N 78 4 N 84 1 N 96 2

N 5 4 S 10 2 N 6 1 N 14 3 S 17 2 N 10 4 S 9 2 N 8 3 S 15 2 S 16 3 S 25 2 N 60 2 S 18 3 S 23 3 S 24 1 N 9 2 S 21 2 N 24 4 S 40 2 N 22 2 S 8 2 S 6 1

Data Set 2

S 13 9 S 15 11 S 24 12 S 31 4 N 40 5 S 8 15

N 55 6 N 8 4 N 31 10 S 60 5 S 37 6 N 23 1 N 42 3 N 50 9 S 20 3 S 14 7

S 65 2 S 58 8 S 45 4 S 39 3 S 31 1 S 21 2 S 16 2 S 11 3 S 4 5 N 12 1 N 18 6 N 26 2 N 36 4 N 48 3

S 65 2 S 58 8 S 50 2 S 45 4 S 39 3 S 31 1 S 29 5 S 21 2 S 16 2 S 11 3 S 4 5 N 12 1 N 18 6 N 26 2 N 31 1 N 36 4 N 42 1 N 48 3

S 43 2 S 31 1 S 26 2 S 20 4 S 14 1 S 6 3 N 6 2 N 10 1 N 14 5 N 19 1 N 25 2 N 33 2 N 38 3 N 44 5 N 50 1 N 60 6 N 65 2 N 70 1 N 78 4 N 84 1 N 89 3 N 96 2

Data Set 3

N 5 2 N 14 8 N 10 3 N 60 6 S 25 25 N 8 7

S 50 6 S 46 9 S 40 3 S 31 10 S 20 2 S 14 4 S 6 7 N 15 3 N 21 6 N 32 5

N 22 5 N 14 10 S 8 2 S 65 4 S 23 5 S 15 1 N 12 6 N 18 11 S 42 6 S 24 1 S 12 6 S 3 15 S 7 4 S 9 5

N 13 1 N 9 4 N 18 3 S 25 2 N 10 1 N 3 5 N 5 1 S 7 2 S 15 4 S 9 1 N 20 1 N 35 3 N 40 3 S 21 6 S 17 4 S 10 8 N 7 8 N 6 4

S 60 2 S 53 1 S 46 8 S 42 2 S 34 4 S 30 1 S 24 3 S 21 2 S 18 1 S 12 5 S 8 1 S 5 2 N 6 2 N 10 3 N 14 5 N 19 1 N 23 6 N 28 2 N 33 1 N 40 4 N 48 1 N 55 3

Data Set 4

S 40 11 S 7 13 S 15 8 N 20 8 S 32 16 S 24 2

S 14 6 S 8 5 S 5 3 N 6 4 N 10 7 N 13 2 N 16 5 N 21 11 N 28 4 N 34 9

S 60 2 S 53 1 S 46 8 S 34 4 S 24 3 S 21 2 S 18 1 S 5 2 N 6 2 N 19 1 N 28 2 N 33 1 N 48 1 N 55 3

S 60 2 S 53 1 S 46 8 S 34 4 S 30 1 S 24 3 S 21 2 S 18 1 S 8 1 S 5 2 N 6 2 N 14 5 N 19 1 N 23 6 N 28 2 N 33 1 N 48 1 N 55 3

S 85 2 S 76 1 S 70 2 S 62 4 S 54 1 S 50 3 S 43 2 S 36 1 S 30 5 S 21 1 N 15 2 N 30 2 N 40 3 N 49 5 N 60 1 N 70 6 N 78 2 N 82 1 N 90 4 S 7 1 S 14 3 S 7 8

Data Set 5

S 23 9 N 20 14 S 14 13 S 5 10 N 4 8 N 17 5

N 3 10 N 6 2 N 12 11 N 25 6 N 29 3 S 10 5 S 18 10 S 21 6 S 28 3 S 35 4

S 85 2 S 70 2 S 62 4 S 43 2 S 30 5 S 21 1 N 15 2 N 30 2 N 40 3 N 70 6 N 90 4 S 7 1 S 14 3 S 7 8

S 85 2 S 70 2 S 62 4 S 50 3 S 43 2 S 36 1 S 30 5 S 21 1 N 15 2 N 30 2 N 40 3 N 60 1 N 70 6 N 78 2 N 90 4 S 7 1 S 14 3 S 7 8

S 65 2 S 61 1 S 58 8 S 50 2 S 45 4 S 42 1 S 39 3 S 34 2 S 31 1 S 29 5 S 26 1 S 21 2 S 16 2 S 11 3 S 4 5 N 12 1 N 18 6 N 26 2 N 31 1 N 36 4 N 42 1 N 48 3

 

 

 

 

 

 

 

 

 

// the result found by backtracking

N 2, N 4, N 6, total kid-kilo = 24

S 2, S 4, S 6, total kid-kilo = 24

N 2, S 2, N 10, total kid-kilo = 68

N 2, S 3, S 5, N 10, total kid-kilo = 224

N 20, N 25, N 40, S 5, S 10, S 14, total kid-kilo = 2860

S 20, S 25, S 40, N 5, N 10, N 14, total kid-kilo = 2860

S 4, N 15, N 16, N 20, N 27, N 30, N 34, S 7, S 12, S 25, total kid-kilo = 1763

S 6, S 14, S 20, N 10, N 25, N 38, N 44, N 50, N 60, N 70, N 78, N 84, N 96, S 43, total kid-kilo = 3164

S 6, N 6, N 10, N 14, N 25, N 33, N 38, N 44, N 50, N 60, N 70, N 78, N 84, N 96, S 14, S 20, S 26, S 43, total kid-kilo = 4116

N 5, N 6, N 8, N 9, N 10, N 14, N 22, N 24, S 6, S 8, S 9, S 10, S 15, S 16, S 17, S 18, S 21, S 23, S 24, S 25, S 40, N 60, total kid-kilo = 2453

S 8, S 13, S 15, S 24, S 31, N 40, total kid-kilo = 1324

N 8, N 23, N 31, N 42, N 50, N 55, S 14, S 20, S 37, S 60, total kid-kilo = 4261

S 4, S 11, S 16, S 21, S 31, S 39, S 45, S 58, S 65, N 12, N 18, N 26, N 36, N 48, total kid-kilo = 3589

S 4, S 11, S 16, S 21, S 29, S 31, S 39, S 45, S 50, S 58, S 65, N 12, N 18, N 26, N 31, N 36, N 42, N 48, total kid-kilo = 4167

N 6, N 10, N 14, N 19, N 25, N 33, N 38, N 44, N 50, N 60, N 65, N 70, N 78, N 84, N 89, N 96, S 6, S 14, S 20, S 26, S 31, S 43, total kid-kilo = 4803

N 5, N 8, N 10, N 14, S 25, N 60, total kid-kilo = 2361

S 6, S 14, S 20, S 31, S 40, S 46, S 50, N 15, N 21, N 32, total kid-kilo = 3013

S 3, N 12, N 14, N 18, N 22, S 7, S 8, S 9, S 12, S 15, S 23, S 24, S 42, S 65, total kid-kilo = 3284

N 3, N 5, N 6, N 7, N 9, S 7, S 9, S 10, S 15, S 17, S 21, S 25, N 10, N 13, N 18, N 20, N 35, N 40, total kid-kilo = 2167

S 5, S 8, S 12, S 18, S 21, S 24, S 30, S 34, S 42, S 46, N 6, N 10, N 14, N 19, N 23, N 28, N 33, N 40, N 48, N 55, S 53, S 60, total kid-kilo = 4914

S 7, S 15, S 24, S 32, S 40, N 20, total kid-kilo = 2011

N 6, N 10, N 13, N 16, N 21, N 28, N 34, S 5, S 8, S 14, total kid-kilo = 1940

S 5, S 18, S 21, S 24, S 34, S 46, S 53, S 60, N 6, N 19, N 28, N 33, N 48, N 55, total kid-kilo = 2352

N 6, N 14, N 19, N 23, N 28, S 5, S 8, S 18, S 21, S 24, S 30, S 34, S 46, S 53, S 60, N 33, N 48, N 55, total kid-kilo = 3678

S 7, S 7, S 14, S 21, S 30, S 36, S 43, S 50, S 54, S 62, S 70, S 76, S 85, N 15, N 30, N 40, N 49, N 60, N 70, N 78, N 82, N 90, total kid-kilo = 7189

S 5, S 14, S 23, N 4, N 17, N 20, total kid-kilo = 2078

N 3, N 6, N 12, S 10, S 18, S 21, S 28, S 35, N 25, N 29, total kid-kilo = 2509

S 7, S 7, S 14, S 21, S 30, S 43, S 62, S 70, S 85, N 15, N 30, N 40, N 70, N 90, total kid-kilo = 4800

S 7, S 7, S 14, S 21, S 30, S 36, S 43, S 50, S 62, S 70, S 85, N 15, N 30, N 40, N 60, N 70, N 78, N 90, total kid-kilo = 5712

S 4, S 11, S 16, S 21, S 26, S 29, S 31, S 34, S 39, S 42, S 45, S 50, S 58, S 61, S 65, N 12, N 18, N 26, N 31, N 36, N 42, N 48, total kid-kilo = 4364

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                // the result found by branch-and-bound

N 2, N 4, N 6, total kid-kilo = 24

S 2, S 4, S 6, total kid-kilo = 24

N 2, S 2, N 10, total kid-kilo = 68

N 2, S 3, S 5, N 10, total kid-kilo = 224

N 20, N 25, N 40, S 5, S 10, S 14, total kid-kilo = 2860

S 20, S 25, S 40, N 5, N 10, N 14, total kid-kilo = 2860

S 4, N 15, N 16, N 20, N 27, N 30, N 34, S 7, S 12, S 25, total kid-kilo = 1763

S 6, S 14, S 20, N 10, N 25, N 38, N 44, N 50, N 60, N 70, N 78, N 84, N 96, S 43, total kid-kilo = 3164

S 6, N 6, N 10, N 14, N 25, N 33, N 38, N 44, N 50, N 60, N 70, N 78, N 84, N 96, S 14, S 20, S 26, S 43, total kid-kilo = 4116

N 5, N 6, N 8, N 9, N 10, N 14, N 22, N 24, S 6, S 8, S 9, S 10, S 15, S 16, S 17, S 18, S 21, S 23, S 24, S 25, S 40, N 60, total kid-kilo = 2453

S 8, S 13, S 15, S 24, S 31, N 40, total kid-kilo = 1324

N 8, N 23, N 31, N 42, N 50, N 55, S 14, S 20, S 37, S 60, total kid-kilo = 4261

S 4, S 11, S 16, S 21, S 31, S 39, S 45, S 58, S 65, N 12, N 18, N 26, N 36, N 48, total kid-kilo = 3589

S 4, S 11, S 16, S 21, S 29, S 31, S 39, S 45, S 50, S 58, S 65, N 12, N 18, N 26, N 31, N 36, N 42, N 48, total kid-kilo = 4167

N 6, N 10, N 14, N 19, N 25, N 33, N 38, N 44, N 50, N 60, N 65, N 70, N 78, N 84, N 89, N 96, S 6, S 14, S 20, S 26, S 31, S 43, total kid-kilo = 4803

N 5, N 8, N 10, N 14, S 25, N 60, total kid-kilo = 2361

S 6, S 14, S 20, S 31, S 40, S 46, S 50, N 15, N 21, N 32, total kid-kilo = 3013

S 3, N 12, N 14, N 18, N 22, S 7, S 8, S 9, S 12, S 15, S 23, S 24, S 42, S 65, total kid-kilo = 3284

N 3, N 5, N 6, N 7, N 9, S 7, S 9, S 10, S 15, S 17, S 21, S 25, N 10, N 13, N 18, N 20, N 35, N 40, total kid-kilo = 2167

S 5, S 8, S 12, S 18, S 21, S 24, S 30, S 34, S 42, S 46, N 6, N 10, N 14, N 19, N 23, N 28, N 33, N 40, N 48, N 55, S 53, S 60, total kid-kilo = 4914

S 7, S 15, S 24, S 32, S 40, N 20, total kid-kilo = 2011

N 6, N 10, N 13, N 16, N 21, N 28, N 34, S 5, S 8, S 14, total kid-kilo = 1940

S 5, S 18, S 21, S 24, S 34, S 46, S 53, S 60, N 6, N 19, N 28, N 33, N 48, N 55, total kid-kilo = 2352

N 6, N 14, N 19, N 23, N 28, S 5, S 8, S 18, S 21, S 24, S 30, S 34, S 46, S 53, S 60, N 33, N 48, N 55, total kid-kilo = 3678

S 7, S 7, S 14, S 21, S 30, S 36, S 43, S 50, S 54, S 62, S 70, S 76, S 85, N 15, N 30, N 40, N 49, N 60, N 70, N 78, N 82, N 90, total kid-kilo = 7189

S 5, S 14, S 23, N 4, N 17, N 20, total kid-kilo = 2078

N 3, N 6, N 12, S 10, S 18, S 21, S 28, S 35, N 25, N 29, total kid-kilo = 2509

S 7, S 7, S 14, S 21, S 30, S 43, S 62, S 70, S 85, N 15, N 30, N 40, N 70, N 90, total kid-kilo = 4800

S 7, S 7, S 14, S 21, S 30, S 36, S 43, S 50, S 62, S 70, S 85, N 15, N 30, N 40, N 60, N 70, N 78, N 90, total kid-kilo = 5712

S 4, S 11, S 16, S 21, S 26, S 29, S 31, S 34, S 39, S 42, S 45, S 50, S 58, S 61, S 65, N 12, N 18, N 26, N 31, N 36, N 42, N 48, total kid-kilo = 4364

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                // the time spent by two different methods millsecond)

Data Set 0

backtracking         branch-and-bound

10                                            50

0                                              0

0                                              10

30                                            10

20                                            20

 

Data Set 1

backtracking         branch-and-bound

0                                              10

20                                            0

130                                          10

1082                                        10

63532                                      20

 

Data Set 2

backtracking         branch-and-bound

0                                              0

10                                            0

251                                          10

3846                                        0

9975                                        10

 

Data Set 3

backtracking         branch-and-bound

0                                              0

10                                            0

121                                          10

3846                                        0

82058                                      31

 

Data Set 4

backtracking         branch-and-bound

0                                              0

10                                            0

320                                          0

5268                                        10

63451                                      10

 

Data Set 5

backtracking         branch-and-bound

0                                              0

20                                            10

241                                          10

3806                                        50

22272                                      0

 

The time average of data sets 1-5:

                 Stops

         backtracking Average

  branch-and-bound  Average

                    6

                       0

                        2

                   10

                      12

                        2

                   14

                      164.4

                        6

                   18

                      3569.6

                       14

                   20

                      46262.6

                       14.2