randomized_algorithm_problems_aima_style.py

import numpy as np
from search import *

## Flip-flop
class MaximizeAlternations(Problem):
    def __init__(self, initial):
        """initial state is a numpy array with each element representing a bit 0 or 1, 
        goal state is same size as initial state with all bits turned 1"""
        assert sum([n != 0 and n != 1 for n in initial]) == 0, "initial state must contain binary values."
        self.initial = initial
        self.goal = np.ones((len(self.initial)))
        
    def actions(self, state):
        """Return all locations for hamming distance 1"""
        return np.arange(len(state))
    
    def result(self, state, action):
        """Return state bit at location specified by action"""
        state = state.copy()
        state[action] = 1 - state[action] # toggle
        return state
    
    def value(self, state):
        """Return sum of all the elements"""
        return sum([state[i] != state[i+1] for i in range(len(state)-1)]) + 1
    
    def random_states(self, count=10):
        return np.random.randint(0, 2, size=(count, len(self.initial)))
        
## One-Max
class MaximizeOnes(Problem):
    def __init__(self, initial):
        """initial state is a numpy array with each element representing a bit 0 or 1, 
        goal state is same size as initial state with all bits turned 1"""
        assert sum([n != 0 and n != 1 for n in initial]) == 0, "initial state must contain binary values."
        self.initial = initial
        self.goal = np.ones((len(self.initial)))
        
    def actions(self, state):
        """Return all locations for hamming distance 1"""
        return np.arange(len(state))
    
    def result(self, state, action):
        """Return state bit at location specified by action"""
        state = state.copy()
        state[action] = 1 - state[action] # toggle
        return state
    
    def value(self, state):
        """Return sum of all the elements"""
        return sum(state)
    
    def random_states(self, count=10):
        return np.random.randint(0, 2, size=(count, len(self.initial)))
        
## Knapsack
class Knapsack(Problem):
    
    def __init__(self, initial, max_weight=50, max_value=50, knapsack_capacity_percent=0.4):
        """initial state is a numpy array with each element representing a bit 0 or 1, 
        goal state is same size as initial state with all bits turned 1"""
        
        assert initial.dtype == np.int
        assert sum([n != 0 and n != 1 for n in initial]) == 0, "initial state must contain binary values."
        self.initial = initial
        n_items = len(self.initial)
        
        self.values = np.random.randint(0, max_value, n_items)
        self.weights = np.random.randint(0, max_weight, n_items)
        self.all_items_weight = self.weights.sum()
        self.knapsack_capacity = self.weights.sum() * knapsack_capacity_percent
        print("Total Value: {}, Items Weight: {}, Knapsack Capacity: {}".format(sum(self.values), self.all_items_weight, self.knapsack_capacity))
        
    def actions(self, state):
        """Return all locations for hamming distance 1"""
        return np.arange(len(state))
    
    def result(self, state, action):
        """Return state bit at location specified by action"""
        state = state.copy()
        state[action] = 1 - state[action] # toggle
        return state
    
    def get_weight(self, state):
        
        return sum([self.weights[i] if st == 1 else 0 for i, st in enumerate(state)])
    
    def value(self, state):
        """Return sum of all the elements"""
        
        weight, value = 0, 0
        for i, st in enumerate(state):
            if st == 1:
                value += self.values[int(i)]
                weight += self.weights[int(i)]
            
        return value if weight < self.knapsack_capacity else 1e-10*(self.all_items_weight-weight)
    
    def random_states(self, count=10):
        return np.random.randint(0, 2, size=(count, len(self.initial)))
        
## Continuous Peaks 
class ContinuousPeaks(Problem):
    def __init__(self, initial, t):
        """initial state is a numpy array with each element representing a bit 0 or 1, 
        goal state is same size as initial state with all bits turned 1"""
        assert initial.dtype == np.int
        assert sum([n != 0 and n != 1 for n in initial]) == 0, "initial state must contain binary values."
        self.initial = initial
        self.t = t
        
    def actions(self, state):
        """Return all locations for hamming distance 1"""
        return np.arange(len(state))
    
    def result(self, state, action):
        """Return state bit at location specified by action"""
        state = state.copy()
        state[action] = 1 - state[action] # toggle
        return state
    
    def value(self, state):
        """Return sum of all the elements"""
        
        # count 0s peak
        max_0 = 0
        count = 0
        for st in state:
            
            if st == 0:
                count += 1
            else:
                if count > max_0:
                    max_0 = count
                    count = 0
                    
        # count 1s peak
        max_1 = 0
        count = 0
        for st in state:
            if st == 1:
                count += 1
            else:
                if count > max_1:
                    max_1 = count
                    count = 0
        r = 0
        if max_1 > self.t and max_0 > self.t:
            r = len(self.initial)
        
        return max(max_1, max_0) + r
    
    def random_states(self, count=10):
        return np.random.randint(0, 2, size=(count, len(self.initial)))