Problém s vyhledáváním - Search problem

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Problém s vyhledáváním“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (prosinec 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek možná matoucí nebo nejasné čtenářům. Prosím, pomoz nám objasnit článek. O tom by mohla být diskuse diskusní stránka. (Prosinec 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie výpočetní složitosti a teorie vypočítatelnosti, a problém s hledáním je typ výpočetní problém zastoupená a binární relace. Li R je binární vztah takový, že pole (R) ⊆ Γ⁺ a T je Turingův stroj, pak T počítá R li:

• Li X je takový, že tam nějaký je y takhle R(X, y) pak T přijímá X s výstupem z takhle R(X, z) (může jich být více y, a T stačí najít jen jednu z nich)
• Li X je takový, že neexistuje y takhle R(X, y) pak T odmítá X

Problém intuitivně spočívá v nalezení struktury „y“ v objektu „x“. An algoritmus říká se, že řeší problém, pokud existuje alespoň jedna odpovídající struktura, a poté se vytvoří jeden výskyt této struktury; jinak se algoritmus zastaví s příslušným výstupem („Položka nebyla nalezena“ nebo jakoukoli podobnou zprávou).

Takové problémy se velmi často vyskytují v teorie grafů například při hledání grafů pro struktury, jako jsou konkrétní vhodný, kliky, nezávislá sada atd. jsou předmětem zájmu.

Všimněte si, že graf částečné funkce je binární relace, a pokud T vypočítá částečnou funkci, pak existuje maximálně jeden možný výstup.

Vztah R lze považovat za problém hledání a Turingův stroj, který počítá R také to říká. Každý problém hledání má odpovídající rozhodovací problém, jmenovitě

${ displaystyle L (R) = {x střední existuje yR (x, y) }. ,}$

Tuto definici lze zobecnit na n-ary vztahy pomocí libovolného vhodného kódování, které umožňuje komprimovat více řetězců do jednoho řetězce (například jejich postupným výpisem s oddělovačem).

Definice

Problém s vyhledáváním je definován:^[1]

• Sada státy
• A počáteční stav
• A stav cíle nebo test cíle

booleovská funkce, která nám říká, zda je daný stav stavem cíle

• A nástupnická funkce

mapování ze státu do množiny nových států

Objektivní

Najděte řešení, pokud nemáte daný algoritmus k řešení problému, ale pouze specifikaci toho, jak řešení vypadá.^[1]

Metoda vyhledávání

• Obecný vyhledávací algoritmus: vzhledem k grafu, počátečním uzlům a uzlům cíle, postupně prozkoumejte cesty od počátečních uzlů.
• Udržujte hranici cest ze startovacího uzlu, které byly prozkoumány.
• Jak hledání pokračuje, hranice se rozšiřuje do neprozkoumaných uzlů, dokud nenarazí na cílový uzel.
• Způsob, jakým se hranice rozšiřuje, definuje strategii vyhledávání.^[1]

   Vstup: graf, sada počátečních uzlů, cíl booleovské procedury (n), který testuje, zda n je uzel cíle. frontier: = {s: s je počáteční uzel}; zatímco hranice není prázdná: vyberte a odeberte cestu  z hranice; pokud cíl (nk) vrátí ; pro každého souseda n z nk přidejte  na hranici; skončit chvíli

Viz také

• Neomezený vyhledávací operátor
• Rozhodovací problém
• Problém s optimalizací
• Problém počítání (složitost)
• Funkční problém
• Hledat hry

Reference

Tento článek včlení materiál od problému hledání na PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.