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:

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ż

Referencje

Ten artykuł zawiera materiał z problemem wyszukiwania na PlanetMath , który jest licencjonowany w ramach Creative Commons Attribution Share-Alike / licencji .