Search Programm CI Space

Installieren Sie das Search Progamm aus dem CI Space Website

Analysieren Sie die Schweizer Karte der Verbindungen der Hauptstädte mit ihrer Distanzen

Geben Sie das Schweizer Netz ins Search Programm und versuchen Sie die Algorithmen "Depth First" und "Breadth First" interaktiv für die Strecke Lausanne -> St. Gallen. Geben Sie jeweils die Ergebnisse des Ablauf in Ihr Journal ein.

Depth First:

PREVIOUS PATH:
Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel
NEW FRONTIER:
Node: Solothurn Path Cost: 829.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn
Node: Luzern Path Cost: 839.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Luzern
Node: Aarau Path Cost: 811.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Aarau
Node: Aarau Path Cost: 741.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Aarau
Node: Luzern Path Cost: 699.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Luzern
Node: Aarau Path Cost: 671.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Aarau
Node: Aarau Path Cost: 601.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Aarau
Node: Luzern Path Cost: 559.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Luzern
Node: Aarau Path Cost: 531.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Aarau
Node: Aarau Path Cost: 461.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Aarau
Node: Luzern Path Cost: 419.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Luzern
Node: Aarau Path Cost: 391.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern --> Aarau
Node: Aarau Path Cost: 321.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Aarau
Node: Luzern Path Cost: 279.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Luzern
Node: Aarau Path Cost: 251.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Aarau
Node: Aarau Path Cost: 181.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Aarau
Node: Fribourg Path Cost: 75.0 Path: Lausanne --> Fribourg

Breadth First:

CURRENT PATH:
Lausanne --> Neuchâtel --> Solothurn --> Aarau --> Zürich --> St. Gallen (Goal)
NEW FRONTIER:
Node: Bern Path Cost: 247.0 Path: Lausanne --> Fribourg --> Bern --> Neuchâtel --> Solothurn --> Bern
Node: Aarau Path Cost: 259.0 Path: Lausanne --> Fribourg --> Bern --> Neuchâtel --> Solothurn --> Aarau
Node: Zürich Path Cost: 275.0 Path: Lausanne --> Fribourg --> Bern --> Luzern --> Zug --> Zürich
Node: Neuchâtel Path Cost: 379.0 Path: Lausanne --> Fribourg --> Bern --> Aarau --> Basel --> Neuchâtel
Node: Zürich Path Cost: 324.0 Path: Lausanne --> Fribourg --> Bern --> Aarau --> Basel --> Zürich
Node: Bern Path Cost: 358.0 Path: Lausanne --> Fribourg --> Bern --> Aarau --> Zürich --> Bern
Node: St. Gallen Path Cost: 326.0 Path: Lausanne --> Fribourg --> Bern --> Aarau --> Zürich --> St. Gallen
Node: Bern Path Cost: 309.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Bern
Node: Aarau Path Cost: 321.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Neuchâtel --> Solothurn --> Aarau
Node: Zürich Path Cost: 337.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Luzern --> Zug --> Zürich
Node: Neuchâtel Path Cost: 441.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Aarau --> Basel --> Neuchâtel
Node: Zürich Path Cost: 386.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Aarau --> Basel --> Zürich
Node: Bern Path Cost: 420.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Aarau --> Zürich --> Bern
Node: St. Gallen Path Cost: 388.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Bern --> Aarau --> Zürich --> St. Gallen
Node: Solothurn Path Cost: 427.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Aarau --> Basel --> Neuchâtel --> Solothurn
Node: Bern Path Cost: 438.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Aarau --> Basel --> Zürich --> Bern
Node: St. Gallen Path Cost: 406.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Aarau --> Basel --> Zürich --> St. Gallen
Node: Neuchâtel Path Cost: 394.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Aarau --> Zürich --> Bern --> Neuchâtel
Node: Luzern Path Cost: 460.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Aarau --> Zürich --> Bern --> Luzern
Node: Aarau Path Cost: 432.0 Path: Lausanne --> Neuchâtel --> Solothurn --> Aarau --> Zürich --> Bern --> Aarau

A star

Implementieren Sie die Beispiele des A* Tutorial in C++

D:\fh\ds_al\Lektion 11>A-Tutorial-8puzzle 013824765
STL A* 8-puzzle solver implementation
(C)2001 Justin Heyes-Jones
Search found goal state
Displaying solution
0 1 3
8 2 4
7 6 5

1 0 3
8 2 4
7 6 5

1 2 3
8 0 4
7 6 5

Solution steps 2
1 2 3
8 0 4
7 6 5

SearchSteps : 3


D:\fh\ds_al\Lektion 11>a-tutorial-findpath
STL A* Search implementation
(C)2001 Justin Heyes-Jones
Search found goal state
Node position : (0,0)
Node position : (1,0)
Node position : (2,0)
Node position : (3,0)
Node position : (3,1)
Node position : (3,2)
Node position : (3,3)
Node position : (4,3)
Node position : (4,4)
Node position : (5,4)
Node position : (5,5)
Node position : (6,5)
Node position : (6,6)
Node position : (7,6)
Node position : (8,6)
Node position : (9,6)
Node position : (9,7)
Node position : (9,8)
Node position : (10,8)
Node position : (10,9)
Node position : (10,10)
Node position : (11,10)
Node position : (12,10)
Node position : (13,10)
Node position : (14,10)
Node position : (15,10)
Node position : (16,10)
Node position : (16,11)
Node position : (17,11)
Node position : (18,11)
Node position : (18,12)
Node position : (18,13)
Node position : (18,14)
Node position : (18,15)
Node position : (18,16)
Node position : (19,16)
Node position : (19,17)
Node position : (19,18)
Node position : (19,19)
Solution steps 38
SearchSteps : 39

A star

Kompilieren Sie das Projekt astern_stl und versuchen Sie einige Konfigurationen. Publizieren Sie in Ihr Journal eine Konfiguration, welche keine Lösung hat. Versuchen Sie eine andere heuristische Funktion. Publizieren Sie diese andere heuristische Funktion in Ihr Journal

Nicht durchgeführt; Ich probiere stattdessen, den Algorithmus in Java zu implementieren.