Search problem

In the mathematics of computational complexity theory, computability theory, and decision theory, a search problem is a type of computational problem represented by a binary relation. Intuitively, the problem consists in finding structure "y" in object "x". An algorithm is said to solve the problem if at least one corresponding structure exists, and then one occurrence of this structure is made output; otherwise, the algorithm stops with an appropriate output ("not found" or any message of the like).

Every search problem also has a corresponding decision problem, namely

This definition may be generalized to n-ary relations using any suitable encoding which allows multiple strings to be compressed into one string (for instance by listing them consecutively with a delimiter).

More formally, a relation R can be viewed as a search problem, and a Turing machine which calculates R is also said to solve it. More formally, if R is a binary relation such that field(R) ⊆ Γ+ and T is a Turing machine, then T calculates R if:

  • If x is such that there is some y such that R(x, y) then T accepts x with output z such that R(x, z) (there may be multiple y, and T need only find one of them)
  • If x is such that there is no y such that R(x, y) then T rejects x

(Note that the graph of a partial function is a binary relation, and if T calculates a partial function then there is at most one possible output.)

Such problems occur very frequently in graph theory and combinatorial optimization, for example, where searching for structures such as particular matchings, optional cliques, particular stable sets, etc. are subjects of interest.

Definition

A search problem is often characterized by:[1]

Objective

Find a solution when not given an algorithm to solve a problem, but only a specification of what a solution looks like.[1]

Search method

  • Generic search algorithm: given a graph, start nodes, and goal nodes, incrementally explore paths from the start nodes.
  • Maintain a frontier of paths from the start node that have been explored.
  • As search proceeds, the frontier expands into the unexplored nodes until a goal node is encountered.
  • The way in which the frontier is expanded defines the search strategy.[1]
   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

See also

References

  1. ^ a b c Leyton-Brown, Kevin. "Graph Search" (PDF). ubc. Retrieved 7 February 2013.

This article incorporates material from search problem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

Read other articles:

Anis sisik

Anis sisik From West Bengal, India. Status konservasi Risiko Rendah (IUCN 3.1)[1] Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: Aves Ordo: Passeriformes Famili: Turdidae Genus: Zoothera Spesies: Z. dauma Nama binomial Zoothera dauma(Latham, 1790) Sinonim Geocichla horsfieldi Anis sisik (Zoothera dauma) merupakan salah jenis burung kicau berukuran besar dari keluarga Turdidae dan genus Zoothera. Burung anis sisi merupakan salah satu dari 39 jenis burung anis y...

 

 

Carrie Underwood

Carrie UnderwoodCarrie Underwood di American Music Award pada tahun 2018Informasi latar belakangNama lahirCarrie Marie UnderwoodLahir10 Maret 1983 (umur 41)Muskogee, Oklahoma, Amerika SerikatAsalChecotah, Oklahoma, Amerika SerikatGenre Country Pop Pekerjaan Penyanyi Penulis lagu Instrumen Vokal Gjtar Piano Tahun aktif2005-kiniLabelArista Nashville, Capitol NashvilleArtis terkaitGretchen WilsonSitus webwww.carrieunderwoodofficial.com Carrie Marie Underwood (lahir 10 Maret 1983) merupakan ...

 

 

Taman Lahan Basah Nasional Xixi

Taman Lahan Basah Nasional Xixi西溪国家湿地公园LetakHangzhou, Zhejiang, TiongkokLuas1.150 hektare (2.800 ekar)Didirikan2005www.xixiwetland.com.cn Taman Lahan Basah Nasional Xixi Taman Lahan Basah Nasional Xixi (Hanzi: 西溪国家湿地公园) adalah kawasan lahan basah yang terletak di bagian barat Provinsi Hangzhou, Zhejiang, Tiongkok, seluas total 1.150 hektare. Taman lahan basah ini dipadati dengan enam anak sungai utama yang saling bersilangan, termasuk di antaranya berbagai ...

Oakland, Rhode Island

United States historic placeOakland Historic DistrictU.S. National Register of Historic PlacesU.S. Historic district What's left of the mill in OaklandShow map of Rhode IslandShow map of the United StatesLocationBurrillville, Rhode IslandArchitectMultipleArchitectural styleColonial Revival, Queen Anne, Shingle StyleNRHP reference No.87001359[1]Added to NRHPSeptember 9, 1987 Oakland is a village in Burrillville, Providence County, Rhode Island, United States. It was dev...

 

 

List of shipwrecks in 2014

The list of shipwrecks in 2014 includes ships sunk, foundered, grounded, or otherwise lost during 2014. This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by adding missing items with reliable sources. table of contents ← 2013 2014 2015 → Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec References January 1 January List of shipwrecks: 1 January 2014 Ship State Description Peace  Cambodia The cargo ship issued ...

 

 

Virgin CrossCountry

1997–2007 UK train operating company For the present franchise holder of the Cross Country Route, see CrossCountry. Virgin CrossCountryA Class 220 Voyager at Bristol Temple Meads in 2005OverviewFranchise(s)InterCity CrossCountry 6 January 1997 – 10 November 2007Main route(s)Southern England/London Paddington and South West England/South East Wales – Midlands – Northern England and ScotlandFleet size34 Voyager and 44 Super Voyager setsParent companyVirgin Group (51%)Stagecoach (49%)Rep...

Terms of Endearment

1983 drama film directed by James L. Brooks This article is about the film. For other uses, see Terms of Endearment (disambiguation). Terms of EndearmentTheatrical release posterDirected byJames L. BrooksScreenplay byJames L. BrooksBased onTerms of Endearmentby Larry McMurtryProduced byJames L. BrooksStarring Debra Winger Shirley MacLaine Jack Nicholson Danny DeVito John Lithgow CinematographyAndrzej BartkowiakEdited byRichard MarksMusic byMichael GoreDistributed byParamount PicturesRelease d...

 

 

Checkers speech

1952 television address by Richard Nixon Checkers speechNixon delivering the speechDateSeptember 23, 1952 (1952-09-23)Time6:30 pm (Pacific Time, UTC–8)Duration30 minutesVenueEl Capitan TheatreLocationLos Angeles, California, U.S.Coordinates34°06′10″N 118°19′37″W / 34.1027°N 118.3270°W / 34.1027; -118.3270Also known asFund speechTypeSpeechParticipantsSenator Richard NixonOutcomeNixon remained on Republican ticket after receiving a wave of pu...

 

 

Interair South Africa

Interair South Africa IATA ICAO Kode panggil D6 ILN INLINE Didirikan1993PenghubungBandar Udara Internasional OR TamboArmada5TujuanRegional AfricaKantor pusatJohannesburg, Afrika SelatanSitus webhttp://www.interair.co.za/ Interair South Africa adalah maskapai penerbangan berkantor pusat di Johannesburg, Afrika Selatan. Maskapai ini mengoperasikan penerbangan penumpang terjadwal dari Johannesburg ke kota-kota regional di Afrika. Basis utamanya adalah Bandar Udara Internasional OR Tambo, Johanne...

ソー (オー＝ド＝セーヌ県)

Sceaux 行政国 フランス地域圏 (Région) イル＝ド＝フランス地域圏県 (département) オー＝ド＝セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長（任期） フィリップ・ローラン（2008年-2014年）自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人（2007年）人口密度 5466人/km2住民の呼称 Scéens地理座標 北緯48度4...

 

 

Сэмуайз Гэмджи

Сэмуайз ГэмджиSamwise Gamgee Варианты имени Сэм, Сэмуайз Гарднер, Баназир Гэлбаси Титул Мэр Мичел Делвинга Раса Хоббит Пол Мужской Место обитания Шир Годы жизни 6 апреля 2980 г. Т. Э.[1] — после 61 г. Ч. Э. (102+ года) Оружие Меч из Могильника  Медиафайлы на Викискладе Сэ́муай�...

 

 

Muhammad Syafiuddin II

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Desember 2022. Muhammad Syafiuddin II Muhammad Syafiuddin II (18 November 1841 – 12 September 1924) adalah seorang sultan Sambas. Pada 1891, ia dianugerahi Bahaderi Singa Nederland (Rider in de orde van den Nederlansche Indie Leeuw) oleh Raja William...

Математична освіта

У математичному класі Частина серіїМатематика Основні розділи математики Геометрія Алгебра Теорія чисел Диференціальне та інтегральне числення Математичний аналіз Математична логіка Теорія множин Теорія ймовірностей Математична статистика Дискретна математика Те�...

 

 

The Beverly Hilton

The Beverly HiltonThe Beverly Hilton dilihat dari Wilshire BoulevardLetak di Beverly Hills/Western Los Angeles AreaInformasi umumLokasi9876 Wilshire BoulevardBeverly Hills, California 90210Koordinat34°3′59″N 118°24′47″W / 34.06639°N 118.41306°W / 34.06639; -118.41306Koordinat: 34°3′59″N 118°24′47″W / 34.06639°N 118.41306°W / 34.06639; -118.41306Pembukaan12 Agustus 1955 (1955-08-12)PemilikOasis West RealtyManajemenHil...

 

 

Armenian Rite

Christian liturgical rite Liturgy according to the Armenian Rite in Tatev monastery The Armenian Rite (Armenian: Հայկական պատարագ)[1][2] is a liturgical rite used by both the Armenian Apostolic and the Armenian Catholic churches. Isaac of Armenia, the Catholicos of All Armenians, initiated a series of reforms with help from Mesrop Mashtots in the 5th century that distinguished Armenia from its Greek and Syriac counterparts. These reforms included a retranslation...

Stefan–Boltzmann law

Physical law on the emissive power of black body Stefan's law redirects here. Not to be confused with Stefan's equation or Stefan's formula. Total emitted energy, j ≡ M ∘ {\displaystyle j\equiv M^{\circ }} , of a black body as a function of its temperature, T {\displaystyle T} . The upper (black) curve depicts the Stefan–Boltzmann law, M ∘ = σ T 4 {\displaystyle M^{\circ }=\sigma \,T^{4}} . The lower (blue) curve is total energy according to the Wien approximatio...

 

 

Masa Kekacauan

Minin menyerukan kepada rakyat Nizhny Novgorod untuk melawan Polandia. Lukisan karya Konstantin Makovsky. Masa Kekacauan (bahasa Rusia: Смутное время, Smutnoe vremya) adalah periode dalam sejarah Rusia yang mencakup masa interregnum setelah kematian Tsar Rusia terakhir dari Dinasti Rurik, Feodor Ivanovich, pada tahun 1598, hingga pendirian Dinasti Romanov pada tahun 1613. Pada tahun 1601–03, Rusia mengalami bencana kelaparan yang menewaskan sepertiga penduduknya (sekitar dua...

 

 

第一屆池田內閣

 日本內閣第一次池田内閣だいいちじいけだないかく內閣總理大臣池田勇人（第58任）成立日期1960年7月19日總辭日期1960年10月24日執政黨／派系自由民主黨內閣閣僚名簿（首相官邸） 第一屆池田内閣（日语：第一次池田内閣／だいいちじいけだないかく Daīchiji Ikeda Naikaku */?）是日本眾議院議員、自由民主黨總裁池田勇人就任第58任內閣總理大臣（首相）後，自1960...

Ku Klux Klan

Disambiguazione – KKK rimanda qui. Se stai cercando altri significati, vedi KKK (disambigua). Ku Klux KlanLa croce bianca, uno dei simboli del Ku Klux KlanAttivaPrimo Klan: 1865-1872Secondo Klan: 1915-1944Terzo Klan: 1946/1950-oggi Nazione Stati Uniti ContestoRazzismo negli Stati Uniti IdeologiaIslamofobiaNeonazismoSuprematismo biancoNazionalismo biancoSegregazione razzialeImperialismo statunitenseAnti-immigrazioneAteofobiaAntisemitismoOmofobiaXenofobiaAnticomunismoTerrorismo ...

 

 

Serbia and Montenegro

Federal republic (1992–2003) and political union (2003–2006) in the Balkans FRY redirects here. For other uses, see FRY (disambiguation). For the relations of the modern-day sovereign states of Serbia and Montenegro, see Montenegro–Serbia relations. Federal Republic of Yugoslavia redirects here. Not to be confused with the Socialist Federal Republic of Yugoslavia. Federal Republic of Yugoslavia(1992–2003)Савезна Република ЈугославијаSavezna Republika Jugosla...