Szukaj problemem - Search problem
W teorii złożoności obliczeniowej i teoria obliczalności , A Problem wyszukiwania to typ obliczeniowej problemu reprezentowany przez relacji binarnej . Jeśli R jest takie, że stosunek binarnego pola ( R ) ⊆ Γ + i T to maszyna Turinga , a T oblicza R w przypadku gdy:
- Jeśli x jest taka, że istnieją pewne y takie, że R ( x , y ), a następnie T przyjmuje X z wyjścia oo taki sposób, że R ( x , z ) (może być wiele Y i T trzeba znaleźć tylko jedna z nich)
- Jeśli x jest taka, że nie ma y takie, że R ( x , y ), a następnie t odrzuca x
Intuicyjnie, problem polega na znalezieniu struktura „Y” obiekt „X”. Algorytm mówi się rozwiązać ten problem, jeżeli co najmniej jedna odpowiednia struktura istnieje, a następnie w jednym przypadku tej konstrukcji jest wynikiem; w przeciwnym razie, algorytm zatrzymuje się z odpowiednim wyjściem ( „Nie znaleziono elementu” lub przesłanie podobne).
Takie problemy występują bardzo często w teorii grafów , na przykład, gdzie szukają wykresy dla konkretnej konstrukcji, takich jak dopasowywanie , klik , niezależnego zestawu itp są przedmiotem zainteresowania.
Należy zauważyć, że wykres częściowego funkcji jest związek binarne jeśli T oblicza częściowy Następnie funkcja jest co najwyżej jednej możliwej mocy.
Relacja R mogą być traktowane jako błąd wyszukiwania, a maszyna Turinga który oblicza R jest również, aby rozwiązać. Każdy problem wyszukiwania ma odpowiedni problemu decyzyjnego , a mianowicie
Definicja ta może być uogólnione do n stosunki -ary zastosowaniem jakiegokolwiek odpowiedniego kodowania, które umożliwia wielokrotne ciągi do sprasowania w jeden łańcuch (na przykład poprzez umieszczenie ich po kolei z separatora).
Definicja
Problem wyszukiwania jest określona przez:
- Zestaw stanach
- Stan początkowy
- Stan cel lub cel testu
- logiczną funkcją, która mówi nam, czy dany stan jest stanem cel
- odwzorowaniem ze stanu do zestawu nowych państw
Cel
Znaleźć rozwiązanie, gdy nie podano algorytm do rozwiązania problemu, ale tylko specyfikację co rozwiązanie wygląda.
metoda wyszukiwania
- Generic algorytm wyszukiwania: podany wykres, start węzłów, a goal węzły, stopniowo odkrywać ścieżki z węzłów startowych.
- Utrzymać granicę ścieżki od węzła początkowego, które zostały zbadane.
- W miarę postępu wyszukiwania, granica rozwija się niezbadanych węzłów aż węzeł celem jest spotykane.
- Sposób, w których granica jest rozszerzona określa strategię wyszukiwania.
Input: a graph, a set of start nodes, Boolean procedure goal(n) that tests if n is a goal node. frontier := {s : s is a start node}; while frontier is not empty: select and remove path <n0, ..., nk> from frontier; if goal(nk) return <n0, ..., nk>; for every neighbor n of nk add <n0, ..., nk, n> to frontier; end while
Zobacz też
- Nieograniczona operator wyszukiwania
- problem decyzyjny
- problem optymalizacji
- Liczenie problem (złożoność)
- problem funkcja
- Wyszukiwarka gier
Referencje
Ten artykuł zawiera materiał z problemem wyszukiwania na PlanetMath , który jest licencjonowany w ramach Creative Commons Attribution Share-Alike / licencji .