Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Hopfield networks

Sortuj według:

Ogranicz wyniki do:

Approximate solutions of Happynet on cubic graphs

Giannakos A., Pottie O.

Foundations of Computing and Decision Sciences

2006

Vol. 31, No. 3-4

233-241

The HAPPYNET problem is defined as follows : Given a undirected simple graph G with integer weights wvu on its edges vu 6 E(G), find a function s : V(G] → { — 1,1} such that ∀νV(G), v is happy in G, i.e. such that . It is easy to see [3] that HAPPYNET has always a solution, no matter what the input is. However, no polynomial algorithm is known for this problem, which is complete for the class PLS (see [4] for a definition). Parberry et al, have shown in [7] that in the case of cubic graphs (i.e. of maximum degree 3) HAPPYNET is as difficult as for arbitrary graphs. A ρ-approximate solution to a HAPPYNET instance of size n can be defined for 0 le ρ le 1 as a natural extension of the solution function, with at least pn happy vertices. In this paper, we present a polynomial-time algorithm that finds a ρ-approximate solution for the HAPPYNET problem on cubic graphs, with ρ 3/4 .

Neural network models for combinatorial optimization : a survey of deterministic, stochastic and chaotic approaches

Smith K., Potvin J., Kwok T.

Control and Cybernetics

2002

Vol. 31, no 2

183-216

This paper serves as a tutorial on the use of neural networks for solving combinatorial optimization problems. It reviews the two main classes of neural network models : the gradient-based neural networks such as the Hopfield network, and the deformable template approaches such as the elastic net method and self organizing maps. In each class, the original model is presented, its limitations discussed, and subsequent developments and extensions are reviewed. Particular emphasis is placed on stochastic and chaotic variations on the neural network models designed to improve the optimization performance. Finally, the performance of these neural network models is compared and discussed relative to other heuristic approaches.