Temat 9

Question 1

Heurystyka, czy tradycyjne algorytmy przeszukiwania grafu?

Answer 1

Heurystyka jest zazwyczaj bardziej wydajniejsza, jednakże musi być sprawna i dobrze napisana. Niewłaściwa heurystyka może zmniejszyć optymalność.

Question 2

Kiedy najlepiej używać DFS albo BFS nad heurystyką?

Answer 2

Algorytmy DFS i BFS służą głównie do grafów nieskierowanych i nieważonych. Są również optymalnym rozwiązaniem w porównaniu do złej heurystyki.

Question 3

Z jakich algorytmów korzysta algorytm Johnsona?

Answer 3

Bellmana-Forda i Dijkstry dlatego jego złożoność czasowa wynosi: O(n^2logn + kn)

Question 4

Kiedy algorytm Johnsona jest lepszy od Floyd-Warshalla?

Answer 4

Jest bardziej efektywny dla grafów rzadkich.

Question 5

Jakie mamy dwa sposoby poruszania się w przeszukiwaniu wszerz (BFS)?

Answer 5

• ruch w czterech kierunkach - von Neumana
• ruch w ośmiu kierunkach - Moore’a

Question 6

Algorytm A*: Co oznacza gwiazdka przy A? Jaki problem rozwiązuje ten algorytm?
Co jest ważne w tym algorytmie?

Answer 6

Gwiazdka oznacza optymalność. Algorytm rozwiązuje problem single-pair shortest path. Najważniejsza jest heurystyka algorytmu, która oblicza koszt dotarcia do celu h(v).

Question 7

Na czym polega algorytm Dijkstry i Bellmana-Forda i jaka jest ich znacząca różnica?

Answer 7

Na relaksacji krawędzi, z tym, że Dijkstra jest zachłanny i szuka najlepszej drogi. Dodatkowo Dijkstra działa jedynie na wagach dodatnich.