Geek Answers Handbook

Difficulty in Prolog programs?

In Prolog, problems are resolved using reverse tracking. This is a declarative paradigm, not an imperative (for example, in C, PHP, or Python). In such languages ​​is it worth considering in terms of complexity?

The natural way you consider problems is O (N ^ 2), as someone pointed out this question .

+4
source share
3 answers

It is important to analyze Complexity in any language, whether it be a prologue or any imperative language. However, I can give you some tips on speeding up your prolog programs.

  • Always always try to do recursive programs. This ensures that your program does not end from the stack.
  • Try using cut and fail in your programs where you know you don't need further answers.
  • Try using drives.
  • Check out CLPFD, it helps significantly reduce the search space that speeds up your program. Essentially, this eliminates the bad choices before your program can step back and spend time exploring these options.
  • Always write the best result rule. (It really depends on the problem, but generally the rule is best suited).
+1
source

You can definitely analyze the complexity of Prolog programs, like any other language. This particular problem that you have connected may be O (n ^ 2). But not all Prolog programs will have this complexity. For example, you can easily write a SAT solution in Prolog, and this problem is NP-Complete.

+4
source

It completely depends on the problem.

eg. as far as I can tell, summing up the list of numbers O (N).

sum([],0). sum(List,Total) :- sum(List,0,Total). sum([],Total,Total). sum([Head|Rest],Accumulator,Total) :- SoFar is Head + Accumulator, sum(Rest,SoFar,Total).

The only actions are adding ("is") and a recursive call, which should cost 1 each. They will be executed ~ once per element in the list, so the total actions should be ~ 2N, which is equal to O (N).

+4
source

More articles:


All Articles