Uniform cost search questions

[Class Account]

The book describes uniform cost search as the following:

Uniform cost search expands the node n with the lowest path cost

What type of fringe is usually associated with UCS? It mentions that "if all step costs are equal, UCS is identical to BFS". Does this imply that it uses a queue as a fringe?

When they say "node n with the lowest path cost", does that mean "this lowest path cost of the children of the current node being searched"? Or does it mean "the lowest path cost of nodes in the fringe"?

For every search algorithm, is it true to say: "all children of the current node being examined is added to the fringe"? DFS pushes children starting from the right to the left onto a stack, BFS enqueues children from left to right, UCS enqueues (?) children from lowest cost to highest cost?

With no closed list, how can one detect cycles? (or is it impossible)

[Jason Wolfe]

Post by Class Account
What type of fringe is usually associated with UCS? It mentions that
"if all step costs are equal, UCS is identical to BFS". Does this
imply that it uses a queue as a fringe?

It represents the fringe with a priority queue. If all step costs are
equal, all nodes with the same path length have the same path cost and
so the priority queue acts as a normal queue.

Post by Class Account
When they say "node n with the lowest path cost", does that mean
"this lowest path cost of the children of the current node being
searched"? Or does it mean "the lowest path cost of nodes in the
fringe"?

It means the node with lowest path cost of all nodes in the fringe.

Post by Class Account
For every search algorithm, is it true to say: "all children of the
current node being examined is added to the fringe"? DFS pushes
children starting from the right to the left onto a stack, BFS
enqueues children from left to right, UCS enqueues (?) children from
lowest cost to highest cost?

That is the definition of "expanding" a node. Technically, UCS can
enqueue children in any order; the priority queue will handle ordering
them by cost.

Post by Class Account
With no closed list, how can one detect cycles? (or is it
impossible)

In the formulation we are using, we always keep all ancestors of nodes
in memory in memory as well (so we can extract a solution path once we
find the goal). This is enough to detect cycles -- we can either loop
through the ancestors, or maintain a hash table to detect cycles in
constant time.

Hope this helps ... let me know if any of this is not clear.

Jason