0

In Prolog, i have a simple list of twelve strings. I also have a list of rules that together assign a score to that list. So according to how those elements are placed in my list, they may or may not break a rule.

I need to find the permutation of that list that gives me the highest possible score. How can i do that?

Here is what i have:

compute(InitialSettings, NewSettings, NewSettingsScore):-
    perm(InitialSettings, NewSettings),
    check_bonds(NewSettings, NewSettings, -1, 0, NewSettingsScore).

I omitted the code inside check_bonds because it's not relevant to the question and it would only make it more complicated. Basically i need to loop through all the permutations and find the one that has the highest NewSettingsScore. Is there any way to do this? Thanks in advance!

JayK23
  • 287
  • 1
  • 15
  • 49
  • 1
    Some methods: https://stackoverflow.com/questions/42590572/prolog-getting-max-min-value-via-backtracking – brebs Aug 30 '23 at 16:48
  • 2
    Sounds like it could be a performance optimization to write a predicate which *combines* the `perm` and `check_bonds` logic, to allow earlier rejection. – brebs Aug 30 '23 at 16:51
  • For the scoring method - it is better to give penalty points, i.e. the lowest score wins. This is so that, if you know that the "best" (i.e. lowest score) so far is e.g. 100, and the current penalty score is higher than 100, then the code can *fail fast*, i.e. know that it's pointless to continue calculating the current score, because it will never be "better" than the best so far. – brebs Sep 02 '23 at 08:41

1 Answers1

0

A very simple solution sould be generating all the permutations and then select the one with the highest associated score. In SWI you can write

assign_score(_L,1).
solve(L,Best):-
    findall(LO,permutation(L,LO),LP),
    maplist(assign_score,LP,Ls),
    max_list(Ls,Best).

For simplicity, I assume that all the lists have the same score, since I don't know how they are computed. You get:

?- solve([1,2,3],B).
B = 1.

It can be easily extended to also get the list with the highest score. Moreover, depending on the score computation, you can prune some of the lists while evluating them, so speeding up the process.

damianodamiano
  • 2,528
  • 2
  • 13
  • 21