Подобрать цвета для раскраски башни из 10 этажей

Программирование Помощь с решением задач на Prolog Решение головоломок на Prolog Подобрать цвета для раскраски башни из 10 этажей

В этой теме 3 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 7 мес., 2 нед. назад.

Просмотр 4 сообщений - с 1 по 4 (из 4 всего)
  • Автор
    Сообщения
  • #4241

    toshytwx
    Участник

    Условия:
    1) Последовательность использования цветов должна соответствовать последовательности цветов радуги. При этом допускается повтор текущего цвета и пропуск не более двух цветов.
    2) Яркость каждого последующего цвета должна быть меньше чем яркость предыдущего.
    3) SWI prolog

    Вот, что у меня получилось (работает неправильно):

        :-dynamic layers/3.
    
        init_database :-
            assert(layers(lay1,0.1,red)),
            assert(layers(lay2,0.2,red)),
            assert(layers(lay3,0.4,orange)),
            assert(layers(lay4,0.3,orange)),
            assert(layers(lay5,0.5,yellow)),
            assert(layers(lay6,0.7,yellow)),
            assert(layers(lay7,0.6,green)),
            assert(layers(lay8,0.8,green)),
            assert(layers(lay9,0.7,cyan)),
            assert(layers(lay10,0.9,blue)),
            assert(layers(lay11,1,magente)).
    
        rainbow(red,orange).
        rainbow(orange,yellow).
        rainbow(yellow,green).
        rainbow(green,cyan).
        rainbow(cyan,blue).
        rainbow(blue,magente).
    
        % ?P1, -Result
        main(L1, Res):-
            layers(_, _, _),
            !,
            layers_main(L1, Res).
        main(L1, Res):-
            init_database,
            layers_main(L1, Res).
    
        % ?P1, ?Result
        layers_main(L1, [L1|Ls]) :-
            layers(L1, Alpha, Color),
            layers_add([(Alpha,Color)],Color,Ls).
    
        % ?History, ?Previous color, -Res
        layers_add(History, Color, [Next|Layers]) :-
            length(History, Length),
            Length < 10,
            add(History,Color,Next,Alpha,NextColor),
            layers_add([(Alpha,NextColor)|History],NextColor,Layers).
        layers_add(_, _, []).
    
        %+History, +Color, -Id, -Sides, -Color
        add(History,Color,Next,Alpha,NextColor):-
            layers(Next,Alpha,NextColor),
            next_color(Color,NextColor),
            check_alpha(Alpha, History).
        check_alpha(Alpha,[(Alpha1,_)]):-
            Alpha > Alpha1.
    
        % ?Color, ?NextColor
        next_color(C, C).
        next_color(C, C1) :-
            rainbow(C, C1).
        next_color(C, C1) :-
            rainbow(C, T1),
            next_color(T1, C1).

    #4246

    Если доработаете свое решение — очень прошу скинуть окончательный вариант на форум.

    В целом, программа должна перебирать решения. У нас тут есть статья по решению логических задач и там описаны так называемые «переборные задачи». Фактически полный перебор — это поиск в глубину (так устроен механизм перебора с возвратами prolog) — в вашей задаче это подойдет, т.к. глубина фиксирована 10 этажами.

    Чтобы выполнять такой перебор вам надо где-то фиксировать накопленный результат, это может быть, скажем, список цветов. При этом для генерации мы можем брать крайний цвет и из него генерировать следующие возможные.

    Есть требование:

    1) Последовательность использования цветов должна соответствовать последовательности цветов радуги. При этом допускается повтор текущего цвета и пропуск не более двух цветов.

    Согласно нему, «крайним цветом» может быть red, orange или yellow (потому что если yellow — то мы пропустим не более двух цветов). Ваша программа на настоящий момент это не предусматривает:

    first_color(red). 
    first_color(orange).
    first_color(yellow).

    Дальше — необходимо правило генерации следующего цвета. У вас для этого добавлено правило next_color, которое принимает текущий цвет и возвращает «следующий» допустимый (с учетом возможных пропусков). Однако, сейчас оно написано у вас так, что пропускает не более одного цвета, а по условию — пропустить можно не более двух.

    Исправить можно так:

        % ?Color, ?NextColor
        next_color(Color, Color).
        next_color(Color, NextColor):-
            rainbow(Color, NextColor);
    
            rainbow(Color, ColorGap_One),
            next_color(ColorGap_One, NextColor);
    
            rainbow(Color, ColorGap_One),
            next_color(ColorGap_One, ColorGap_Two),
            next_color(ColorGap_Two, NextColor).

    Есть еще одно требование:
    2) Яркость каждого последующего цвета должна быть меньше чем яркость предыдущего.

    Вам нужно правило, которое будет возвращать следующую возможную яркость. Что-то типа next_brightness. Если яркость при этом будет меняться от 1 до 0 — то выглядеть оно может так:

    first_brightness(1).
    
    next_brightness(Brightness, NextBrightness):-
      NextBrightness is Brightness - 0.1.

    Остается запустить перебор (это очень просто). я не понял что там у вас в решении с базой данных (и зачем она вообще нужна). Очень рекомендую посмотреть другие переборные задачи на нашем форуме и сделать по образцу. Когда будете оформлять решение — обратите внимание на правила оформления кода на нашем форуме (имена переменных C, Temp и т.п. — мало о чем говорят и вот в вашем случае Gap гораздо лучше подходит — ошибки в пропуске цвета вам возможно удалось бы избежать за счет правильного именования).

    #4255

    toshytwx
    Участник

    Доброй ночи, высылаю мое решение. Проверил с входящей базой данных — вроде работает 🙂

    :-dynamic layers/3.
    
    init_database :-
        assert(layers(lay1,1,red)),
        assert(layers(lay5,5,yellow)),
        assert(layers(lay3,4,orange)),
        assert(layers(lay4,3,orange)),
        assert(layers(lay13,11,magente)),
        assert(layers(lay6,7,yellow)),
        assert(layers(lay7,6,green)),
        assert(layers(lay10,9,blue)),
        assert(layers(lay8,8,green)),
        assert(layers(lay2,2,red)),
        assert(layers(lay9,7,cyan)),
        assert(layers(lay11,10,magente)),
        assert(layers(lay12,8,cyan)).
    
    rainbow(red,orange).
    rainbow(orange,yellow).
    rainbow(yellow,green).
    rainbow(green,cyan).
    rainbow(cyan,blue).
    rainbow(blue,magente).
    
    first_color(red).
    first_color(orange).
    first_color(yellow).
    
    first_alpha(1).
    
    % ?P1, -Result
    main(L1, Res):-
        layers(_, _, _),
        !,
        layers_main(L1, Res).
    
    main(L1, Res):-
        init_database,
        layers_main(L1, Res).
    
    % ?P1, ?Result
    layers_main(L1, [L1|Ls]) :-
        layers(L1, Alpha, Color),
        first_color(Color),
        first_alpha(Alpha),
        layers_add([(Alpha,Color)],Color,Ls).
    
    layers_add(History, Color, [Next|Layers]) :-
        add(History,Color,Next,Alpha,NextColor),
        layers_add([(Alpha,NextColor)|History],NextColor,Layers).
    layers_add(_, _, []).
    
    add(History,CurrentColor,Next,NextAlpha,NextColor):-
        next_color(CurrentColor,NextColor),
        layers(_,CurrentAlpha, NextColor),
        not(member((CurrentAlpha,CurrentColor),History)),
        NextAlpha = CurrentAlpha,
        layers(Next,NextAlpha,NextColor),
        not(member((NextAlpha,_),History)).
    
    % ?Color, ?NextColor
    next_color(Color, Color).
    next_color(Color, NextColor):-
        rainbow(Color, NextColor);
        rainbow(Color, ColorGap_One),
        next_color(ColorGap_One, NextColor);
        rainbow(Color, ColorGap_One),
        next_color(ColorGap_One, ColorGap_Two),
        next_color(ColorGap_Two, NextColor).

    К слову пытался решить с помощью поиска в глубину, по данной Вами ссылке, но, увы так и не смог найти верного алгоритма для своего случая. Все задачи примеров прочитал — так и не смог подобрать нужные условия. Программа не всегда выдает цвета для 10 этажей башни, и мой SWI prolog очень странно работает с вещественными числами, почему-то при суммировании двух вещественных чисел, к примеру 0.2 + 0.1 ответ будет 0.3000000000000000000000004, пришлось заменить все значения Alpha на целые. Если Вам не составит труда, хотелось бы узнать решение задачи методом поиска в глубину и узнать эти тонкости работы SWI prolog с вещественными числами, уж больно долго я занимался отладкой что бы узнать такой неприятный факт.

    #4256

    Поиск в глубину — это очень просто, но я немного изменил вычисление следующих цветов и также как вы яркость задал целым числом.

    Перечислим все возможные цвета и напишем функцию, которая из них формирует список:

    color(red).
    color(orange).
    color(yellow).
    color(green).
    color(cyan).
    color(blue).
    color(magente).
    
    get_all_colors(Colors):-
      findall(Color, color(Color), Colors).
    

    Они нам пригодятся, т.к. нам надо не только находить следующий допустимый цвет, но и проверить, что «пропусков не больше двух» с конца радуги.

    зададим яркость, напишем функцию для получения следующей яркости. Ну и следующий уровень получим аналогично:

    first_brightness(10).
    
    next_brightness(Brightness, NextBrightness):-
      NextBrightness is Brightness - 1.
      
    next_layer(Layer, NextLayer):-
      NextLayer is Layer + 1.

    Чтобы получить следующий цвет — собираем список цветов и говорим, что между текущим цветом и следующим есть не более заданного числа элементов. С помощью этой функции мы можем не только найти следующий элемент (при этом пропускается согласно задания не более двух), но и после получения результата — проверить его корректность. От «конца» радуги тоже пропущено ведь не более двух элементов, а мы проверим, что от последнего цвета (magente) не более одного.

    next_color(Color, Color, _MaxGapSize).
    next_color(Color, NextColor, MaxGapSize):-
      get_all_colors(Colors),
      divide_list(Colors, [_, [Color], Gap, [NextColor], _]),
      length(Gap, GapSize),
      GapSize =< MaxGapSize.

    Для разбиения списка на части используется функция divide_list.

    Собственно, проверка последних цветов — получаем все цвета радуги, выбираем встроенной функций last последний из них и требуем, чтобы от текущего цвета до последнего было пропущено не более одного. На самом деле, в таком ключе можно переписать fist_color или наоборот явно перечислить допустимые последние цвета…

    check_last_colors([layer(_Layer, Color, _Brightness)|_Tail]):-
      get_all_colors(Colors),
      last(Colors, LastColor),
      next_color(Color, LastColor, 1).

    Для поиска решения остается получить первый цвет, начальную яркость, запустить поиск в глубину и проверить корректность последнего цвета. Так как поиск в глубину дает перевернутое решение, то проверка последнего цвета на самом деле проверяет первый цвет, ну а полученное решение в конце концов надо перевернуть функцией reverse.

    solve(Rainbow):-
      first_color(FirstColor),
      first_brightness(FirstBrightness),
      
      dfs([layer(1, FirstColor, FirstBrightness)], ReversedRainbow), 
      
      check_last_colors(ReversedRainbow),
      reverse(ReversedRainbow, Rainbow).

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

    dfs(Rainbow, Rainbow):-
      Rainbow = [layer(10, _Color, _Brightness)|_Tail], !.
    dfs(Buffer, Rainbow):-
      Buffer = [layer(HeadLayer, HeadColor, HeadBrightness)|_Tail],
      next_layer(HeadLayer, NextLayer),
      next_brightness(HeadBrightness, NextBrightness),
      next_color(HeadColor, NextColor, 2),
      dfs([layer(NextLayer, NextColor, NextBrightness)|Buffer], Rainbow).

    Вложения:
    Вы должны войти для просмотра вложений.
Просмотр 4 сообщений - с 1 по 4 (из 4 всего)

Для ответа в этой теме необходимо авторизоваться.