Skip to content
Menu
CDhistory
CDhistory

N-Puzzle

Posted on november 4, 2021 by admin

Met deze webtoepassing kunt u een grafische weergave bekijken van een reeks verschillende grafische zoekalgoritmen, terwijl u een keuze maakt uit 8 puzzelproblemen.

  • Start
  • Initiële en Doel staten
  • Zoekalgoritme
  • Heuristische functie
  • Single-Step or Burst Mode
  • De zoekboom
  • Statusweergave
  • Node kleuren
  • Open en gesloten lijsten
  • Credits

Start

Aan de linkerkant van deze toepassing ziet u het configuratiescherm. Met behulp van het Configuratiescherm, kunt u de volgende aspecten van de toepassing configureren:

  • Initiële staat en doel staat
  • Welke zoekalgoritme te gebruiken
  • Welke Heuristische functie te gebruiken, indien u een Informed Search Algorithm
  • En of u single-step of burst mode wilt gebruiken

Elke van deze opties worden hieronder in meer detail beschreven.

Initiële en Doel staten

Om de Initiële of Doel staten in te stellen, kunt u klikken op ofwel de ‘Bewerk staat’ knop of de grafische representatie van de staat.

U zou een popup als de volgende moeten zien:

Om een tile te veranderen, klik eenvoudig op de tile die u wilt vervangen, voer dan de nieuwe waarde in op uw toetsenbord. De tegel wordt dan verwisseld met de tegel die eerder die waarde had.

Zoekalgoritme

N-Puzzle ondersteunt vijf verschillende op grafieken gebaseerde zoekalgoritmen. De eerste drie zijn niet-geïnformeerde zoekalgoritmen:

  • Breadth-first Search
  • Depth-first Search
  • Iterative Deepening Search

De andere twee zijn geinformeerde zoekalgoritmen:

  • A* Zoeken
  • Greedy Zoeken

Als u een Informed Search Algorithm kiest, dan moet u ook een Heuristische Functie kiezen.

Heuristische functie

N-Puzzle ondersteunt drie verschillende heuristische functies:

  • Euclidische afstand
  • Manhattan-afstand (afstand tussen steden en blokken)
  • Tiles Out-of-place

Single-Step or Burst Mode

N-Puzzle kan in twee modi worden gebruikt. Standaard is dit de Single-Step modus, waarmee u een zoekopdracht stap voor stap kunt ’terugspoelen’. Dit is handig om een beter begrip te krijgen van hoe een zoekalgoritme werkt.

De andere modus is de Burst-modus. Eenmaal gestart, gaat de Burst-modus door met zoeken totdat de doeltoestand is gevonden. Een zoekopdracht in de Burst-modus kan worden gepauzeerd, maar kan niet worden ’teruggespoeld’.

De zoekboom

Statusweergave

Terwijl een zoekopdracht actief is, kunt u een visuele weergave van de zoekboom zien. Elk knooppunt in deze zoekboom vertegenwoordigt een arrangement van tegels (of toestand), en wordt getekend als een vak dat is verdeeld in 4 secties.

Het volgende diagram toont een knooppunt uit een Greedy zoekactie:

De grootste sectie is de puzzel toestand. Daaronder zie je twee kleinere secties.

Onder de puzzel staat zijn twee secties. De sectie aan de linkerkant is de diepte van de knoop. De rechtse sectie is de heuristische score. De heuristische score wordt alleen gebruikt met Informed Search Algorithms, dus als je Breadth-first, Depth-first of Iterative Deepening Search gebruikt, zal de heuristische score weggelaten worden.

De laatste sectie registreert de volgorde waarin de knopen zijn uitgebreid. Bijvoorbeeld, de root node zal altijd ‘#1’ zijn, en de volgende node zal worden gemarkeerd als ‘#2’.

Node kleuren

Om de zoekboom meer ‘leesbaar’ te maken, is de rand van elke node gekleurd op basis van zijn huidige status.

Het volgende diagram toont het A* algoritme (met de Euclidische afstand heuristiek) toegepast op een probleem dat in slechts twee zetten kan worden opgelost:

De kleuren kunnen als volgt worden geïnterpreteerd:

Kleur Betekenis
Blauw Als een knooppunt in de Open Lijst staat, wordt het blauw gemarkeerd.
Rood Na elke iteratie van een zoekalgoritme wordt het knooppunt dat als volgende zal worden uitgebreid rood gemarkeerd. Dit geldt zelfs als het doel-knooppunt al gevonden is.
Grijs Als een toestand al verkend is, wordt deze grijs weergegeven. Bijvoorbeeld, in stap 2) van het diagram hierboven, is de begintoestand grijs gekleurd om aan te geven dat deze is verkend. In stap 3) wordt een knoop die de begintoestand voorstelt opnieuw ontdekt, maar hij wordt niet uitgebreid omdat de begintoestand is uitgebreid via de wortelknoop.
Groen Als de doeltoestand eenmaal is gevonden, wordt hij groen gemarkeerd.
Goud Als een knoop die de doeltoestand vertegenwoordigt is gevonden, zullen alle knooppunten op het pad terug naar de hoofdknoop in goud worden gemarkeerd.
Paars Als Iterative Deepening Search wordt gebruikt, zullen niet-ontdekte knooppunten die de maximale diepte overschrijden niet aan de open lijst worden toegevoegd. Deze knooppunten worden paars gekleurd.

Open en gesloten lijsten

Terwijl de zoekalgoritmen worden uitgevoerd, worden twee lijsten bijgehouden. De eerste is de Open Lijst – deze wordt gebruikt om knooppunten bij te houden die ontdekt zijn, maar nog niet verkend.

De tweede is de Gesloten Lijst – deze wordt gebruikt om knooppunten bij te houden die verkend zijn, of knooppunten die niet verkend zullen worden omdat ze toestanden vertegenwoordigen die al verkend zijn via andere knooppunten.

Wanneer een zoekactie actief is, zal het aantal knooppunten in de Open en Gesloten Lijsten zichtbaar zijn in de linker bovenhoek:

Credits

Geef een antwoord Antwoord annuleren

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *

Recente berichten

  • Acela is terug: NYC of Boston voor $99
  • OMIM Entry – # 608363 – CHROMOSOME 22q11.2 DUPLICATION SYNDROME
  • Kate Albrecht’s Parents – Learn More About Her Father Chris Albrecht And Mother Annie Albrecht
  • Temple Fork Outfitters
  • Burr (roman)

Archieven

  • februari 2022
  • januari 2022
  • december 2021
  • november 2021
  • oktober 2021
  • september 2021
  • augustus 2021
  • juli 2021
  • juni 2021
  • mei 2021
  • april 2021
  • DeutschDeutsch
  • NederlandsNederlands
  • SvenskaSvenska
  • DanskDansk
  • EspañolEspañol
  • FrançaisFrançais
  • PortuguêsPortuguês
  • ItalianoItaliano
  • RomânăRomână
  • PolskiPolski
  • ČeštinaČeština
  • MagyarMagyar
  • SuomiSuomi
  • 日本語日本語
©2022 CDhistory | Powered by WordPress & Superb Themes