Overig

COS3751 assignment 3 memo 2024

4 keer verkocht

Vak
Techniques of Artificial Intelligence (COS3751)

Instelling
University Of South Africa (Unisa)

COS3751 assignment 3 memo 2024: Question 1: 30 Marks (1.1) Highlight the differences between a tree and graph search. (1.2) How does a Breadth First Search (BFS) differ from the general tree search algorithm? What is the major reason for implementing the algorithm in this way? Provide an exampl...

[Meer zien]

Voorbeeld 2 van de 8 pagina's

Bekijk voorbeeld

Geupload op 24 augustus 2024
Aantal pagina's 8
Geschreven in 2024/2025
Type Overig
Persoon Onbekend

cos3751

Instelling
University of South Africa (Unisa)
Vak
Techniques of Artificial Intelligence (COS3751)

Volgen

CrystalIndigo

Lid sinds 4 jaar 433 documenten verkocht

€6,38

In winkelwagen

Op verlanglijstje

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

COS3751 ASSIGNMENT 3 2024
memo (detailed explanation)

Crystal Indigo!
Crystal Indigo!
Providing all solutions you need anytime
+27 76 626 8187

, Question 1

1.1 Differences between Tree and Graph Search
Tree search Graph search
A tree search algorithm starts at a root node and A graph search algorithm also starts at a root
explores branches to find a goal state. node but accounts for the possibility of cycles
and revisits to the same nodes.
It assumes that each node is unique and doesn't Maintains an explored set to track visited nodes,
revisit nodes. ensuring that the algorithm does not revisit them
and thus avoids infinite loops.
No need to keep track of visited nodes since all More complex than tree search due to the need
nodes are distinct. to handle redundant paths and cycles.
The main difference between the two is that we don’t need to keep track of already explored nodes,
since a simple tree cannot have revisited states. So the tree search simple selects a leaf node from
the frontier, goal tests, and if it is a goal it returns the path to that node. Applying a tree search to a
graph creates problems since there may be redundant paths and loops. The graph search solves this
problem by augmenting the tree search with an explored list. When nodes are generated during the
search that are already on the closed list they are not added to the frontier.

1.2 How does a Breadth First Search (BFS) differ from the general tree
search algorithm? What is the major reason for implementing the algorithm in
this way? Provide an example to aid your discussion.
BFS explores the search space level by level, visiting all nodes at the current depth before moving
on to nodes at the next depth level. It guarantees finding the shortest path in an unweighted graph,
making it suitable for scenarios where the goal is to minimize steps or actions.

The general tree search algorithm does not prescribe a specific order of node exploration, meaning
it can be implemented as BFS, DFS, or another strategy. Unlike BFS, a general tree search might
not guarantee the shortest path if it does not explore nodes level by level. In a general tree search
the goal test phase happens on expansion. Since a BFS has degraded performace in large search
spaces, the goal test takes place during generation. Any suitable example to illustrate this concept is
considered
Major Reason for Implementing BFS:
BFS is implemented to ensure that the shortest path is found in the minimum number of steps,
which is crucial in scenarios where the cost is associated with the number of actions taken. For
example, consider a maze where you need to find the shortest path from the entrance to the exit.
BFS will explore all possible paths leading one step away from the entrance, then all paths leading
two steps away, and so on, ensuring the shortest path is found.

1.3 Consider an example of a sliding-block puzzle game state provided
below (Figure 1). How many distinct states are there for puzzles of this sort?
How many search nodes? Explain how you reached your answer.
1. Distinct States:
• The number of distinct states in a sliding-block puzzle depends on the number of
blocks and positions they can occupy. For a 15-puzzle (4x4 grid with 15 blocks and

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, Bancontact of creditcard en je bent klaar. Geen abonnement nodig.

Focus op de essentie

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper CrystalIndigo. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €6,38. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 69052 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Start met verkopen

Overig

COS3751 assignment 3 memo 2024

Document informatie

Onderwerpen

Geschreven voor

Verkoper

Ontvangen beoordelingen

Voorbeeld van de inhoud