I'm trying to implement an SMA* graph search algorithm that I found in a paper here(Rong Zhou, Eric A. Hansen: Memory-Bounded A* Graph Search. FLAIRS-02 Proceedings 203-209) and I would like to clarify my understanding of the pseudo-code found in the appendices, specifically the set builder notation used:

set builder notation

What I understand this to mean is: make a set called B from all the elements of beta, given that beta and x are elements of OPEN, and only include the elements of beta where F(beta)<=F(x)

To test my understanding I have written this pseudo-code which I believe builds the necessary set.

x = {OPEN}
b = {OPEN}

B = {}

for i = 0; i<sizeof(b); i++
  for j = 0; j<sizeof(x); j++
    if F(b[i]) <= F(x[j])

My question is:

Do my plain English sentence and pseudo-code demonstrate that I have interpreted the set builder notation correctly?

  • 1
    $\begingroup$ What exactly is your question? "Please debug my code for me" is off-topic here and everywhere else on the Stack Exchange network. $\endgroup$ – David Richerby Apr 27 '17 at 17:04
  • $\begingroup$ Welcome to CS.SE! Do you know what set comprehension notation $\{\beta \mid \cdots \}$ means? If not, it might help you to study that. Can you ask a more specific question than "I don't understand those two lines"? What parts of those lines do you understand, and what parts don't you? Can you infer anything from the text of the paper? It appears they're using nonstandard notation in at least one place: I have no idea what $\forall x \implies \cdots$ is supposed to mean. Can you edit the question to give a full reference for the paper, including title, authors, and where it was published? $\endgroup$ – D.W. Apr 27 '17 at 17:39
  • $\begingroup$ The paper says that SMAG* came from an earlier paper, "Kaindl and Khorsand (1994)", and is based on SMA*, from "Russell (1992)". You should be reading those earlier papers! Presumably the paper that introduced SMAG* should have a clear description of how it works. Why don't you read those papers, then if there's something you're still unclear on, come back and edit your question to ask a more specific question and to address the feedback you've gotten so far? $\endgroup$ – D.W. Apr 27 '17 at 17:41
  • $\begingroup$ Thanks for the feedback. I can see now that I included too much information in the hope of providing some context, but that it has confused the question. I had not heard of set comprehension notation before, but after reading the wikipedia article it seems to be the missing puzzle piece in my understanding. I'll now edit the question, and hopefully it'll be clearer what I am asking. $\endgroup$ – moremilopls Apr 28 '17 at 5:18
  • $\begingroup$ I did look for those other referenced papers but I couldn't find them on google scholar or my University's database. I think I understand how the algorithm works and I can do it on paper, but my background is in engineering, so the logic and the code are confusing me $\endgroup$ – moremilopls Apr 28 '17 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.