Динамическое программирование на Хаскеле

Динамическое программирование это подход к решению задач основанный на рекуррентной формуле решения и одном или нескольких стартовых значениях. Задача решается методами динамического программирования если решения подзадач меньшего размера может быть использовано для вычисления решения исходной задачи. Алгоритмы DP обладают полиномиальной сложностью, что намного превосходит другие способы решения задач такого рода.
Для примера, классическая DP-задача 'Размен монет':
Вам даны монеты определенного достоинства (V1, V2, V3…, VN) необходимо посчитать, какое минимальное количество монет потребуется чтобы набрать заданную сумму S. Количество монет каждого достоинства не ограничено.
Рекуррентная формула для решения этой задачи:

  
D(S) = 1 + MIN (D(S-Vi))   

Где D(S) это минимальное количество монет которое потребуется чтобы набрать сумму S
Как мы это можем реализовать в императивном стиле?

  
    public int change(int[] coins, int s) {
        int[] dp = new int[s + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for ( int i = 1; i <= s; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
                    dp[i] = dp[i - coins[j]] + 1;
                }
            }
        }
        return dp[s];
    }

В основе этого решения лежит запоминание предыдущих результатов.
Как это решить на Haskell? Ведь мы уже не можем использовать изменяемые массивы или хэш-таблицы. Зато Haskell нам дает в руки такой мощный инструмент как lazy-evaluation. Lazy-evaluation это тоже в своем роде 'запоминание’ только в обратную сторону. Итак решение:

  
import Array

change :: [Int] -> Int -> Int
change xs n = dp!n
   where
       dp = listArray (0,n) [ cell i | i<-[0..n]]
       cell 0 = 0
       cell i = succ$minl [dp!(i-x)| x<-xs, i>=x]
  
  
minl :: [Int] -> Int
minl [] =  0
minl xs =  minimum xs

Что здесь происходит? Прежде всего, мы создаем массив с решениями

  
dp = listArray (0,n) [ cell i | i<-[0..n]]

Но в чем особенность? Особенность в том, что значения в этом массиве появляются по-требованию.

  
cell i = succ$minl [dp!(i-x)| x<-xs, i>x]

Здесь, справа налево, мы вычисляем i-ый элемент массива. Сначала выбираем все монеты достоинство которых меньше либо равно вычисляемой суммы, потом для каждого такого значения смотрим оптимальное решение в массиве. Заметьте, решения там может еще не быть, но оно будет вычислено для нас по-требованию, причем будет вычисленно лишь однажды и лишь для тех значений, которые нам на самом деле нужны! Находим минимальное решение и прибавляем к нему единицу (succ)
Маленькая утилитная функция, которую пришлось ввести minl нужна лишь потому, что стандартная функция minimum не работает с пустыми массивами.

Заключение

В статьях и литературе динамическое программирование как правило приводится с примерами в императивном стиле. Я попытался привести пример решения классической DP задачи в функциональном стиле, который, надеюсь, может оказаться для кого-то полезным.

Hello World генетический алгоритм

Возвращаясь к Queue ICPC Challenge. Когда алгоритм решения был уже написан и оставались считанные дни до конца соревнования мне пришло в голову поиграть с коэффициентами. Ведь в моем решении, как и почти в любом недетерминированном алгоритме были коэффициенты и от их настройки зависела эффективность алгоритма.

Но как же подобрать оптимальные коэффициенты, когда они нелинейно взаимодействуют друг с другом, когда не известны их границы и не возможно предсказать их влияние на результат исходя из теоретической модели. В голову пришло написание генетического алгоритма.

Чтобы с чего-то начать с генетическим алгоритмом, я написал генетический Hello World. Что он делает? Он берет случайные строки мутирует и скрещивает их до тех пор пока не получится строка ”Hello World!”. На мой взгляд, этот пример является наглядным пособием по реализации генетического алгоритма и помогает в написании генетических алгоритмов для реальных задач.

  

import java.util.List;
import java.util.Collections;
import java.util.ArrayList;


public class GAHelloWorld {

    public static final int POPULATION_SIZE = 1000;
    public static final double ELITE_RATE = 0.1;
    public static final double SURVIVE_RATE = 0.5;
    public static final double MUTATION_RATE = 0.2;
    public static final String TARGET = "Hello World!";
    private static final int MAX_ITER = 1000;

    void initializePopulation(List<Genome> population) {
        int tsize = TARGET.length();

        for (int i = 0; i < POPULATION_SIZE; i++) {
            StringBuilder str = new StringBuilder();
            for (int j = 0; j < tsize; j++) {
                str.append((char) (Math.random() * 255));
            }
            Genome citizen = new Genome(str.toString());
            population.add(citizen);
        }

    }



    String mutate(String str) {
        int tsize = TARGET.length();
        int ipos = (int) (Math.random() * tsize);
        char delta = (char) (Math.random() * 255);

        return str.substring(0, ipos) + delta + str.substring(ipos + 1);

    }

    List<Genome> mate(List<Genome> population) {
        int esize = (int) (POPULATION_SIZE * ELITE_RATE);
        int tsize = TARGET.length();
        List<Genome> children = new ArrayList<Genome>();

        selectElite(population, children, esize);

        for (int i = esize; i < POPULATION_SIZE; i++) {
            int i1 = (int) (Math.random() * POPULATION_SIZE * SURVIVE_RATE);
            int i2 = (int) (Math.random() * POPULATION_SIZE * SURVIVE_RATE);
            int spos = (int) (Math.random() * tsize);

            String str = population.get(i1).str.substring(0, spos) +
                    population.get(i2).str.substring(spos);
            if (Math.random() < MUTATION_RATE) {
                str = mutate(str);
            }
            Genome child = new Genome(str);
            children.add(child);


        }
        return children;
    }

    private void selectElite(List<Genome> population, List<Genome> children, int esize) {
        for(int i=0; i<esize; i++){
            children.add(population.get(i));
        }
    }

    private void go(){
        List<Genome> population = new ArrayList<Genome>();
        initializePopulation(population);

        for (int i=0; i< MAX_ITER; i++) {
            Collections.sort(population);
            System.out.println(i + " > " + population.get(0));

            if (population.get(0).fitness == 0) {
                break;
            }

            population = mate(population);
        }

    }

    public static void main(String[] args) {
       new GAHelloWorld().go();
   }

}
class Genome implements Comparable<Genome> {
    final String str;
    final int fitness;

    public Genome(String str) {
        this.str = str;
        int fitness = 0;
        for (int j = 0; j < str.length(); j++) {
            fitness += Math.abs(str.charAt(j) - GAHelloWorld.TARGET.charAt(j));
        }
        this.fitness = fitness;
    }

    public int compareTo(Genome o) {
        return fitness - o.fitness;
    }

    public String toString(){
        return fitness + " " + str;
    }

}

Результат работы генетического Hello World-а:

  
0 > 419 Un~?z^Kr??p┬
1 > 262 Un~?z^Kr?j?↨
2 > 262 Un~?z^Kr?j?↨
…
15 > 46 Afpdm'Ynosa"
16 > 46 Afpdm'Ynosa"
17 > 42 Afpdm'Ynoia"
18 > 27 Jfpmm↓Vopoa"
…
33 > 9 Ielmo▼Wnole"
34 > 8 Ielmo▲Vopld"
35 > 8 Ielmo▲Vopld"
…
50 > 1 Hello World"
51 > 1 Hello World"
52 > 0 Hello World!

Конечно, запуская алгоритм снова и снова будут получатся другие результаты, ведь изначально выбираются случайные строки.