Пролог, как упорядочить список с ограничениями

Я новичок в Prolog, и я пытаюсь использовать его для заказа списка с определенными ограничениями.

Проблема начинается со следующих определений:

  • Item — это список длиной 3: [Name, Type, Weight].
  • Content — это список элементов [item_0,.....item_n].
  • ContentList — это список Content

Например:

С предметами:

item_1 = [chicken, meat, 1.0]
item_2 = [eggplant, vegetable, 0.5]
item_3 = [tomatoes, vegetable, 1.0]
item_4 = [bread, other, 0.2]

Мы создаем два содержания:

contentA = [item_2, item_3]
contentB = [item_1, item_4]
contentC = [item_3, item_4]

Итак, теперь, допустим, у нас есть некоторые определения контента:

hasItemType([_, XType, _], XType).

hasListItemType([H|T], Type) :-
    hasItemType(H, Type);
    hasListItemType(T, Type).

hasListOnlyItemType([H|T], Type) :-
    hasItemType(H, Type),
    hasListItemType(T, Type)

isVegetarian(Content) :- hasListOnlyItemType(Content, vegetable).
hasVegetables(Content) :- hasListItemType(Content, vegetable).
hasMeat(Content) :- hasListItemType(Content, meat).

Цель будет:

Учитывая список Content, возвращает ContentList, который лучше всего соответствует определенному порядку:

Например (но, таким образом, мой вопрос, я не уверен, что это правильный способ сделать это.)

 -> `order(A, B)` A is before B in the output list.


order(ContentA, ContentB) :-
    isVegetarian(ContentA),
    hasVegetables(ContentB).

order(ContentA, ContentB) :-
    hasVegetables(ContentA),
    hasMeat(ContentB).

В идеале я хотел бы что-то вроде этого:

solve([contentB, contentC, contentA]) чтобы вернуть [contentA, contentB, contentC]

потому что: порядок (содержание A, содержимое B), порядок (содержимое A, содержимое C), порядок (содержимое B, содержимое C)

Итак, у меня есть два основных вопроса:

  1. Это разумный способ формализовать мою проблему.
  2. Как только order и ограничения будут правильно определены, как можно будет написать решатель?

Я понимаю, что мой вопрос немного широк, поэтому я приму любые предложения, ссылки, идеи;)

Заранее спасибо, если вы это прочитаете!


constraint-programming prolog
person Antobiotics    schedule 17.10.2016    source источник
comment
Где определение hasItemType(H, Type)?? также приведите простой пример для вывода порядка/2 и пример для решателя.   -  person coder    schedule 17.10.2016
comment
Привет, спасибо за внимание к моему вопросу. Я добавил немного деталей. Это на самом деле мой вопрос, я не уверен, как написать решатель   -  person Antobiotics    schedule 17.10.2016

Ответы (1)


arrow_upward
1
arrow_downward

Вам нужна функция сортировки, но не сортировка со стандартными функциями-предикатами сравнения, такими как =< или >=, а с использованием вашего предиката порядка. Итак, вам нужно реализовать алгоритм сортировки на Прологе, например сортировку вставками:

insertionSort([], []).

insertionSort([HEAD|TAIL], RESULT) :-
   insertionSort(TAIL, LIST), insertInPlace(HEAD, LIST, RESULT).

insertInPlace(ELEMENT, [], [ELEMENT]).

insertInPlace(ELEMENT, [HEAD|TAIL], [ELEMENT|LIST]) :-
   order(ELEMENT,HEAD), insertInPlace(HEAD, TAIL, LIST).

insertInPlace(ELEMENT, [HEAD|TAIL], [HEAD|LIST]) :-
   \+order(ELEMENT ,HEAD), insertInPlace(ELEMENT, TAIL, LIST).

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

Я думаю, что это работает, я проверил это, запросив:

insertionSort([[[chicken, meat, 1.0],[beaf, meat, 1.0]],[[eggplant, vegetable, 0.5],[tomatoes, vegetable, 1.0]]],Result).

где я дал список [content1,cntent2], где content1 имел тип мяса, а контент 2 имел тип овоща, поэтому в соответствии с предикатом порядка вывод должен быть [content2,content1], так что вывод я считаю правильным:

?- insertionSort([[[chicken, meat, 1.0],[beaf, meat, 1.0]],[[eggplant, vegetable, 0.5],[tomatoes, vegetable, 1.0]]],Result).
Result = [[[eggplant, vegetable, 0.5], [tomatoes, vegetable, 1.0]], [[chicken, meat, 1.0], [beaf, meat, 1.0]]] ;
false.
person coder    schedule 17.10.2016
comment
Большое спасибо! Отличная отправная точка. Я постараюсь поделиться с вами, где я иду с ним. - person Antobiotics; 17.10.2016
comment
Я пробовал с разными примерами, и, похоже, это работает очень хорошо! Спасибо большое. Процесс создания программ на Прологе теперь ясен! Большое спасибо - person Antobiotics; 18.10.2016
comment
Рад, что помог!!, имейте в виду, что ваша проблема была больше похожа на понимание того, что вам нужен алгоритм сортировки, тогда вы можете реализовать любой алгоритм сортировки, который пожелаете, например, вы можете реализовать сортировку слиянием, которая еще более эффективна.... - person coder; 18.10.2016