From: Roland K. <kam...@cs...> - 2012-06-09 14:13:18
|
On Saturday, June 09, 2012 01:36:34 PM Martin wrote: > On Sat, 2012-06-09 at 13:51 +0200, Sai Pavan K Veeranki wrote: > > Dear Fellows, > > > > I am Learning answer set programing for my project, i need to be > > honest, its really hard to understand. > > > > I was trying to write a program for shortest path between any two > > nodes. I took the example from the guide which was running pretty > > good, i didn't understand some of the steps. I have got no clue to get > > the shortest path between two nodes. > > OK; what problems were you having? Can you be a bit more specific than > not understanding some of it? Could you post the bits you get and the > bits you don't. > > > I would like to request you guys, to let me know where i have to start > > with constraint programing. Which kind of basic knowledge would help > > me to understand the scripts of ASP. > > One tip; I'd suggest you don't think of the input as a 'script' or > 'program' in the conventional sense as there is no notion of procedure > or sequence. Think of it more as a description, a specification or a > formulae. > > > I am an average student, but interested in learning new stuff, so I > > need help to get hands on experience on ASP. > > Any information like literature, books, examples, would be very much > > appreciated. > > Well... if you forgive the shameless self promotion; you might want to read > our paper: > > A pragmatic programmer’s guide to answer set programming > http://opus.bath.ac.uk/17862/ > > this includes the methodology we use and a step by step worked example > of how to develop a program. I've got an updated and expanded version > of it that I will send to you off-list. You might also want to have a > look at the work done by the M&M ASP project of Hans Tompits. Hi, I just want to add a comment on the problem you are trying to solve: Calculating shortest paths is a well studied problem; Dijkstra's algorithm is polynomial and works very well to solve this problem. Actually, it is possible to calculate shortest paths in ASP too, but it is hard to write something that mimics Dijkstra's algorithm. If you do not care for performance (this is a lousy way to encode this), you could abuse the minimize constraint: % instance edge(A,B,Weight). source(X). target(X). % encoding { path(A,B) : edge(A,B,_) }. reach(A) :- source(A). reach(B) :- reach(A), path(A,B). :- not reach(A), target(A). #minimize [ path(A,B) : edge(A,B,W) = W]. It is of course possible to encode Dijkstra's algorithm too. But this is quite involved and I cannot do it in just a minute here. If possible, I would always do such computations outside of ASP in, e.g., a preprocessing step. ASP is better at solving search problems. Regards, Roland |