Іздеу мәселесі: есептеу күрделілігі, алгоритмдер, және шешім қабылдау теорияларындағы маңызды ұғым. Құрылымды табу, іздеу және шешу жолдары туралы ақпарат.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік күрделілік теориясының, есептеу теориясының және шешім қабылдау теориясының математикасында іздеу мәселесі – екілік қатынас арқылы бейнеленген есептеу мәселесінің бір түрі. Интуитивті түрде, мәселе "x" нысанында "y" құрылымын табудан тұрады. Алгоритм мәселені шешкен деп есептеледі, егер кем дегенде бір сәйкес құрылым болса, онда осы құрылымның бір мысалы шығарылады; әйтпесе, алгоритм тиісті шығыспен тоқталады ("табылған жоқ" немесе осыған ұқсас хабарлама). Кез келген іздеу мәселесіне сәйкес шешім қабылдау мәселесі де бар, атап айтқанда,
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
Бұл анықтаманы n-арлық қатынастарға кеңейтуге болады, егер бірнеше жолдарды бір жолға сығуға мүмкіндік беретін қолайлы кодтау қолданылса (мысалы, оларды үзіліс белгісімен тізімдеу арқылы). Формальды түрде, R қатынасын іздеу мәселесі ретінде қарастыруға болады, ал R-ді есептейтін Тьюринг машинасы оны шешеді деп айтылады. Формальды түрде, егер R – R(x, y) ⊆ Γ+ және T – Тьюринг машинасы болса, онда T, R-ді есептейді, егер:
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:
Егер x үшін R(x, y) болатын y бар болса, онда T, x-ті R(x, z) болатын z шығысымен қабылдайды (бірнеше y болуы мүмкін, және T олардың тек біреуін табуы керек).
Егер x үшін R(x, y) болатын y болмаса, онда T, x-ті қабылдамайды.
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
(Ішінара функцияның графигі екілік қатынас екенін ескеріңіз, және егер T ішінара функцияны есептейтін болса, онда ең көп дегенде бір мүмкін шығыс болады.) Мұндай мәселелер график теориясы және комбинаторлық оптимизацияда жиі кездеседі, мысалы, нақты сәйкестіктер, міндетті емес кликалар, нақты тұрақты жиынтар және т.б. сияқты құрылымдарды іздеуде қызығушылық тудыратын тақырыптар болып табылады.
(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.
Мақсаты
Алгоритм берілмеген, тек шешімнің қандай болу керектігі көрсетілген мәселені қалай шешуге болады?
Find a solution when not given an algorithm to solve a problem, but only a specification of what a solution looks like.