In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time.Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - PLS (complexity) (en)
- PLS (complexidade) (pt)
|
| rdfs:comment
| - In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time.Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum. (en)
- Na teoria da complexidade computacional, a Pesquisa Local Polinomial (PLS) é uma classe de complexidade que modela a dificuldade de encontrar uma solução ótima localmente para um problema de otimização. Um problema PLS tem um conjunto de instâncias que são codificados usando seqüências de caracteres sobre um alfabeto finito . Para cada instância existe uma solução finita de . Cada solução tem um número inteiro não-negativo de custo dado por uma função e uma vizinhança . Além disso, a existência dos três seguintes algoritmos de tempo polinomial é necessária: (pt)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time.Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum. (en)
- Na teoria da complexidade computacional, a Pesquisa Local Polinomial (PLS) é uma classe de complexidade que modela a dificuldade de encontrar uma solução ótima localmente para um problema de otimização. Um problema PLS tem um conjunto de instâncias que são codificados usando seqüências de caracteres sobre um alfabeto finito . Para cada instância existe uma solução finita de . Cada solução tem um número inteiro não-negativo de custo dado por uma função e uma vizinhança . Além disso, a existência dos três seguintes algoritmos de tempo polinomial é necessária:
* Algoritmo produz alguma solução .
* Algoritmo determina o valor de .
* Algoritmo mapeia um solução para um elemento de tal forma que se tal elemento não existe. Caso contrário, relata que tal elemento não existe. Uma instância tem a estrutura de um grafo implícito, os vértices sendo as soluções com duas soluções conectados por um arco direcionado se e somente se . O mais interessante problema computacional é o seguinte: Dado alguma instância de um problema PLS , encontrar um local optimum de , i.e. uma solução tal que para todos O problema pode ser resolvido usando o seguinte algoritmo: 1.
* Use para encontrar uma solução inicial 2.
* Use o algoritmo para encontrar uma solução melhor . Se tal solução existe, substituir por , caso contrário retorne Infelizmente, isso geralmente leva um número exponencial de passos de melhoria para encontrar um local optimum, mesmo se o problema pode ser resolvido exatamente em tempo polinomial. Exemplos de problemas PLS-completo incluem relativos ao local optimum do problema do caixeiro viajante, corte máximo e satisfatibilidade, bem como a procura de um puro equilíbrio de Nash de um jogo congestionamento. PLS é uma subclasse da TFNP, uma classe de complexidade estreitamente relacionada com a NP que descreve problemas computacionais em que é garantida a existência de uma solução e que pode ser reconhecida em tempo polinomial. Por um problema no PLS, é garantida a existência de uma solução porque o vértice de custo mínimo do gráfico inteiro é uma solução válida, e a validade de uma solução pode ser verificada através do cálculo de seus vizinhos e comparando os custos de cada um. (pt)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
