In computer science, GSAT and WalkSAT are local search algorithms to solve Boolean satisfiability problems. Both algorithms work on formulae in Boolean logic that are in, or have been converted into conjunctive normal form. They start by assigning a random value to each variable in the formula. If the assignment satisfies all clauses, the algorithm terminates, returning the assignment. Otherwise, a variable is flipped and the above is then repeated until all the clauses are satisfied. WalkSAT and GSAT differ in the methods used to select which variable to flip.
| Attributes | Values |
|---|
| rdfs:label
| - WalkSAT (pt)
- WalkSAT (en)
|
| rdfs:comment
| - In computer science, GSAT and WalkSAT are local search algorithms to solve Boolean satisfiability problems. Both algorithms work on formulae in Boolean logic that are in, or have been converted into conjunctive normal form. They start by assigning a random value to each variable in the formula. If the assignment satisfies all clauses, the algorithm terminates, returning the assignment. Otherwise, a variable is flipped and the above is then repeated until all the clauses are satisfied. WalkSAT and GSAT differ in the methods used to select which variable to flip. (en)
- Na ciência da computação, GSAT e WalkSat são algoritmos de busca local para resolver Problemas de Satisfatibilidade Booleana. Ambos os algoritmos trabalham com fórmulas da lógica booleana que estão na, ou foram convertidas para a, forma normal conjuntiva. Começa-se pela atribuição de um valor aleatório para cada variável na fórmula. Se a atribuição satisfaz todas as cláusulas, o algoritmo termina, retornando a atribuição. Caso contrário, uma variável é substituída e repete-se o passo anterior até que todas as cláusulas sejam satisfeitas. WalkSAT e GSAT diferem-se nos métodos utilizados para selecionar quais variáveis serão substituidas. (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In computer science, GSAT and WalkSAT are local search algorithms to solve Boolean satisfiability problems. Both algorithms work on formulae in Boolean logic that are in, or have been converted into conjunctive normal form. They start by assigning a random value to each variable in the formula. If the assignment satisfies all clauses, the algorithm terminates, returning the assignment. Otherwise, a variable is flipped and the above is then repeated until all the clauses are satisfied. WalkSAT and GSAT differ in the methods used to select which variable to flip.
* GSAT makes the change which minimizes the number of unsatisfied clauses in the new assignment, or with some probability picks a variable at random.
* WalkSAT first picks a clause which is unsatisfied by the current assignment, then flips a variable within that clause. The clause is picked at random among unsatisfied clauses. The variable is picked that will result in the fewest previously satisfied clauses becoming unsatisfied, with some probability of picking one of the variables at random. When picking at random, WalkSAT is guaranteed at least a chance of one out of the number of variables in the clause of fixing a currently incorrect assignment. When picking a guessed-to-be-optimal variable, WalkSAT has to do less calculation than GSAT because it is considering fewer possibilities. Both algorithms may restart with a new random assignment if no solution has been found for too long, as a way of getting out of local minima of numbers of unsatisfied clauses. Many versions of GSAT and WalkSAT exist. WalkSAT has been proven particularly useful in solving satisfiability problems produced by conversion from automated planning problems. The approach to planning that converts planning problems into Boolean satisfiability problems is called satplan. MaxWalkSAT is a variant of WalkSAT designed to solve the weighted satisfiability problem, in which each clause has associated with a weight, and the goal is to find an assignment—one which may or may not satisfy the entire formula—that maximizes the total weight of the clauses satisfied by that assignment. (en)
- Na ciência da computação, GSAT e WalkSat são algoritmos de busca local para resolver Problemas de Satisfatibilidade Booleana. Ambos os algoritmos trabalham com fórmulas da lógica booleana que estão na, ou foram convertidas para a, forma normal conjuntiva. Começa-se pela atribuição de um valor aleatório para cada variável na fórmula. Se a atribuição satisfaz todas as cláusulas, o algoritmo termina, retornando a atribuição. Caso contrário, uma variável é substituída e repete-se o passo anterior até que todas as cláusulas sejam satisfeitas. WalkSAT e GSAT diferem-se nos métodos utilizados para selecionar quais variáveis serão substituidas. GSAT faz mudanças nas variáveis buscando minimizar o número de cláusulas não satisfeitas com a nova atribuição, ou escolhe aleatoriamente uma variável com alguma probabilidade. WalkSAT escolhe uma cláusula que não está sendo satisfeita pela atribuição atual e então substitui uma variável dentro dessa cláusula. A cláusula é escolhida aleatoriamente entre as cláusulas não satisfeitas. A variável escolhida, tornará não satisfeitas o menor número de cláusulas anteriormente satisfeitas. Essa variável também é escolhida de forma aleatória, com alguma probabilidade. Quando se escolhe de forma aleatória, WalkSAT garante pelo menos uma chance de fixar uma atribuição atualmente incorreta dentro do número de variáveis na cláusula. Ao escolher uma variavel ideal de forma aleatória, WalkSAT irá fazer menos cálculos do que GSAT pois considerará uma quantidade menor de possibilidades. O algoritmo poderá reiniciar com uma nova atribuição aleatória se não for encontrada uma solução por muito tempo. Essa é uma forma de escapar dos mínimos locais das cláusulas não satisfeitas. Existem muitas versões da GSAT e WalkSAT. WalkSAT se mostrou particularmente útil na resolução de problemas de satisfabilidade produzidos pela conversão dos problemas de planejamento automatizado. A abordagem para o planejamento que converte problemas de planejamento em problemas de satisfatibilidade booleana é chamado satplan. MaxWalkSat é uma variante do WalkSAT projetado para resolver o problema de satisfatibilidade ponderada, em que para cada cláusula tem um peso associado, e o objetivo é encontrar uma atribuição—uma que pode ou não satisfazer toda a fórmula—a qual maximizará o peso total das cláusulas satisfeitas por essa atribuição. (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
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)