UriSteiff

greedy

May 15th, 2021
514
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package il.ac.tau.cs.sw1.ex7;
  2.  
  3. import java.util.*;
  4.  
  5.  
  6. public interface Greedy<T>{
  7.  
  8.     /**
  9.      * A selection function, which chooses the best candidate to be added to the solution
  10.      */
  11.     Iterator<T> selection();
  12.  
  13.     /**
  14.      * A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
  15.      */
  16.     boolean feasibility(List<T> lst, T element);
  17.  
  18.     /**
  19.      * An assign function, which assigns a value to a solution, or a partial solution
  20.      */
  21.     void assign(List<T> lst, T element);
  22.  
  23.     /**
  24.      * A solution function, which will indicate when we have discovered a complete solution
  25.      */
  26.     boolean solution(List<T> lst);
  27.  
  28.     /**
  29.      * The Greedy Algorithm
  30.      */
  31.     default List<T> greedyAlgorithm(){
  32.         ArrayList<T> candidates_list = new ArrayList<T>(); // empty list
  33.         Iterator<T> selection = selection();
  34.         T element;
  35.         while (selection.hasNext()) { // selection has more elements
  36.             element = selection.next();
  37.             if (feasibility(candidates_list, element)) {
  38.                 assign(candidates_list, element);
  39.             }
  40.             if (solution(candidates_list)) {
  41.                 return candidates_list;
  42.             }
  43.            
  44.         }
  45.         return null;
  46.        
  47.     }
  48. }
  49.  
RAW Paste Data