Логическое программирование: как распределить ресурсы среди потребителей?

Question

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

• каждый потребитель имеет набор типов ресурсов они могут использовать,
• каждый ресурс уникален,
• каждый потребитель должен получить п> 0 ресурсы,
• должны быть распределены все ресурсы.

E. g. мы имеем этот список потребителей и их предпочтений:

• А: {X, W}
• В: {X, Y, V}
• С: {Х, Z}
• D: {Z}

У нас есть список ресурсов: [X, W, Y, V, Z].

Если мы назначим ресурсы наивно, итерируя по списку потребителей и предоставив им первый доступный ресурс из своего набора, мы потерпим неудачу в D, потому что только Z уже назначен C. Лучшим решением является следующее: A (W), B (Y, V), C (X), D (Z).

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

Где я должен смотреть, для чего мне нужно google, имеет ли эта проблема имя?

Answer 1

Это пример бесконечного множества задач выделения ресурсов, для которых логическое программирование действительно хорошо подходит и часто используется. Связанные с этим задачи называются проблемами транспорта и назначения в литературе, хотя детали в этой формулировке различны. Рассмотрим эту формулировку Пролог в качестве рабочего отправную точку, с которой вы можете решить такие задачи:

distribution([], [], []). 
distribution([C-Ps|CPs], Rs0, [C-As|CAs]) :- 
     allocation(Ps, As, Rs0, Rs1), 
     As = [_|_], 
     distribution(CPs, Rs1, CAs). 

allocation(_, [], Rs, Rs). 
allocation(Ps0, [A|As], Rs0, Rs) :- 
     select(A, Ps0, Ps1), 
     select(A, Rs0, Rs1), 
     allocation(Ps1, As, Rs1, Rs). 

distribution/3 ожидает в качестве первого аргумента список пар вида Consumer-Preferences, а в качестве второго аргумента список ресурсов. Он связывает это описание экземпляра с решениями в виде пар Consumer-Allocated resources. Пример запроса с SWI-Prolog для конкретной задачи вы указали:

?- distribution([a-[x,w],b-[x,y,v],c-[x,z],d-[z]], [x,w,y,v,z], Ds). 
Ds = [a-[w], b-[y, v], c-[x], d-[z]] ; 
Ds = [a-[w], b-[v, y], c-[x], d-[z]] ; 
false. 

Вы можете использовать эту формулировку для всех задач такого рода. Формула завершена: В ней сообщаются все существующие решения (и некоторые из них избыточны, поскольку выделенные ресурсы могут быть указаны в любом порядке, как вы уже видите в примере выше, вы можете ввести ограничения на нарушение симметрии в allocation/4, чтобы избежать этого - один из способов решить это - настаивать на том, чтобы As возрастал по отношению к стандартному порядку), и, следовательно, нет (дальнейших) решений, если он отвечает false.