Алгоритм рекурсивного Word Wrap

java algorithm recursion word wrap

1906 просмотра

2 ответа

Я работаю над алгоритмом, который состоит из трех частей. Первый - это рекурсивный метод, который будет привязывать слова к определенной длине с наименьшим штрафом. Второй алгоритм представляет собой динамическую реализацию рекурсивного метода. Последний - Жадный алгоритм проблемы. У меня уже есть Greedy, но я борюсь с рекурсивным решением. Я не совсем уверен, где именно я столкнулся с проблемой с моим рекурсивным методом, но я знаю, что это должно быть нечто похожее на алгоритм Кнута-Пласса. Предполагается, что рекурсивный алгоритм имеет факториальное время работы и больше используется для динамического решения. Если кто-то имеет ссылку на реализацию Knuth-Plass или может обнаружить что-то огромное в моем коде, любая помощь будет оценена по достоинству.

Рекурсивный алгоритм:

    public static ArrayList<String> recursive(ArrayList<String> input, int size) {
    if(input.size() <= 1)
        return input;
    ArrayList<String> temp1 = input;
    ArrayList<String> temp2 = input;
    for(int i = 0; i < input.size(); i++) {
        if(input.size() - 1 >= size)
            break;
        else {
            for(int j = 0; j < input.size(); j++) {
                temp1.set(j, temp1.get(j) + " " + temp1.get(j + 1));
                temp1.remove(j + 1);
                if(totalPenalty(blankChars(temp1, size)) < totalPenalty(blankChars(temp2, size))) {
                    input = recursive(temp1, size);
                } else {
                    input = recursive(temp2, size);
                }
            }
        }
    }
    return input;
}

TotalPenalty () и blankChars возвращают сумму штрафа в конце каждой строки.

EDIT: Я до сих пор не вижу никаких неотложных решений. Любая помощь будет оценена по достоинству.

Автор: Zach Источник Размещён: 17.05.2019 03:41

Ответы (2)


2 плюса

Это похоже на Java, а в Java нет неявного конструктора-копии.

ArrayList<String> temp1 = input;<- это не создаст другого объекта с тем же контентом, а вместо этого ссылку на тот же объект.

Вам необходимо изменить строки 4 и 5 на:

ArrayList<String> temp1 = new ArrayList<String>(input);
ArrayList<String> temp2 = new ArrayList<String>(input);

Я не искал никаких других ошибок, поэтому попробуйте это и обновите вопрос, если у вас возникнут проблемы.

О алгоритме разрушения Knuth-Pass; Вы можете найти реализацию Python по адресу http://oedipus.sourceforge.net/texlib/ . Я не смотрел поближе, но описание похоже на то, что вы ищете.

Автор: Markus Jarderot Размещён: 06.03.2011 11:00

0 плюса

Я надеюсь, что следующий код работает. Здесь я также добавил стоимость для последней строки. Хотя текстовые процессоры используют жадные алгоритмы большую часть времени, и они игнорируют стоимость последней строки. Дайте мне знать, если вам это ясно.

import java.lang.Math;

public int RCS(int[] l , int n , int m , int index) {

    // first base condition - if index gets beyond the array 'l' , then return 0;
    if (index > n - 1) return 0;

    // second base condition - if index is the last word i.e there is only one word left in the
    // array to be inserted in the line then return the cost if added in that line.
    if (index == n - 1) return (m - l[n - 1]) * (m - l[n - 1]) * (m - l[n - 1]);

    // make a global cost variable to be returned
    int cost = Integer.MAX_VALUE;

    // Here , we try to select words from the array and apply RCS on the rest of the array.
    // From index to last element , we iteratvely select first , or first two and so on.
    for (int i = index ; i < n ; i++) {
        int current_space_sum = 0 ;
        // we add the length of the selected word. We have selected words in array from index to i.
        for (int k = index ; k <= i ; k++) {
            current_space_sum = current_space_sum + l[k] ;
        }
        // Adding the space between the words choses. If 2 words are chosen , there is one space and so on
        current_space_sum = current_space_sum + i - index;
        // If the length of the chosen words is greater than the line can accept , no need of looking beyond.
        if (current_space_sum > m) break;
        // Iteratively find the minimum cost
        cost =  Math.min(cost , (m - current_space_sum) * (m - current_space_sum) * (m - current_space_sum) + RCS(l , n , m , i + 1));
    }
    return cost;
}



public static void main(String[] args) {
    WordWrap w = new WordWrap();
    int[] l = {3, 2 , 2 , 5};
    int n = l.length;
    int m = 6;
    int result = w.RCS(l , n , m , 0);

    System.out.println(result);
}
Автор: Ankit kaushik Размещён: 16.11.2018 02:19
Вопросы из категории :
32x32