Задача о ранце на Prolog

      Комментарии к записи Задача о ранце на Prolog отключены

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

  • Автор
    Сообщения
  • #2202

    questioner
    Участник

    Помогите решить на языке Prolog задачу о ранце методом полного перебора.
    Дан мешок вместимости W и набор из n предметов разного веса Wi и стоимости Ci.
    Необходимо выбрать предметы таким образом, чтобы их стоимость была максимальной, а суммарный вес не превосходил размер мешка.

  • #2203

    Алгоритм полного перебора (blind search) выполняет подстановку предметов всех возможных комбинаций предметов, учитывая лишь ограничение вместимости мешка.
    Процесс поиска решения для трех предметов показан на рисунке в виде дерева. Корень дерева — начальное состояние, в котором ни один предмет не выбран. Первым может быть выбран любой из трех предметов, поэтому из корня выходит три дуги; в каждом случае на вторую позицию может быть поставлен любой из двух предметов и т.д. Множество путей из корня дерева представляют собой все возможные решения задачи.

    Вложения:
  • #2205

    Исходные предметы опишем во внутренней базе данных:

    %% item(name, weight, cost)
    item(ball, 0.5, 10).
    item(belcher, 0.2, 11).
    item(hat, 0.1, 20).
    item(glass, 0.5, 5).
    item(book, 0.5, 13).
    item(bread, 0.5, 7).
    item(wurst, 0.2, 15).

    Во время поиска решение (набор предметов и их стоимость) можно накапливать также во внутренней БД. Предикат, в котором будет сохраняться результат должен быть объявлен динамическим — это позволит обновлять значение можно с помощью встроенных Предикаты assert и retract:

    %% bag(Items, Cost)
    :- dynamic
      bag/2. 

    Правило bagpack_problem:

    1. удаляет информацию обо всех предыдущих решениях;
    2. инициализирует начальное значение результата пустым мешком с нулевой ценностью предметов;
    3. выполняет перебор всех решений (при помощи встроенного предиката fail);
    4. выбирает накопленный результат из базы данных.

    bagpack_problem(BagWeight, Bag, Cost):-
      rem_all_bags, 
      assert(bag([], 0)),
      select_items(BagWeight, [], 0), fail;
      bag(Bag, Cost), !.

    Для удаления информации о предыдущих решениях необходимо удалить все факты bag/2 из БД, для этого выполняется retract до тех пор, пока это возможно. Если retract выполнить не удалось, значит все факты удалены, т.е. работа функции завершена:

    rem_all_bags:-
      retract(bag(_Items, _Cost)), rem_all_bags; !.

    Правило перебора решения:

    1. в противном случае обрабатывает одно из возможных решений (но на этом поиск не завершается);
    2. пытается поместить еще один предмет в мешок, остальные обработать рекурсивно;
    3. если в мешок нельзя поместить ни одного предмета — правило завершает работу.

    select_items(_BagWeight, CurrentBag, CurrentBagCost):-
      bag(Items, Cost),
      Cost < CurrentBagCost,
      retract(bag(Items, Cost)),
      assert(bag(CurrentBag, CurrentBagCost)),
      write(CurrentBag), nl.
    select_items(BagWeight, CurrentBag, CurrentBagCost):-
      item(ItemName, ItemWeight, ItemCost),
      ItemWeight =< BagWeight,
      \+ member(ItemName, CurrentBag),
      BagWithItemWeight is BagWeight - ItemWeight,
      BagWithItemCost is CurrentBagCost + ItemCost,
      select_items(BagWithItemWeight, [ItemName|CurrentBag], BagWithItemCost).

    При обработке возможного решения выполняется сравнение стоимости предметов в нем с предыдущим лучшим решением (хранящимся в базе данных). Если новое решение лучше старого — выполняется обновление информации в базе данных. Для просмотра обработанных вариантов и наглядной демонстрации работы программы все найденные варианты выводятся на экран (на алгоритм это не влияет).

    При добавлении нового предмета в мешок нужно выбрать из базы такой предмет, вес которого не превышает вместимость мешка. Кроме того, необходимо проверить, что предмет не был ранее помещен в мешок — используется встроенный предикат member (оператор \+ для таких диалектов, как Turbo Prolog или Visual Prolog должен быть замене на предикат NOT).

  • #2211

    questioner
    Участник

    Решение можно оптимизировать, т.к. сейчас программа перебирает все варианты размещений вещей в мешке, т.е. с учетом порядка их следования. Однако порядок не важен, поэтому количество перебираемых вариантов можно значительно сократить (дерево поиска решений показано на рисунке).
    Дерево поиска решений задачи о ранце. Алгоритм полного перебора.
    Алгоритм по-прежнему перебирает все возможные наборы вещей, т.е. он является полным перебором, реализуя поиск с возвратами.

    • #2249

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

      Алгоритм упаковки рюкзака должен:

      1. инициализировать начальное значение рюкзака;
      2. получить список всех предметов (для генерации сочетаний);
      3. попробовать упаковать в рюкзак каждое возможное сочетание вещей.

      bagpack_problem(BagWeight, Bag, Cost):-
        init_bag,
        
        findall(item(ItemName, ItemWeight, ItemCost), item(ItemName, ItemWeight, ItemCost), Items),
        all_length_compromise(Items, [], Compromise),
        try_bag(Compromise, BagWeight), fail; 
      
        bag(Bag, Cost), !.

      Инициализация рюкзака удаляет всю старую информацию о нем и добавляет запись о пустом рюкзаке с нулевой стоимостью вещей:

      init_bag:-
        retract(bag(_Items, _Cost)), init_bag, !; 
        assert(bag([], 0)), !.

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

      try_bag(Bag, BagWeightLimit):-
        bag_weight_cost(Bag, BagWeight, BagCost),
        BagWeightLimit >= BagWeight, 
        bag(CurrentBag, CurrentBagCost),
        BagCost > CurrentBagCost,
        retract(bag(CurrentBag, CurrentBagCost)),
        assert(bag(Bag, BagCost)).

      Вспомогательное правило bag_weight_cost примает на вход набор вещей, определяет его цену и вес:

      bag_weight_cost([], 0, 0):-!.
      bag_weight_cost([item(_ItemName, ItemWeight, ItemCost)|Tail], Weight, Cost):-
        bag_weight_cost(Tail, TailWeight, TailCost),
        Weight is TailWeight + ItemWeight,
        Cost is TailCost + ItemCost.

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

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